The Hadwiger-Ramsey number is the least integer
such that every coloring of the edges of the complete
graph
with
colors has a color class containing a
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,
|
(1)
|
Norin and Rahman (2026) determine the three-color asymptotic:
|
(2)
|
where
|
(3)
|
Here ,
tends to zero, and
is the natural logarithm.
An asymptotically optimal random construction partitions the vertices into two equal
parts. With
, each within-part edge is independently
assigned color 1 with probability
and each of colors 2 and 3 with probability
. 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 . 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
.
Between two parts it takes their unique common line-direction color with probability
, and the spanning color otherwise. If
is the unique root in
of
,
this proves
|
(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.