OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1: Graph configurations, invariance, monotonicity, and nontriviality: Labelled configurations and the hypotheses imposed on their membership functions

Graph properties on the edge cube.

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 a graph event, the choice of vertex labels and the effect of adding edges are separate issues. Both enter the hypotheses of the main threshold statement.

The Definition

Definition 1. Let nn be a nonnegative integer and write [n]={1,…,n}[n]=\{1,\ldots,n\}. The edge set EnE_n of the complete graph on [n][n] is the family of unordered vertex pairs in (1): En={e⊆[n]:|e|=2}.E_n=\{e\subseteq[n]:|e|=2\}.(1)✦ A labelled graph xx on [n][n] is a Boolean edge configuration, an element of the space Ωn\Omega_n in (2); the value xe=1x_e=1 means that the edge ee is present: Ωn={0,1}En.\Omega_n=\{0,1\}^{E_n}.(2)✦

A graph x∈Ωnx\in\Omega_n is a subgraph of y∈Ωny\in\Omega_n, written x⊆yx\subseteq y, when the edge inclusion condition (3) holds: x⊆y⇔xe≤yefor every e∈En.x\subseteq y \quad\Longleftrightarrow\quad x_e\le y_e\quad\text{for every }e\in E_n.(3)✦

For a vertex permutation π:[n]→[n]\pi:[n]\to[n] and an edge e∈Ene\in E_n, the permuted edge πe∈En\pi e\in E_n is the image in (4): πe={π(v):v∈e}.\pi e=\{\pi(v):v\in e\}.(4)✦ The relabelled graph πx∈Ωn\pi x\in\Omega_n of x∈Ωnx\in\Omega_n is the configuration defined by (5): (πx)e=xπ−1e(e∈En).(\pi x)_e=x_{\pi^{-1}e}\qquad(e\in E_n).(5)✦

A Boolean membership function f:Ωn→{0,1}f:\Omega_n\to\{0,1\}, with f(x)=1f(x)=1 indicating membership, is invariant under vertex permutations when it satisfies (6): f(πx)=f(x)for every vertex permutation π and every x∈Ωn.f(\pi x)=f(x) \quad\text{for every vertex permutation }\pi\text{ and every }x\in\Omega_n.(6)✦ An increasing graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\} is a Boolean function whose accepted configurations are closed under edge inclusion, as in (7): x⊆y,f(x)=1⇒f(y)=1(x,y∈Ωn).x\subseteq y,\quad f(x)=1 \quad\Longrightarrow\quad f(y)=1 \qquad(x,y\in\Omega_n).(7)✦ A nontrivial graph property f:Ωn→{0,1}f:\Omega_n\to\{0,1\} is a Boolean function with both an accepted and a rejected configuration, as in (8): There exist x,y∈Ωn such that f(x)=1 and f(y)=0.\text{There exist }x,y\in\Omega_n\text{ such that }f(x)=1\text{ and }f(y)=0.(8)✦

In the paper, the result reads: for n≥2n\ge2, EnE_n is the family of two-element subsets of [n][n], a graph is a point of {0,1}En\{0,1\}^{E_n}, a graph property is a family invariant under all vertex permutations, increasing means that adding edges preserves membership, and nontrivial means that the family is neither empty nor the whole configuration space.

What Is Checked

The definitions range over every nonnegative integer nn and Boolean functions on Ωn\Omega_n, using the edge order (3) and the vertex relabelling (5).