Ramsey Number

Author

Eric W. Weisstein
September 25, 2024

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

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

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

Values

The Ramsey number is the minimum number of vertices R(m, n) such that all undirected simple graphs of order R contain a clique of order m or an independent set of order n. Ramsey's theorem states that such a number exists for all m and n.

RamseyNumber[m_,n_]:=Module[{R=1,Rmax=9},
While[
R<=Rmax&&!AllTrue[Graphs[R],CliqueNumber[#]≥m||IndependenceNumber[#]≥n&],
R++
];
If[R≤Rmax,R,Missing["NotFound"]]
]

Table[RamseyNumber[m,2],{m,9}]

RamseyNumber[3,3]//Timing

RamseyNumber[3,4]//Timing

TextGrid[Table[RamseyNumber[m,n],{n,5},{m,n}],Dividers->All]//TraditionalForm