Ramsey's Theorem

Author

Eric W. Weisstein
January 12, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/RamseysTheorem.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/RamseysTheorem.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

RamseyNumber[k_,l_]:=Module[{i=3,r=0},
While[
i<=Length[list]&&r==0,
If[((#[[1]]>=k||#[[2]]>=l)&/@(And@@list[[i]])),r=i,i++]
];
r
]

RamseyNumber[n_]:=RamseyNumber[n,n]

Enumeration

n=8

Timing[in=Table[Length/@MaximumIndependentSet/@Graphs[n],{n,8}];]

Timing[cl=Table[Length/@MaximumClique/@Graphs[n],{n,8}];]

list=Transpose/@Transpose[{in,cl}];

Table[RamseyNumber[k,l],{l,4},{k,l}]//TableForm

n=9

Ran overnight:

Timing[in=Table[Length/@MaximumIndependentSet/@Graphs[n],{n,9}];]

Timing[cl=Table[Length/@MaximumClique/@Graphs[n],{n,9}];]

list=Transpose/@Transpose[{in,cl}];

Table[RamseyNumber[k,l],{l,5},{k,l}]//TableForm