OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.1 [Main theorem]: For the incidence graph HH of 22 triples on 13 points, some graph GG with an edge has t(H,G)<p(G)66t(H,G) < p(G)^{66}

A bipartite graph with 66 edges violates Sidorenko’s conjecture.

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

For finite simple graphs FF and GG, a homomorphism from FF to GG is a map f:V(F)→V(G)f\colon V(F)\to V(G), injective or not, that sends every edge uvuv of FF to an edge f(u)f(v)f(u)f(v) of GG, and hom⁡(F,G)\hom(F,G) is the number of homomorphisms from FF to GG.✦ The homomorphism density t(F,G)t(F,G) of FF in GG and the edge density p(G)p(G) of GG are the real numbers t(F,G)=hom⁡(F,G)|V(G)||V(F)|,p(G)=2|E(G)||V(G)|2.t(F,G)=\frac{\hom(F,G)}{|V(G)|^{|V(F)|}},\qquad p(G)=\frac{2\,|E(G)|}{|V(G)|^{2}}.(1)

The item concerns one bipartite graph HH with 35 vertices and 66 edges.

The counterexample statement CE(H)\mathrm{CE}(H) is the assertion that for some positive integer nn there is a simple graph GG on the vertex set {0,…,n−1}\{0,\dots,n-1\} with at least one edge and t(H,G)<p(G)66t(H,G)<p(G)^{66}.✦

The Graph HH

The faces F0,…,F21F_0,\dots,F_{21} are the following twenty-two three-element subsets of the point set {0,1,…,12}\{0,1,\dots,12\}: F0={0,1,3},F1={0,1,9},F2={0,2,3},F3={0,2,9},F4={1,3,10},F5={1,7,10},F6={1,7,12},F7={1,9,12},F8={2,3,4},F9={2,4,9},F10={3,4,11},F11={3,10,11},F12={4,8,9},F13={4,8,11},F14={5,6,7},F15={5,6,11},F16={5,7,10},F17={5,10,11},F18={6,7,12},F19={6,8,11},F20={6,8,12},F21={8,9,12}.\begin{array}{llll} F_{0}=\{0,1,3\}, & F_{1}=\{0,1,9\}, & F_{2}=\{0,2,3\}, & F_{3}=\{0,2,9\},\\ F_{4}=\{1,3,10\}, & F_{5}=\{1,7,10\}, & F_{6}=\{1,7,12\}, & F_{7}=\{1,9,12\},\\ F_{8}=\{2,3,4\}, & F_{9}=\{2,4,9\}, & F_{10}=\{3,4,11\}, & F_{11}=\{3,10,11\},\\ F_{12}=\{4,8,9\}, & F_{13}=\{4,8,11\}, & F_{14}=\{5,6,7\}, & F_{15}=\{5,6,11\},\\ F_{16}=\{5,7,10\}, & F_{17}=\{5,10,11\}, & F_{18}=\{6,7,12\}, & F_{19}=\{6,8,11\},\\ F_{20}=\{6,8,12\}, & F_{21}=\{8,9,12\}. & & \end{array}(2)✦

The incidence graph HH is the bipartite graph whose vertices are the thirteen points and the twenty-two faces, a point ii being adjacent to a face FjF_j exactly when i∈Fji\in F_j.✦

A corner of HH is a pair (j,s)(j,s) of a face index j∈{0,…,21}j\in\{0,\dots,21\} and a slot s∈{0,1,2}s\in\{0,1,2\}.✦ The point c(j,s)c(j,s) of a corner (j,s)(j,s) of HH is the entry in slot ss of the list of the points of FjF_j in increasing order.✦ The 66 corners are the 66 edges of HH, the corner (j,s)(j,s) joining c(j,s)c(j,s) to FjF_j.

Kernels on Finite Probability Spaces

A probability law pp on a finite set AA is a function p:A→[0,∞)p\colon A\to[0,\infty) whose values sum to 11.✦ The expectation 𝔼a∼pf(a)\mathbb{E}_{a\sim p}f(a) of a function f:A→ℝf\colon A\to\mathbb{R} under pp is the number ∑a∈Ap(a)f(a)\sum_{a\in A}p(a)f(a).✦ The product ⨂i∈Ipi\bigotimes_{i\in I}p_i of probability laws pip_i on AA, indexed by a finite set II, is the probability law on AIA^{I} that gives xx the weight ∏i∈Ipi(xi)\prod_{i\in I}p_i(x_i); when every pip_i is pp and I={0,…,m−1}I=\{0,\dots,m-1\}, it is written p⊗mp^{\otimes m}.✦

For probability laws π\pi on a finite set XX and ν\nu on a finite set YY and a function W:X×Y→ℝW\colon X\times Y\to\mathbb{R}, the kernel mean of WW is the number 𝔼π,νW=𝔼x∼π𝔼y∼νW(x,y)\mathbb{E}_{\pi,\nu}W=\mathbb{E}_{x\sim\pi}\,\mathbb{E}_{y\sim\nu}\,W(x,y)✦, and the bipartite moment of WW is the number tπ,ν(H,W)=𝔼x∼π⊗13𝔼y∼ν⊗22∏j=021∏s=02W(xc(j,s),yj),t_{\pi,\nu}(H,W)=\mathbb{E}_{x\sim\pi^{\otimes 13}}\;\mathbb{E}_{y\sim\nu^{\otimes 22}} \prod_{j=0}^{21}\prod_{s=0}^{2}W\bigl(x_{c(j,s)},\,y_j\bigr),(3)✦ with x=(x0,…,x12)x=(x_0,\dots,x_{12}) indexed by the points and y=(y0,…,y21)y=(y_0,\dots,y_{21}) by the faces, one factor for each corner.

A symmetric counter kernel is a triple (Ω,π,U)(\Omega,\pi,U) of a nonempty finite set Ω\Omega, a probability law π\pi on Ω\Omega and a function U:Ω×Ω→[0,1]U\colon\Omega\times\Omega\to[0,1] with U(x,y)=U(y,x)U(x,y)=U(y,x) for all x,y∈Ωx,y\in\Omega, such that 𝔼π,πU>0andtπ,π(H,U)<(𝔼π,πU)66.\mathbb{E}_{\pi,\pi}U>0 \qquad\text{and}\qquad t_{\pi,\pi}(H,U)<\bigl(\mathbb{E}_{\pi,\pi}U\bigr)^{66}.(4)✦

The Claim

Theorem 1. Let HH be the incidence graph of the faces (2).

  1. For some positive integer nn and some simple graph GG on {0,…,n−1}\{0,\dots,n-1\} with at least one edge, as in the counterexample statement, t(H,G)<p(G)66.t(H,G)<p(G)^{66}.(5)✦

  2. The counterexample statement holds: CE(H).\mathrm{CE}(H).(6)✦

  3. Every symmetric counter kernel gives the counterexample statement: (Ω,π,U)a symmetric counter kernel⇒CE(H).(\Omega,\pi,U)\ \text{a symmetric counter kernel}\;\Longrightarrow\;\mathrm{CE}(H).(7)✦

What Is Checked

Claims (5) and (6) are stated over the incidence graph HH of the faces (2) and over simple graphs GG on {0,…,n−1}\{0,\dots,n-1\}, with the homomorphism density and the edge density (1). Claim (7) is stated over symmetric counter kernels (4), whose kernel mean and bipartite moment (3) are expectations under a probability law on a finite set and under its products.

The library proves that the product of probability laws on a finite set is again a probability law, its weights ∏i∈Ipi(xi)\prod_{i\in I}p_i(x_i) being nonnegative and summing to 11, and that adjacency in HH is symmetric and irreflexive.