# Correspondence coloring with a fixed forbidden subgraph

> Networks with no fixed-size clique have larger independent sets and need fewer colors, by a log factor. Plain-English explainer, Lean status and sources.

Canonical: https://closedform.nishachay.tech/e/openai-math-2026-184/
Last updated: 2026-10-14

**Networks with no fixed-size clique have larger independent sets and need fewer colors, by a log factor.**

**Trust:** Formal proof listed · **Papers:** 2 · **First paper:** September 25, 2026 · **Field:** Combinatorics · **Entry:** 184

*Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error.

An independent set is a group of points in a network with no links between them. If no four points are all linked, such sets should be larger than in general networks. One paper proves they are larger by a factor of order log d, where d is the average number of links. A second paper claims a matching saving in colors, even for a harder kind of coloring.

## At a glance

- **First step:** 1981 (Ajtai, Erdős, Komlós and Szemerédi, who posed the independence conjecture)
- **Significance:** Major. It settles two long-standing conjectures on independent sets and coloring in clique-free graphs.
- **Trust:** Formal proof listed
- **Field:** Combinatorics (2 papers)

## The explanation

Draw five points in a ring, each joined to its two neighbors. Pick points so that no two picked points are joined. Such a choice is an independent set. In the ring of five, you can pick two points, but never three. Now draw six points as two separate triangles. Again you can pick only two, one from each triangle.

A simple rule says how many you can always pick. Say there are n points with d links each on average. Then you can always pick at least n divided by d + 1. Groups of points that are all joined to each other, called cliques, show the rule cannot be improved in general[1]. The two triangles fit it exactly: 6 divided by 3 is 2.

What if the network has no large clique? Suppose no four points are all joined to each other. Then much larger independent sets should exist. For triangle-free networks, Ajtai, Komlós and Szemerédi showed this in 1980[2]. The gain is a factor of about log d, the natural logarithm of the average number of links. For a million points with 1,000 links each on average, the simple rule promises about 999 points. A bound of n log d divided by d would give about 6,908.

In 1981, Ajtai, Erdős, Komlós and Szemerédi conjectured the same gain when any fixed clique is banned. They proved a weaker gain, of order log log d[3]. Shearer later came within a factor of log log d of the goal[4]. A log log is tiny, about 1.9 when d is 1,000, but it grows without limit.

One paper proves the conjecture for every fixed clique size r of at least 4[5,6]. Every network with no r points all joined has an independent set of at least a constant times n log d divided by d. The constant depends only on r. The order cannot be improved, even for triangle-free networks[7].

A second paper turns to coloring. Give each point a color so that joined points differ. If each point has at most Δ links, Δ + 1 colors always suffice. Color the points one at a time, avoiding colors their neighbors already use[8]. Correspondence coloring is a harder version, introduced by Dvořák and Postle[9]. Each point gets its own list of options, and each link says which options clash across it. Take a ring of four points with two options each. Ordinary coloring works by alternating. But let one link clash option 1 with option 2, and vice versa. Then no choice works, as a check of all 16 cases confirms. Any correspondence bound also covers ordinary coloring[10].

Without triangles, Johansson showed that about Δ divided by log Δ colors are enough. With a fixed clique banned, his bound kept an extra log log Δ factor[11]. That was still the best general correspondence bound for r of at least 4[12]. Dhawan, Janzer and Methuku had removed the extra factor for ordinary coloring in a narrower family of cases[13].

That paper claims a bound of order Δ divided by log Δ for every network with no r-point clique, once Δ is large[14]. It applies to correspondence coloring, and so to ordinary coloring too. The same holds when any fixed network F is banned as a part. This settles a conjecture of Alon, Krivelevich and Sudakov in a stronger form[15]. When F contains a closed loop, the order Δ divided by log Δ cannot be improved[16]. Neither paper gives a value for its constants[17].

The main obstacle was triangles. Banning four-point cliques still allows many triangles, and triangles spoil the counting that works when they are absent. The independence proof spreads weights over the points. Its central step bounds the weight on triangles by a constant times the weight on links[18]. The coloring proof colors a few points at a time in random rounds[19]. Removing one option can knock out two clashing options at once, which creates unwanted correlations[20]. It reuses and extends the triangle tools of the independence paper to pay for this[21].

How sure is this? A computer proof checker called Lean has checked a formal version of the independence bound. It covers every network with no r-point clique, for each r of at least 4, with average degree at least 2. The coloring paper is not in the Lean scope note, so its result remains a claim. The independence proof claims no efficient method for finding the sets[22]. No specialist review of these papers has been published.

**What it doesn't show.** This does not give values for the constants, or claim a fast method for finding the independent sets.

## Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

## Hype check

Major if the proofs hold. Lean has checked a formal version of the independence bound. The coloring result is outside the Lean note, the constants have no stated value, and no specialist review is published.

## Words used

- **Independent set:** A group of points in a network with no link between any two of them.
- **Clique:** A group of points that are all linked to each other.
- **Average degree:** The average number of links at a point, written d.
- **Correspondence coloring:** Coloring where each point has its own list of options and each link says which options clash across it.
- **Logarithm:** A slowly growing function; the natural log of 1,000 is about 6.9.
- **Lean:** A computer program that checks each step of a formally written proof.

## The original papers (2)

- [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf) - October 5, 2026
- [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf) - September 25, 2026 · Formal proof listed

- [Lean notes](https://github.com/openai/math/blob/main/lean/docs/184.md)

## Quoted lines from the paper (22)

[1] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> For general graphs, the elementary bound $\alpha(G)\ge n/(d+1)$ is best possible, as disjoint unions of cliques show.

[2] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> Ajtai, Koml\'os and Szemer\'edi proved the logarithmic improvement when triangles are excluded.

[3] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> They proved the lower bound $\Omega_r(n\log\log d/d)$ as $d\to\infty$, so excluding any fixed clique already improves on the general bound.

[4] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> Theorem … removes this remaining $\log\log d$ denominator.

[5] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> We prove that the improvement is a factor of order $\log d$.

[6] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> The theorem gives a positive answer to the fixed-clique-size independence conjecture of Ajtai, Erd\H{o}s, Koml\'os and Szemer\'edi, also recorded as Erd\H{o}s Problem 802.

[7] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> The order $n\log d/d$ is best possible up to a constant factor even for triangle-free graphs, and hence for the larger class of $K_r$-free graphs.

[8] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> Thus \[ \chi(G)\le \chi_{\mathrm{list}}(G)\le\chi_{\mathrm{DP}}(G) \le \Delta(G)+1, \] where the last inequality follows by greedy coloring.

[9] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> Dvo\v{r}\'ak and Postle introduced correspondence coloring in their 2015 preprint, published as, to allow the identification of colors to vary from edge to edge.

[10] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> This notion includes list coloring: replace each color in each list by a distinct copy, and match copies of the same color along an edge.

[11] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> Johansson subsequently obtained the list-coloring bounds $O(\Delta/\log\Delta)$ for triangle-free graphs and $O_r(\Delta\log\log\Delta/\log\Delta)$ for $K_r$-free graphs.

[12] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> In particular, the previous general upper bound for fixed $r\ge4$ was \[ \chi_{\mathrm{DP}}(G) =O_r\!\left(\frac{\Delta\log\log\Delta}{\log\Delta}\right). \]

[13] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> More recently, Dhawan, Janzer, and Methuku proved $O_t(\Delta/\log\Delta)$ for ordinary coloring of $K_{t,t,t}$-free graphs, and hence for every fixed three-colorable forbidden graph.

[14] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> We prove a logarithmic improvement when the clique number is bounded.

[15] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> The corollary therefore proves that conjecture in the stronger correspondence-coloring form.

[16] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> If $F$ contains a cycle, the order $\Delta/\log\Delta$ cannot be improved in general: graphs with girth larger than $|V(F)|$ can have maximum degree at most $\Delta$ and chromatic number of this order; see also the proof of.

[17] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> We do not optimize the constant or the degree threshold.

[18] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> The central step is to show that $T_G(w)$ is at most a constant depending only on $r$ times $M_G(w)$ when $w$ maximizes, over nonnegative vertex weights, \[ F_G(w)=\sum_v w_v(1-\log w_v)-M_G(w). \]

[19] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> The proof constructs a partial coloring in small random rounds.

[20] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> Even after compensating their individual losses to first order, this shared deletion creates a positive edge correlation.

[21] From [Correspondence coloring graphs with a forbidden clique](https://github.com/openai/math/blob/main/preprints/Correspondence-Coloring-Graphs-with-a-Forbidden-Clique-October-5-2026/correspondence-coloring-forbidden-clique.pdf):

> The structural argument develops the multiplier and entropy-splitting methods of the companion manuscript \emph{A logarithmic independence bound for clique-free graphs}.

[22] From [A logarithmic independence bound for clique-free graphs](https://github.com/openai/math/blob/main/preprints/A-Logarithmic-Independence-Bound-for-Clique-Free-Graphs-September-25-2026/paper.pdf):

> The proof gives an existence result with an $r$-dependent constant; it makes no claim of an efficient algorithm or an optimal leading constant.

## Other sources

- [M. Ajtai, J. Komlós and E. Szemerédi, “A note on Ramsey numbers”, Journal of Combinatorial Theory, Series A 29(3) (1980), 354–360](https://doi.org/10.1016/0097-3165(80)90030-8)
- [M. Ajtai, P. Erdős, J. Komlós and E. Szemerédi, “On Turán’s theorem for sparse graphs”, Combinatorica 1(4) (1981), 313–317](https://doi.org/10.1007/BF02579451)
- [J. B. Shearer, “On the independence number of sparse graphs”, Random Structures & Algorithms 7(3) (1995), 269–271](https://doi.org/10.1002/rsa.3240070305)
- [N. Alon, M. Krivelevich and B. Sudakov, “Coloring graphs with sparse neighborhoods”, Journal of Combinatorial Theory, Series B 77(1) (1999), 73–82](https://doi.org/10.1006/jctb.1999.1910)
- [Z. Dvořák and L. Postle, “Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8”, Journal of Combinatorial Theory, Series B 129 (2018), 38–54](https://doi.org/10.1016/j.jctb.2017.09.001)
- [A. Dhawan, O. Janzer and A. Methuku, “Independent sets and colorings of K_{t,t,t}-free graphs”, arXiv:2511.17191 (2025)](https://arxiv.org/abs/2511.17191)
- [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model”

## Related

- [Superexponential van der Waerden numbers](https://closedform.nishachay.tech/e/openai-math-2026-160/) - Combinatorics
- [The Erdős–Gallai cycle-decomposition conjecture](https://closedform.nishachay.tech/e/openai-math-2026-181/) - Combinatorics
- [Cycle–clique Ramsey numbers](https://closedform.nishachay.tech/e/openai-math-2026-189/) - Combinatorics
- [The hypercube Ramsey conjecture](https://closedform.nishachay.tech/e/openai-math-2026-171/) - Combinatorics
- [Erdős’s reciprocal-sum conjecture and quasipolynomial Szemerédi bounds](https://closedform.nishachay.tech/e/openai-math-2026-159/) - Combinatorics
- [Combinatorics](https://closedform.nishachay.tech/science/mathematics/combinatorics/) - Field · 37 results
- [Erdős problems](https://closedform.nishachay.tech/topic/erdos-problems/) - Topic · 13 results
- [Graph theory](https://closedform.nishachay.tech/topic/graph-theory/) - Topic · 40 results
- [Open since the 1980s](https://closedform.nishachay.tech/open-since/1980s/) - Era · 60 results
- [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results
- [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20184%5D%20)