Directed Graph Ramsey Numbers
It is also possible to define Ramsey numbers for directed graphs. (These were introduced by P. Erdős & L. Moser.) Let R(n) be the smallest number Q such that any complete graph with singly directed arcs (also called a "tournament") and with ≥ Q nodes contains an acyclic (also called "transitive") n-node subtournament.
This is the directed-graph analogue of what (above) has been called R(n,n;2), the smallest number Z such that any 2-colouring of the edges of a complete undirected graph with ≥ Z nodes, contains a monochromatic complete graph on n nodes. (The directed analogue of the two possible arc colours is the two directions of the arcs, the analogue of "monochromatic" is "all arc-arrows point the same way," i.e. "acyclic.")
Indeed many find the directed graph problem to actually be more elegant than the unidirected one. We have R(0)=0, R(1)=1, R(2)=2, R(3)=4, R(4)=8, R(5)=14, R(6)=28, 32≤R(7)≤55, and R(8) is again a problem you do not want powerful aliens to pose.
Read more about this topic: Ramsey's Theorem
Famous quotes containing the words directed, graph and/or numbers:
“Whether in the field of health, education or welfare, I have put my emphasis on preventive rather than curative programs and tried to influence our elaborate, costly and ill- co-ordinated welfare organizations in that direction. Unfortunately the momentum of social work is still directed toward compensating the victims of our society for its injustices rather than eliminating those injustices.”
—Agnes E. Meyer (1887–1970)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)
“The only phenomenon with which writing has always been concomitant is the creation of cities and empires, that is the integration of large numbers of individuals into a political system, and their grading into castes or classes.... It seems to have favored the exploitation of human beings rather than their enlightenment.”
—Claude Lévi-Strauss (b. 1908)