OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: For nontrivial increasing properties invariant under vertex permutations

A bound on graph threshold widths.

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 VnV_n be a set of nn labelled vertices. The potential edges form the set EnE_n in (1); a labelled graph is a function xx in the same display, with x(e)=1x(e)=1 indicating that the edge ee is present. En=(Vn2),x:En→{0,1}.E_n=\binom{V_n}{2},\qquad x\colon E_n\longrightarrow\{0,1\}.(1) A Boolean graph property is a function f:{0,1}En→{0,1}f\colon\{0,1\}^{E_n}\to\{0,1\}, with f(x)=1f(x)=1 indicating that xx belongs to the property.

For labelled graphs xx and yy, edge inclusion x⊆yx\subseteq y means that every edge present in xx is present in yy.✦ An increasing graph property ff is a Boolean graph property such that f(x)=1f(x)=1 and x⊆yx\subseteq y imply f(y)=1f(y)=1.✦ A nontrivial graph property ff is a Boolean graph property that takes both values 00 and 11.✦

A permutation π\pi of VnV_n acts on edges and labelled graphs by (2). πe={π(v):v∈e},(πx)(e)=x(π−1e).\pi e=\{\pi(v):v\in e\},\qquad (\pi x)(e)=x(\pi^{-1}e).(2) A vertex-invariant graph property ff is a Boolean graph property satisfying f(πx)=f(x)f(\pi x)=f(x) for every permutation π\pi of VnV_n and every labelled graph xx.✦ For a permutation π\pi of VnV_n and a potential edge e∈Ene\in E_n, the permuted edge πe∈En\pi e\in E_n is the image of ee under π\pi. For a permutation π\pi of VnV_n and a labelled graph xx, the relabelled graph πx\pi x assigns to each potential edge ee the value that xx assigns to π−1e\pi^{-1}e.

The random graph G(n,p)G(n,p), where 0≤p≤10\le p\le1, has each potential edge present independently with probability pp. The probability mass wp(x)w_p(x) of the random graph G(n,p)G(n,p) at a labelled graph xx is the probability of obtaining xx. The Boolean indicator 𝟏{f(x)=1}\mathbf{1}_{\{f(x)=1\}} is the real number 11 when f(x)=1f(x)=1 and 00 otherwise.✦ The graph property probability μp(f)\mu_p(f) is the expectation in (3). μp(f)=∑x∈{0,1}Enwp(x)𝟏{f(x)=1}=Pr⁡(f(G(n,p))=1).\mu_p(f) =\sum_{x\in\{0,1\}^{E_n}}w_p(x)\mathbf{1}_{\{f(x)=1\}} =\Pr\bigl(f(G(n,p))=1\bigr).(3)✦

The infimum quantile pa(f)p_a(f) at a real level aa is the infimum in (4), taken over edge densities in the closed unit interval. pa(f)=inf⁡{p∈[0,1]:μp(f)≥a}.p_a(f)=\inf\{p\in[0,1]:\mu_p(f)\ge a\}.(4)✦

All logarithms are natural logarithms.

The Claim

Theorem 1. Let n≥2n\ge2, and let ff be a nontrivial increasing graph property on nn vertices that is invariant under vertex permutations. For 0<ε<1/20<\varepsilon<1/2, its quantile width satisfies (5): p1−ε(f)−pε(f)≤219(log⁡n)2log⁡(12ε).p_{1-\varepsilon}(f)-p_{\varepsilon}(f) \le \frac{2^{19}}{(\log n)^2} \log\!\left(\frac{1}{2\varepsilon}\right).(5)✦

What Is Checked

The claim is stated over nontrivial increasing vertex-invariant Boolean properties of labelled graphs and their infimum quantiles (4).