TOPICS
Search

Erdős-Rado Number


The Erdős-Rado number k(n,m) is the least k such that every oriented graph on k vertices has an independent vertex set of size n or a transitive tournament on m vertices. The problem of determining these numbers is problem 112 in Bloom's (2026) collection. Ihringer et al. (2021) proved k(n,3)<=n^2-n+3 for n>=3.

Orden (2026a) reports 30<=k(6,3)<=32, improving the earlier range from 29 to 33. The lower bound uses an explicit 29-vertex oriented graph avoiding both required structures. Claude agents helped find the witness and develop the upper-bound argument and Lean formalization. The author reports that Lean, Nanoda, and con-ron checked the formal proof. The preprint remains unrefereed.

Orden (2026b) also reports k(7,3)>=39, k(8,3)>=47, k(6,4)>=78, and k(3,6)>=71. Each lower bound is witnessed by an explicit oriented graph on one fewer vertex. Claude agents found the witnesses and wrote the formalization. The author reports Lean kernel checks of all four witnesses. These bounds leave the exact values open.


See also

Erdős Problems, Oriented Graph, Ramsey Number, Tournament

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 112." 2026. https://www.erdosproblems.com/112.Ihringer, F.; Rajendraprasad, D.; and Weinert, T. V. "New Bounds on the Ramsey Number r(I_m,L_n)." Disc. Math. 344, 112268, 2021. https://arxiv.org/abs/1707.09556.Orden, T. S. "New Bounds on the Erdős-Rado Number k(6,3)." 2026a. https://aixiv.online/abs/2611.02312.Orden, T. S. "Lower Bounds for Four Small Erdős-Rado Numbers in Lean 4." 2026b. https://github.com/Tyorden/erdos-112-small-bounds-lean.

Cite this as:

Weisstein, Eric W. "Erdős-Rado Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Erdos-RadoNumber.html

Subject classifications