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:
“Sadism is all right in its place, but it should be directed to proper ends.”
—Sigmund Freud (1856–1939)
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)
“All experience teaches that, whenever there is a great national establishment, employing large numbers of officials, the public must be reconciled to support many incompetent men; for such is the favoritism and nepotism always prevailing in the purlieus of these establishments, that some incompetent persons are always admitted, to the exclusion of many of the worthy.”
—Herman Melville (1819–1891)