gpt 6 astra ultra attempt on Math-1136

Chromatic number of random lifts of complete graphs

Definitions and mathematical statement

For an integer $h\ge1$, a labelled $h$-lift of the complete graph $K_5$ has vertex set $\{1,2,3,4,5\}\times\{1,\ldots,h\}$. For each pair $1\le i<j\le5$, choose a bijection $\pi_{ij}:\{1,\ldots,h\}\to\{1,\ldots,h\}$ and put in the $h$ edges \[ (i,a)(j,\pi_{ij}(a)),\qquad 1\le a\le h. \] There are no other edges. Each of the five fibres is independent, and the edges between each pair of fibres form a perfect matching. Every vertex therefore has degree four.

Let $L_h$ be the random lift obtained by choosing the ten bijections independently and uniformly from all $h!$ permutations. This defines the probability model on labelled lifts; it is not uniform over unlabelled isomorphism classes. Write $\chi(L_h)$ for the minimum number of colours in a proper vertex colouring.

The question is whether there exists a fixed integer $q$ such that \[ \lim_{h\to\infty} \mathbb P\left(\chi(L_h)=q\right)=1. \] If so, determine the value $q$. The base graph is fixed as $K_5$ throughout; only the size of the fibres tends to infinity. One asks for exact concentration on a single integer, rather than bounded variance, concentration in an interval of several integers, or a limit for the expected chromatic number. A colouring using fibre labels always uses five colours, but its existence alone gives no answer to this single-value concentration question.

Short English statement

As the fibre size grows, does the chromatic number of a random lift of K5 equal one fixed integer with probability tending to one?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 2 October 2026. The canonical formulation above is retained. This attempt uses a primary-source literature audit, independent restricted proofs, and adversarial checks. Reproved results are not claimed as new. Numerical tests below are reproducible in scripts/check_attempt_batch03_extremal_2026_10_02.py.

Literature and chosen reduction.

Farzad--Theis [S3] establish three-colourability with high probability for random lifts of $K_5$ with one edge deleted. That base graph has nine independent matchings, whereas the catalogue requires all ten; the extra matching cannot be discarded in a proper-colouring proof. We locate the chromatic number of the actual $K_5$ lift in $\{3,4\}$ with probability tending to one, while leaving the choice between those values unresolved.

A triangle detects non-bipartiteness.

Restrict the lift to three fixed base vertices forming a triangle. Following its three matchings once around induces a permutation $\sigma$ of one fibre. This permutation is uniform in $S_h$: condition on two matchings, and the remaining independent uniform permutation makes their composition uniform. A cycle of length $\ell$ in $\sigma$ corresponds to a cycle of length $3\ell$ in the lifted triangle. Therefore the whole lift can be bipartite only if every cycle of $\sigma$ has even length.

Let $a_h$ be the probability of this event. The standard permutation cycle count can be derived by giving a permutation with $c_j$ cycles of length $j$ the count $h!/\prod_j(j^{c_j}c_j!)$. Summing only over even lengths gives the probability generating series \[ \sum_{h\ge0}a_hz^h =\exp\left(\sum_{j\ge1}\frac{z^{2j}}{2j}\right) =(1-z^2)^{-1/2}. \] Consequently $a_h=0$ for odd $h$, and \[ a_{2m}=\frac{\binom{2m}{m}}{4^m} =\prod_{j=1}^m\left(1-\frac1{2j}\right) \le\exp\left(-\frac12\sum_{j=1}^m\frac1j\right) \le(m+1)^{-1/2}. \] The last inequality follows by comparing the harmonic sum with the integral of $1/x$ from $1$ to $m+1$. Thus $\Pr[\chi<3]\le a_h\to0$. No independence between different base triangles is needed.

Controlling the five-colour exception.

Every vertex of the lift has degree exactly four, one neighbour in each other fibre. Brooks's theorem [S4] says that a graph of maximum degree four is four-colourable unless it has a $K_5$ component; the odd-cycle exception in the general theorem has maximum degree two and does not apply here.

A $K_5$ in the lift must use exactly one vertex from each fibre, because vertices in the same fibre are nonadjacent. There are $h^5$ choices of such a tuple. For a fixed tuple, each of the ten independent matching permutations sends its prescribed vertex to the prescribed partner with probability $1/h$. The probability that all its edges occur is $h^{-10}$. Hence the expected number of $K_5$ copies is $h^{-5}$, and a union bound gives probability at most $h^{-5}$ of any copy. Because all degrees are four, any such copy is automatically a whole component. Combining the estimates yields \[ \Pr[3\le\chi(G_h)\le4]\ge1-a_h-h^{-5}\longrightarrow1. \] This uses Brooks's theorem as a cited input; the permutation and exceptional-component estimates are proved above.

Verification and remaining obstruction.

The script enumerates permutations through $h=8$ and checks the exact formula for $a_h$. It also exhausts the $2^{10}$ possible two-lifts and computes their chromatic numbers, confirming that the fibre and matching conventions match the argument. At $h=1$, the lift is $K_5$ and has five colours, so excluding exceptional components is necessary. The triangle estimate alone cannot distinguish three from four colours, and Brooks supplies no three-colouring procedure. Nor does concentration on two adjacent integers imply concentration on a single integer: the probabilities could both remain bounded away from zero.

Final status.

The possible limiting colour counts reduce to three and four with an explicit error bound. Proving that one of these probabilities tends to one, or proving failure of such concentration, is the first remaining gap. The catalogue question is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3310 (OPG-37656), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Chromatic number of random lifts of complete graphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/chromatic_number_of_random_lifts_of_complete_graphs.
• S3 B. Farzad and D. O. Theis, Random lifts of $K_5-e$ are 3-colourable, arXiv:1003.1527; the missing base edge distinguishes this result from the present question. https://arxiv.org/abs/1003.1527.
• S4 R. L. Brooks, On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society 37 $1941$, 194--197. https://doi.org/10.1017/S030500410002168X.