OctoInformBeta

OpenAI preprint, September 2026 · §5. Splitting at a scale · §5

Lemma 5.2: For 0<α≤10<\alpha\le1 and α2u≥100\alpha^2u\ge100, a graph of order uu with vertex expansion at least α\alpha has a cycle longer than α2u/100\alpha^2u/100

Vertex expansion forces a long cycle and a long path.

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

Let HH be a graph of order uu whose vertex sets expand, expansion being counted in vertices rather than in edges as in cut expansion. The question is how long a cycle, and how long a path, HH must contain, in terms of uu and the rate α\alpha at which its vertex sets expand.

Vertex Expansion

The external neighbourhood of a set UU of vertices of HH is the set NH(U)\UN_H(U)\setminus U of vertices of HH outside UU that are adjacent to at least one vertex of UU: NH(U)\U={v∈V(H)\U:vx∈E(H) for some x∈U}.N_H(U)\setminus U=\{\,v\in V(H)\setminus U : vx\in E(H)\text{ for some }x\in U\,\}.(1)✦

For a real number α\alpha, a graph HH of order uu has vertex expansion at least α\alpha when every nonempty set UU of at most u/2u/2 vertices has at least α|U|\alpha|U| vertices in its external neighbourhood: |NH(U)\U|≥α|U|for every U⊆V(H) with 0<|U|≤u/2.|N_H(U)\setminus U|\ge\alpha|U|\qquad\text{for every }U\subseteq V(H)\text{ with }0<|U|\le u/2.(2)✦

The Claim

Theorem 1. Let α≤1\alpha\le 1 be a real number and let HH be a graph of order uu with vertex expansion at least α\alpha.

  1. If α>0\alpha>0 and α2u/100≥1\alpha^2u/100\ge 1, then HH contains a cycle of length ℓ\ell, where ℓ>α2u100.\ell>\frac{\alpha^2u}{100}.(3)✦

  2. There are distinct vertices v1,…,vmv_1,\dots,v_m of HH, each adjacent to the next, where m≥αu3.m\ge\frac{\alpha u}{3}.(4)✦

In the paper, the result reads: with ε=1/32\varepsilon=1/32, for every sufficiently large integer uu and α=ε/log⁡2u\alpha=\varepsilon/\log^2 u, a graph HH of order uu in which |NH(U)\U|≥α|U||N_H(U)\setminus U|\ge\alpha|U| for every UU with 0<|U|≤u/20<|U|\le u/2 contains a cycle of length greater than q(u)=α2u/100q(u)=\alpha^2u/100.

The box asks of α\alpha only that 0<α≤10<\alpha\le 1 and α2u/100≥1\alpha^2u/100\ge 1, which the paper’s α\alpha satisfies for every large uu.

What Is Checked

The two statements in the box are stated over a graph HH of order uu and a real number α≤1\alpha\le 1, through the external neighbourhoods (1) of the vertex sets of HH and the condition that HH has vertex expansion at least α\alpha as in (2).