Coloring random subgraphs

Coloring random subgraphs

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph containing at least one edge, and let $k=\chi(G)\ge2$ be its chromatic number. A proper colouring assigns different colours to adjacent vertices. Form the random spanning subgraph $G_{1/2}=(V,E')$ by retaining each edge of $G$ independently with probability $1/2$. The vertex set is unchanged, even when retained edges leave some vertices isolated.

The problem asks whether there exists an absolute constant $c>0$ such that every such graph satisfies \[ \mathbb E\left[\chi(G_{1/2})\right] >c\,\frac{\chi(G)}{\log\chi(G)}. \] Expectation is over all $2^{|E|}$ equally likely edge subsets, and $\log$ means the natural logarithm. Changing the logarithm base only rescales the unknown constant. The restriction $k\ge2$ explicitly avoids the undefined denominator for a nonempty edgeless graph.

Equivalently, the question is whether $\inf_G\mathbb E[\chi(G_{1/2})]\log\chi(G)/\chi(G)>0$, with the infimum over finite graphs having an edge. The strict inequality can be replaced by a non-strict one after decreasing the constant.

The same $c$ must work for all orders and all graph structures. A bound involving $\log|V|$ instead of $\log\chi(G)$ is a different claim, since these quantities can be arbitrarily far apart. The random operation deletes edges, not vertices, and no conditioning on connectedness or on the retained number of edges is imposed.

Short English statement

Does independently keeping half the edges preserve an expected chromatic number at least a constant times the original chromatic number divided by its logarithm?

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 strategy.

Bukh, Krivelevich and Narayanan [S3, version 3] discuss the target as a conjecture and prove several lower-tail results. Their counterexample to a proposed degeneracy bound concerns a different claim. Here logarithms in the catalogue target are natural. We prove an unconditional square-root lower bound, then recover the requested order for graphs with a clique comparable to their chromatic number. Neither result controls arbitrary high-chromatic graphs without large cliques.

A complementary-colouring inequality.

Let $k=\chi(G)$, assign each edge independently to $H$ or $H'$, with equal probability, and retain all vertices. The two random graphs have the same distribution as $G_{1/2}$, although they are not independent. If proper colourings of $H$ and $H'$ use $s,t$ colours, give each vertex the ordered pair of its two colours. Every edge of $G$ appears in one of the two graphs, so its endpoints have different ordered pairs. Therefore $k\le st$ for every outcome. The arithmetic--geometric mean inequality yields \[ \chi(H)+\chi(H')\ge2\sqrt{k},\qquad \mathbb E\chi(G_{1/2})\ge\sqrt{k}. \] This avoids the invalid step of replacing the expectation of a product by a product of expectations. It holds for every finite graph of chromatic number at least two, regardless of its number of vertices.

An explicit clique estimate.

For $q\ge16$, put $t=\lceil4\log_2q\rceil\le q$. In the random graph $(K_q)_{1/2}$, a specified $t$-vertex set is independent with probability $2^{-t(t-1)/2}$. Consequently \[ \Pr[\alpha\ge t]\le\binom qt2^{-t(t-1)/2} \le 2^{t\log_2q-t(t-1)/2}\le\tfrac12. \] For the final inequality, write $x=\log_2q\ge4$ and use $t\ge4x$ to bound the exponent by $t(-x+1/2)\le-1$. On the complementary event every colour class has size less than $t$, so $\chi\ge q/t$. Since $t\le5\log_2q$, \[ \mathbb E\chi((K_q)_{1/2})\ge\frac{q}{10\log_2q} \ge\frac{q}{16\log_2q}. \] For $2\le q<16$, the last bound also holds because the chromatic number is at least one and $q\le16\log_2q$. Thus the weaker displayed constant works uniformly.

If $G$ has a clique of order $q\ge\eta k$, with $q\ge2$ and fixed $\eta>0$, restriction of a colouring to this clique gives \[ \mathbb E\chi(G_{1/2})\ge\frac{\log 2}{16}\frac{q}{\log q} \ge\frac{\eta\log 2}{16}\frac{k}{\log k}. \] The last comparison uses $q\ge\eta k$ and $q\le k$. Taking half this constant supplies the catalogue's strict inequality on this restricted class. In particular the conjectured order holds whenever $\chi(G)=\omega(G)$.

Boundary tests.

For a bipartite graph with $m\ge1$ edges, the random subgraph has chromatic number one exactly when all edges disappear; otherwise it has chromatic number two. Its expectation is $2-2^{-m}$. For an odd cycle with $m$ edges, every proper nonempty edge subset is a bipartite graph with an edge. The full cycle has chromatic number three and the empty subgraph has chromatic number one; these two exceptional outcomes have the same probability. The expectation is therefore exactly two. The script enumerates random subgraphs of small cliques and odd cycles and verifies these identities using exact integer sums.

Verification and final status.

The clique estimate uses only edges inside the clique, so arbitrary extra vertices cause no hidden factor involving $|V(G)|$. The universal $\sqrt{k}$ bound is asymptotically smaller than $k/\log k$. For graphs with clique number $o(k)$, the restricted proof supplies no constant independent of $G$. Controlling that regime is the first gap. The full expectation inequality is UNRESOLVED by this attempt.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3308 (OPG-827), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Coloring random subgraphs. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/coloring_random_subgraphs.
• S3 B. Bukh, M. Krivelevich and B. Narayanan, Colouring random subgraphs, arXiv:2312.08340v3, 6 January 2025; particularly the initial conjecture and the distinction between chromatic and degeneracy assertions. https://arxiv.org/html/2312.08340v3.