OctoInformBeta

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

§1 (setting): homomorphism and edge densities, the pattern H: HH is the incidence graph of 22 triples on 13 points, and t(F,G)t(F,G) the share of maps V(F)→V(G)V(F)\to V(G) preserving every edge

The incidence pattern HH and homomorphism densities.

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

Take the thirteen points of [13][13], where [n]={0,1,…,n−1}[n]=\{0,1,\dots,n-1\}, and a fixed list of 22 triples of them, the faces. The pattern HH is the point-face incidence graph of this configuration, a bipartite graph with 35 vertices and 66 edges.✦ A host graph GG is measured against it by the homomorphism density t(H,G)t(H,G) and the edge density p(G)p(G), the two quantities that Sidorenko’s conjecture compares for a bipartite pattern.

The Definition

The library lists the faces explicitly and defines the homomorphism count and both densities for arbitrary finite simple graphs FF and GG, so that t(H,G)t(H,G) is the case F=HF=H.

Definition 1. The faces F0,…,F21F_0,\dots,F_{21} are the 22 three-element subsets of the point set [13][13] given by 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}(1)✦

The vertex set of the pattern HH is the disjoint union of the points and the faces, with a vertex ii for each point ii and a vertex jj for each face FjF_j: V(H)=[13]⊔[22].V(H) = [13] \sqcup [22].(2)✦

The incidence relation ∼\sim on V(H)V(H) holds between a point ii and a face jj, in either order, exactly when the point lies in the face, and never between two points or two faces: i∼j⇔j∼i⇔i∈Fj(i∈[13],j∈[22]).i \sim j \iff j \sim i \iff i \in F_j \qquad (i\in[13],\ j\in[22]).(3)✦

The pattern graph HH is the simple graph on V(H)V(H) whose edges are the incident pairs, E(H)={{u,v}⊆V(H):u∼v}.E(H) = \bigl\{\{u,v\} \subseteq V(H) : u \sim v\bigr\}.(4)✦

For finite simple graphs FF and GG, the homomorphism count hom⁡(F,G)\hom(F,G) is the number of maps V(F)→V(G)V(F)\to V(G), injective or not, that send every edge of FF to an edge of GG: hom⁡(F,G)=|{f:V(F)→V(G):f(u)f(v)∈E(G) for every uv∈E(F)}|.\hom(F,G) = \bigl|\{\, f\colon V(F)\to V(G) : f(u)f(v)\in E(G) \text{ for every } uv\in E(F) \,\}\bigr|.(5)✦

For finite simple graphs FF and GG, the homomorphism density of FF in GG is the real number t(F,G)=hom⁡(F,G)|V(G)||V(F)|.t(F,G) = \frac{\hom(F,G)}{|V(G)|^{|V(F)|}}.(6)✦

The edge density of a finite simple graph GG is the real number p(G)=2|E(G)||V(G)|2.p(G) = \frac{2\,|E(G)|}{|V(G)|^{2}}.(7)✦

In the paper, the result reads: for finite simple graphs HH and GG (the page’s FF and GG), t(H,G)=hom⁡(H,G)/|V(G)||V(H)|t(H,G)=\hom(H,G)/|V(G)|^{|V(H)|} with hom⁡(H,G)\hom(H,G) counting all edge-preserving maps, and p(G)=2|E(G)|/|V(G)|2p(G)=2|E(G)|/|V(G)|^2; the pattern HH is the incidence graph of the 22 triples of Table 1, the page’s faces F0,…,F21F_0,\dots,F_{21}.

What Is Checked

The pattern HH is stated over the faces (1) and the incidence relation (3) on the vertex set (2), and the count (5) and the densities (6) and (7) over an arbitrary pair of finite simple graphs FF and GG, the densities taking real values.