TOPICS
Search

Hadwiger-Ramsey Number


The Hadwiger-Ramsey number R_h(k;l) is the least integer n such that every coloring of the edges of the complete graph K_n with l colors has a color class containing a K_k graph minor (Axenovich and Steiner 2026). Each color class is regarded as a spanning graph, and its largest complete minor is measured by the Hadwiger number. The requirement is a monochromatic complete minor, rather than the monochromatic complete subgraph in an ordinary Ramsey number. For two colors,

 R_h(k;2)=(1+o(1))ksqrt(log_2k).
(1)

Norin and Rahman (2026) determine the three-color asymptotic:

 R_h(k;3)=(beta^(-1)+o(1))ksqrt(lnk),
(2)

where

 beta=1/2sqrt(-ln(10-4sqrt(6))),  beta^(-1)=1.58149....
(3)

Here k->infty, o(1) tends to zero, and ln is the natural logarithm. An asymptotically optimal random construction partitions the vertices into two equal parts. With p=5-2sqrt(6), each within-part edge is independently assigned color 1 with probability 1-2p and each of colors 2 and 3 with probability p. Every between-part edge is independently assigned color 2 or 3 with equal probability. Uniform random three-coloring gives a weaker bound.

The paper also gives a five-color lower-bound construction using the nine points of the affine plane over GF(3). Four colors correspond to the four partitions into three parallel lines, and the fifth is a spanning color. Within each of the nine equal vertex parts, an edge takes each of the first four colors with probability 1/4. Between two parts it takes their unique common line-direction color with probability p, and the spanning color otherwise. If p is the unique root in (0,1) of 4p^(24)=3(1-p)^2, this proves

 liminf_(k->infty)(R_h(k;5))/(ksqrt(lnk))>=sqrt(9/(-8lnp))=2.5901....
(4)

Optimality of this five-color construction is not established. Norin and Rahman report that AI supplied technical random-graph and dense-minor lemmas following their outlines, which they subsequently checked and polished.


See also

Hadwiger Number, Ramsey Number

Explore with Wolfram|Alpha

References

Axenovich, M. and Steiner, R. "A Note on Ramsey Numbers for Minors." 2026. https://arxiv.org/abs/2603.10510.Norin, S. and Rahman, N. "Asymptotics of the Three-color Hadwiger-Ramsey Numbers." 15 Nov 2026. https://arxiv.org/abs/2611.19834v1.

Cite this as:

Weisstein, Eric W. "Hadwiger-Ramsey Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Hadwiger-RamseyNumber.html

Subject classifications