Forbidden subgraphs, independence, and correspondence coloring

Source and verification

This article explains family 184 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Forbidden cliques, degrees, and independent sets

An independent set contains no adjacent pair. For a graph $G$ on $n$ vertices, write $\alpha (G)$ for its largest size, $d=2|E(G)|/n$ for average degree, and $\Delta$ for maximum degree. A graph is $K_r$-free if it has no clique of size $r$, as an ordinary subgraph.

The elementary lower bound $\alpha (G)\ge n/(d+1)$ follows by taking a uniformly random vertex order and selecting vertices preceding all their neighbors. The expected selected size is ${\sum }_{v}1/(d(v)+1)$, at least $n/(d+1)$ by convexity. Selected vertices are independent because an adjacent pair cannot both precede the other.

Independence manuscript claim

For every fixed $r\ge 4$, there is $c_r>0$ such that every $K_r$-free graph of average degree $d\ge 2$ satisfies

$$\alpha (G)\ge c_r\frac{n\log d}{d}.$$

The constant is uniform in the graph order and degree. (OpenAI, 2026)

The improvement is a logarithmic factor. The theorem does not assert an optimal leading constant or an efficient algorithm.

🏷️ Correspondence coloring

In list coloring, every vertex has its own allowed colors, and equal colors are forbidden across an edge. Correspondence coloring permits a more general rule: use disjoint lists $L(v)$ and, for each edge $uv$, a matching between $L(u)$ and $L(v)$ specifying forbidden pairs. These matchings need not identify colors consistently around cycles.

The correspondence chromatic number ${\chi }_{\mathrm{DP}}(G)$ is the least list size making every such assignment colorable. It dominates the list and ordinary chromatic numbers and is at most $\Delta +1$ by greedy selection.

Coloring manuscript claim

For every fixed $r\ge 4$, constants $C_r,{\Delta }_r$ give

$${\chi }_{\mathrm{DP}}(G)\le \lceil C_r\frac{\Delta }{\log \Delta }\rceil$$

for every $K_r$-free graph with $\Delta \ge {\Delta }_r$. The constants are independent of list sizes and correspondence matchings. (OpenAI, 2026b)

If a fixed graph $F$ is forbidden as an ordinary subgraph, set $r=\max \{4,|V(F)|\}$. Since $K_r$ contains $F$, an $F$-free graph is $K_r$-free, giving the same order of coloring bound with constants depending on $F$. This argument does not apply to exclusion only as an induced subgraph.

🏷️ Entropy-weighted optimization

The independence proof assigns positive weights $w_v$ and considers

$$\begin{array}{rl}{M}_G(w)& =\sum _{uv\in E(G)}{w}_u{w}_v,\\ T_G(w)& =\sum _{\{u,v,z\}\text{ triangle}}{w}_u{w}_v{w}_z,\\ F_G(w)& =\sum _v{w}_v(1-\log w_v)\\ & -M_G(w).\end{array}$$

Edge and triangle sums are unordered. At a maximizing weight vector, the central estimate bounds triangle mass by an $r$-dependent multiple of edge mass.

Random multipliers of mean one first extract a bound on weighted edges between arbitrary vertex sets. This bound survives deleting edges and splitting vertices into copies, provided every original directed edge is retained at most once. The new weights need not remain optimizers, so retaining an invariant independent of optimality is essential.

Walks inside neighborhoods then guide a splitting process. Entropy estimates make distributions started from the two ends of a weighted triangle close on average. Coupling those distributions puts most triangle edges into compatible groups, while a cutoff limits each group’s neighbor weight. Splitting reduces a neighborhood bound from $e^x$ to $e^{\sqrt{x}}$ with summable losses. Once neighborhood weights are bounded, the triangle-to-edge estimate is immediate.

🏷️ Turning the potential into independent vertices

For maximum degree at most $\Delta$, constant weights of order $(\log \Delta )/\Delta$ give $F_G$ at least a constant times $n(\log \Delta {)}^2/\Delta$.

Select a vertex and delete its closed neighborhood. The loss of potential involves edges among its neighbors, hence triangles through that vertex. Averaging with probabilities proportional to $w_v$ and using the triangle bound finds a deletion costing at most $D_r\log \Delta$. Repeating produces an independent set with size of order $n\log \Delta /\Delta$.

To pass to average degree, discard vertices of degree greater than $2d$. Fewer than half the vertices are discarded by the degree sum. The remaining graph has at least $n/2$ vertices and maximum degree at most $2d$, so the maximum-degree result gives the asserted order after adjusting constants. Small degree ranges can be absorbed into the constant.

🏷️ Random coloring rounds and their extra obligation

The coloring proof works on the graph of list entries, where edges are forbidden pairs. Every entry has at most one neighbor in any other list, and every clique projects to a clique of $G$.

Small random activation rounds color some vertices while maintaining sufficient total weight in each remaining list. A potential combines entropy, lost-weight penalties, and incident conflicting weight. Shared deletions at common neighbors create positive triangle correlations, so local weight adjustments must compensate for them.

The independence paper’s splitting ideas supply the structural estimate, but correspondence coloring needs more: each adjustment must affect only a controlled number of entries in each list. Small graph radius alone does not imply this, since one list may have many entries nearby.

The one-neighbor-per-list property supplies the needed participation bound. Concentration then applies to functions of independent trial inputs even though updated entry weights are dependent. Collision edges are controlled by extracting matchings, whose endpoint activations are independent. A local-lemma argument obtains simultaneous progress, and greedy coloring finishes once every remaining list has more entries than the remaining degree.

🏷️ Key steps and proof outlines

Optimize a potential that pays for deleting a neighborhood

For vertex weights $w_v\ge 0$, write $W={\sum }_v{w}_v$, $M={\sum }_{uv\in E}{w}_u{w}_v$, and consider

$$F(w)=\sum _v{w}_v(1-\log w_v)-M.$$

At the maximizing weights, the source proves positivity, $w_v\le 1$, and the stationary equation $\log (1/w_v)=w(N(v))$, where $w(S)={\sum }_{u\in S}{w}_u$. The clique-free structural input bounds weighted triangle mass $T$ by $B_{r}M$, with $B_r$ depending on the forbidden clique size. (OpenAI, 2026a)

Take the closed neighborhood $A_v=\{v\}\cup N(v)$ and erase its weights. Stationarity makes the potential loss exactly

$$F(w)-F(w{|}_{V\setminus A_v})=w(A_v)+M_{G[A_v]}(w).$$

Average this loss with probability $w_v/W$. The numerator expands into

$$\sum _v{w}_v^2+2M+\sum _v{w}_v^{2}w(N(v))+3T.$$

Using $w_v\le 1$ and the triangle bound, the average is at most $1+(4+3B_r)M/W$. This calculation is the bridge from the structural triangle estimate to an actual vertex-selection algorithm: some closed neighborhood costs no more than the average.

Compare the potential’s size with its deletion cost

For maximum degree $\Delta \ge 3$, unweighted Jensen gives

$$\log (n/W)\le \frac{1}{n}\sum _v\log (1/w_v)\le \frac{\Delta W}{n}.$$

It follows that $W\ge n/\Delta$. Weighted Jensen then gives

$$\frac{2M}{W}=\sum _v\frac{w_v}{W}\log (1/w_v)\le \log (n/W)\le \log \Delta .$$

Thus one can choose a vertex, add it to the independent set, and delete its closed neighborhood at potential cost at most $D_r\log \Delta$, where $D_r=3+3B_r/2$. Repeating yields an independent set of size at least $F^{\ast }/(D_r\log \Delta )$, with $F^{\ast }$ the optimal potential.

The constant test weight $w_v=(\log \Delta )/\Delta$ gives $F^{\ast }\ge n(\log \Delta {)}^2/(4\Delta )$. Dividing this initial budget by the cost per chosen vertex gives the logarithmic improvement. For average degree $d$, first retain the at least half of the vertices of degree at most $2d$, and apply the maximum-degree result there. Each step has a distinct role: the clique-free input controls triangles, stationarity turns deletion into an exact identity, and Jensen compares the resulting weighted quantities.

Concentration when updated color weights are dependent

The correspondence-coloring companion uses random rounds, but updated list entries are not mutually independent. A useful replacement is bounded participation. Suppose $X_j$ is a bounded function of independent underlying inputs, has range length $b_j$, and each input participates in at most $p$ such functions. Repeated conditioning and Hölder’s inequality give the generalized product bound needed for

$$\log \mathbb{E}\exp \left(s\sum _j(X_j-\mathbb{E}{X}_j)\right)\le \frac{p{s}^2}{8}\sum _j{b}_j^2.$$

For a single variable, the bound follows because every exponential tilt still has variance at most $b_j^2/4$; integrate this bound twice. Optimizing the exponential Markov estimate gives an upper tail at most $\exp (-2a^2/(p{\sum }_j{b}_j^2))$ for deviation $a$. (OpenAI, 2026b)

The correspondence condition is operational here: along an edge, an activated color conflicts with at most one color in the neighboring list. Together with the adjustment rule’s participation bound $P_0$, this bounds how many summands one random input influences. For sums indexed by matching edges, the participation count is at most $2P_0$. This supplies concentration without asserting independence of the updated weights.

Large collision counts contain an unlikely matching

Let $X_v$ count simultaneously activated conflicting pairs in the relevant local graph. The source bounds its mean by $\mu \le {\Delta }^{0.80+o(1)}$. A separate exponential estimate shows that its activated maximum degree exceeds ${\Delta }^{0.01}$ only with very small probability. Outside that exceptional event, too many collision edges force, by greedy selection, a matching of size $m=\lceil {\Delta }^{0.82}\rceil$.

Along a matching the endpoints are disjoint, so the activation probabilities multiply. Summing over such matchings gives

$$\mathrm{Pr}(\text{an activated matching of size }m)\le \frac{{\mu }^m}{m!}\le (e\mu /m{)}^m\le \exp (-{\Delta }^{0.8})$$

for sufficiently large $\Delta$. This bounds the collision losses needed to make each coloring round advance. The proof therefore combines bounded-participation concentration for many small contributions with matching extraction for rare large collision configurations; these are separate mechanisms in the companion’s rounds section.

See Also

• Coloring and clique minors controls lists through clique minors rather than forbidden subgraphs and degree.
• Off-diagonal Ramsey numbers studies extremal graph order; an average-degree theorem must also handle sparse input graphs.

🏷️ Manuscripts and verification scope

• Correspondence coloring graphs with a forbidden clique — pinned manuscript and companion source.
• A logarithmic independence bound for clique-free graphs — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. Despite the family heading, the page documents only the average-degree independence bound. It does not document the correspondence-coloring companion. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A logarithmic independence bound for clique-free graphs.

🐻  OpenAI 2026b. Correspondence coloring graphs with a forbidden clique.