OctoInformBeta

OpenAI preprint, September 2026 · Section 6. From triangle mass to independent sets

Proposition 6.1: Maximum degree determines the loss when one independent set controls the variational functional at every nonnegative weight

Uniform optimizer triangle bounds give independence estimates.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

The problem is to find a large independent set in a clique-free graph from a bound on its maximum degree and a uniform weighted triangle estimate. Let G=(V,E)G=(V,E) be a finite simple graph with n=|V|n=|V| vertices. Its independence number α(G)\alpha(G) is the maximum cardinality of an independent set in GG. The neighborhood NG(v)N_G(v) of v∈Vv\in V is the set of vertices adjacent to vv.✦

For a real vertex weight w:V→ℝw:V\to\mathbb R, the vertex mass w(S)w(S) of S⊆VS\subseteq V and the cross edge mass ew(S,D)e_w(S,D) between S,D⊆VS,D\subseteq V are the sums in (1); the latter runs over ordered adjacent pairs, and S,DS,D may overlap. w(S)=∑v∈Sw(v),ew(S,D)=∑u∈S,v∈D{u,v}∈Ew(u)w(v).w(S)=\sum_{v\in S}w(v), \qquad e_w(S,D)=\sum_{\substack{u\in S,\ v\in D\\\{u,v\}\in E}}w(u)w(v).(1) The unordered edge mass MG(w)M_G(w) is the sum of endpoint weight products over the unordered edges of GG, given by (2). MG(w)=∑{u,v}∈Ew(u)w(v)=12ew(V,V).M_G(w)=\sum_{\{u,v\}\in E}w(u)w(v)=\frac12 e_w(V,V).(2)✦

The common neighborhood mass cw(u,v)c_w(u,v) of vertices u,v∈Vu,v\in V is the mass of their common neighbors.✦ The twice neighborhood triangle mass τw(u)\tau_w(u) at u∈Vu\in V is the sum over its neighbors in (3). cw(u,v)=w(NG(u)∩NG(v)),τw(u)=∑v∈NG(u)w(v)cw(u,v).c_w(u,v)=w\bigl(N_G(u)\cap N_G(v)\bigr), \qquad \tau_w(u)=\sum_{v\in N_G(u)}w(v)c_w(u,v).(3) The unordered triangle mass TG(w)T_G(w) is the sum of products of the three vertex weights over unordered triangles of GG, given by (4). TG(w)=16∑u∈Vw(u)τw(u).T_G(w)=\frac16\sum_{u\in V}w(u)\tau_w(u).(4)✦

The Variational Functional

The vertex potential ϕ\phi is the real-valued function of a real variable tt given by (5). All logarithms are natural, with the convention 0log⁡0=00\log0=0. ϕ(t)={t(1−log⁡|t|),t≠0,0,t=0.\phi(t)= \begin{cases} t(1-\log|t|),&t\ne0,\\ 0,&t=0. \end{cases}(5) The weighted graph potential FG(w)F_G(w) is the sum of the vertex potentials minus the unordered edge mass, as in (6). FG(w)=∑v∈Vϕ(w(v))−MG(w).F_G(w)=\sum_{v\in V}\phi\bigl(w(v)\bigr)-M_G(w).(6)✦ An optimizer of FGF_G is a nonnegative weight w:V→ℝw:V\to\mathbb R such that FG(q)≤FG(w)F_G(q)\le F_G(w) for every nonnegative weight q:V→ℝq:V\to\mathbb R.✦ Write FG*F_G^* for the scalar optimal value of FGF_G on nonnegative weights.

The Claim

Theorem 1. Fix an integer r≥2r\ge2 and real numbers B≥0B\ge0 and Δ≥3\Delta\ge3. Assume that every finite KrK_r-free graph HH and every optimizer ww of FHF_H satisfy the uniform estimate (7): TH(w)≤BMH(w).T_H(w)\le B M_H(w).(7) Let GG be a finite KrK_r-free graph on nn vertices with maximum degree at most Δ\Delta, and put C=3+3B/2C=3+3B/2. There exists an independent set I⊆VI\subseteq V for which (8) holds: FG(q)≤Clog⁡Δ|I|for every q:V→[0,∞).F_G(q)\le C\log\Delta\,|I| \qquad\text{for every }q:V\to[0,\infty).(8)✦ The independence number satisfies (9): α(G)≥nlog⁡Δ4CΔ.\alpha(G)\ge\frac{n\log\Delta}{4C\Delta}.(9)✦

In the paper, the result reads: for every integer r≥4r\ge4, every real Δ≥3\Delta\ge3, and every finite KrK_r-free graph GG with nn vertices and maximum degree at most Δ\Delta, α(G)≥FG*/(Drlog⁡Δ)\alpha(G)\ge F_G^*/(D_r\log\Delta) and α(G)≥nlog⁡Δ/(4DrΔ)\alpha(G)\ge n\log\Delta/(4D_r\Delta), where Br≥0B_r\ge0 is the uniform optimizer triangle constant and Dr=3+3Br/2D_r=3+3B_r/2.

What Is Checked

The statements concern finite KrK_r-free simple graphs with the stated maximum degree bound, together with the weighted masses and nonnegative global maximizers of the variational functional appearing in the uniform hypothesis (7).