Ramsey Number Bounds: How OpenAI’s Proof Found the Missing Logarithmic Power in r(5,t)

How long can a network avoid both five mutually connected vertices and a large group with no connections among them? For the Ramsey number $r(5,t)$, the power of $t$ had been settled, but the best bounds still differed by three powers of a logarithm. OpenAI’s September 24, 2026 preprint pins the logarithmic exponent down to three, giving $r(5,t)=t^4/(\log t)^{3+o(1)}$. The new Ramsey number bounds come from showing that a graph built from projective geometry can have much smaller independent sets than the previous analysis guaranteed. The proof turns any putative long independent sequence into a message shorter than its entropy permits. Read the original preprint.

1. Ramsey Number Bounds and the Problem r(5,t)

A clique is a set whose vertices are all pairwise adjacent. An independent set is a set with no edges between its vertices. In a network where edges represent mutual acquaintance, these are groups of mutual acquaintances and mutual strangers. The Ramsey number $r(5,t)$ is the least vertex count at which every simple graph contains a five-clique or an independent set of size $t$. The two targets can differ, making these off-diagonal Ramsey numbers.

For a lower bound, exhibit one graph that avoids both patterns. For an upper bound, show that every graph beyond a threshold must contain at least one. Theorem 1.1 improves the lower bound and recovers the classical upper bound.

2. What OpenAI’s Proof Establishes About r(5,t)

For every fixed $\varepsilon>0$ and all sufficiently large integers $t$, Theorem 1.1 gives the following bounds, where $C$ is an absolute positive constant and $\log$ denotes the natural logarithm.

The threshold for $t$ can depend on $\varepsilon$. Taking logarithms turns each power of $\log t$ into a multiple of $\log\log t$. Subtracting $\log r(5,t)$ from $4\log t$ removes the leading power of $t$, giving the limit that defines the sharp exponent.

Equivalently, the denominator is $(\log t)^{3+o(1)}$, with $o(1)$ denoting a quantity that tends to zero. A vanishing exponent error can still give an unbounded multiplicative factor. For example, an error of $1/\sqrt{\log\log t}$ gives the factor $e^{\sqrt{\log\log t}}$.

3. Why Earlier Bounds Left a Logarithmic Gap

Spencer’s local-lemma argument gave a Ramsey number lower bound on the scale $(t/\log t)^3$. Bohman and Keevash improved the logarithmic loss using the random clique-free process, reaching $t^3/(\log t)^{8/3}$ up to a constant. Both bounds still had a cubic power of $t$. Finite geometry supplied a different route. Mattheus and Verstraëte used a Hermitian unital for $r(4,t)$, and Bradač’s projective construction reached the fourth power for $r(5,t)$.

Bradač’s lower bound was proportional to $t^4/(\log t)^6$, while the classical Ramsey number upper bound had $(\log t)^3$ in the denominator. Their scales differed by a factor of $(\log t)^3$, ignoring constants. OpenAI’s Ramsey proof uses the ordered flag graph from Bradač’s work and improves the analysis of the independent sequences it can contain. Read Bradač’s off-diagonal Ramsey paper.

4. The Classical Upper Bound and the Three Logarithmic Gains

In a triangle-free graph, a vertex’s neighbors form an independent set. If no independent set reaches size $t$, every degree is below $t$. The paper proves a stronger independence estimate than the greedy bound by choosing a uniformly random independent set. Conditional on the choice outside a vertex’s closed neighborhood, the completions are either the vertex alone or any subset of its available neighbors. Averaging gives a logarithmic improvement over greedy selection and yields an upper bound for $r(3,t)$ proportional to $t^2/\log t$.

For a graph with no clique of size $s$, each neighborhood has no clique of size $s-1$. An edge’s common neighborhood has no clique of size $s-2$. This bounds the maximum degree and the number of triangles through any edge. The paper samples vertices independently, then deletes high-degree vertices and breaks remaining triangles. At high maximum degree, the resulting triangle-free induced graph retains enough vertices relative to its degree for the independence estimate to gain another logarithm. At low degree, greedy selection already suffices. The high-degree step adds a factor of order $t/\log t$ at each passage, giving $t^3/(\log t)^2$ for $r(4,t)$ and $t^4/(\log t)^3$ for $r(5,t)$.

5. How Projective Flags Rule Out Five-Cliques

In $\mathrm{PG}(4,q)$, a point is a one-dimensional subspace of the five-dimensional vector space over the field with $q$ elements. A projective hyperplane comes from a four-dimensional vector subspace. A flag consists of a point $a$ and a hyperplane $b$ that contains it. The notation $a\perp b$ means that incidence holds. Each vertex is a position in a stream of independently sampled uniform flags. Repeated flags are allowed because positions are the vertices. For positions $i<j$, the edge rule is

For a worked example, suppose the first two flags of a proposed clique have point representatives $e_1$ and $e_2$, the first two standard basis vectors. The first hyperplane contains $e_1$ and excludes $e_2$. The second hyperplane contains both and must exclude the third point, so that point lies outside their span. Continue in the same way. The fourth hyperplane contains the first four points and excludes the fifth. The five vectors are therefore linearly independent. Yet the fifth hyperplane must contain all five, which is impossible in a four-dimensional subspace.

6. Why a Selected Independent Sequence Has High Entropy

An independent set, read in stream order, gives a consistent tuple. If an earlier point lies on a later hyperplane, the reverse incidence must hold as well. Suppose every stream contains such a tuple of length $k$, and select one by a fixed rule. Here $k=\lfloor q(\log q)^{1+\eta}\rfloor$, with $\eta$ fixed and small. The selected tuple can be strongly biased because its selection depends on the entire stream.

The paper bounds the probability of each possible output without treating its coordinates as independent. A particular tuple must occur at some choice of positions. For $\ell$ prescribed positions the probability of a prescribed flag tuple is $M^{-\ell}$, with $M$ the total number of flags. A union bound over position sets limits the largest atom, and Shannon entropy is at least the negative logarithm of that atom. Write $\sigma=\log q$. The flag count $M$ scales as $q^7$, and the stream has $\lfloor q^4\sigma\rfloor$ positions. For retained lengths $\ell$ comparable to $k$, the logarithm of the number of position choices costs at most $\ell(3\sigma-\eta\log\sigma)+O(k)$. This leaves an excess of $\eta\ell\log\sigma$, up to an $O(k)$ loss, over $4\sigma\ell$ even after conditioning on events with probability bounded below.

7. Marking Scans, Conditional Dependence, and Collisions

The forward scan keeps, for each potential later hyperplane, the span of the dual vectors representing earlier marked hyperplanes whose points lie on it. Consistency forces the point of a new flag to lie in every hyperplane in that span. A flag is cheap when it belongs to one of the scan’s small, decoder-known classes. In one case, its hyperplane already belongs to many recorded spans. In the other, its point hits relatively few hyperplanes in a tracked rank class. An expensive flag escapes both descriptions, but adding it enlarges enough spans to shrink a tracked set by a fixed fraction of order $1/q$. Only $O(q\log q)$ expensive updates can occur.

A second scan reverses the order and exchanges points with hyperplanes. Recording the scan classes and the expensive flags leaves at most $Cq^4$ joint options per remaining slot and supplies separate caps on its two endpoints. The proof then partitions windows into representative blocks and middle targets. After revealing older rounds of representatives, it selects a fresh round before reading its values. An entropy chain rule bounds the remaining mutual information between representatives and targets.

Under the actual joint law, an incidence that would create an edge is forbidden. Under the product of the conditional marginals, its probability is bounded by mutual information. Incidences in both directions require an extra geometric argument. Where they can persist, the proof charges pairs lying in rectangles formed by a dual subspace and its annihilator. A uniform bound on stream occupancy makes these collisions rare enough. Nearly uniform levels of the endpoint distributions then supply large, sparse supports for the next step.

8. The Sparse Incidence Description Theorem

In projective dimension $d$, a uniformly random point and hyperplane are incident with probability close to $1/q$. Theorem 4.1 concerns hidden sets $S$ of points and $T$ of hyperplanes with density far below that scale, yet with a product of sizes at least $q^{d+1}e^{-b}$ for a controlled loss parameter $b$. The decoder knows enclosing sets, while the encoder knows the hidden sets. A short public-table message describes a set $W$ that contains a constant fraction of the smaller hidden support and is at most $e^{CP}$ times its size. Here $P$ is the theorem’s sampling parameter, with $P=o(\log q)$.

A small support can be sent directly by its rank among subsets of the known enclosure. For larger supports, the proof looks for concentrations on planes or hyperplanes. A large cell lets it restrict points and hyperplanes to a proper flat and invoke the description theorem in lower dimension. Hyperplanes can have the same restriction, so the proof groups restrictions by the number of original hyperplanes that lift them.

When the cells are small, the encoder sends the flat lists and counts instead. Polynomial bounds on rich lines and estimates for overlapping hyperplanes control how often several hyperplanes through the same query point share many training points. This controls the dependence that remains when those hyperplanes are tested against the same random batches.

9. How the Poisson Score Detects Sparse Structure

In the small-cell case, the predictor draws independent batches from the training set with Poisson-distributed sizes. This makes sample counts independent across points and batches. Hyperplanes can still share samples, so their emptiness events can be correlated. The score examines hyperplanes through the query point, using empty-batch indicators and a centering term adjusted for its assigned cells. The centering reduces the contribution from typical hyperplanes. A hyperplane is exceptional if its training incidence departs sufficiently from the expected mass, either across the whole training set or within a recorded cell. The exceptional hyperplanes empty in every batch supply the main signal.

Sparse incidence provides many candidates for those empty exceptional hyperplanes. On successful rows, incidence variance separates the typically low training counts from higher ambient counts. The proof controls score errors with a second-moment estimate on training points and a higher-moment estimate in the ambient space. It accepts sampled points automatically and uses a score threshold for the rest.

A public table proposes samples from the known enclosure. The encoder searches for a row entirely inside the training set that gives both enough capture and a small output. It sends the row index, the cell data, and the number of empty exceptional hyperplanes. The decoder can evaluate the score without knowing which hyperplanes are exceptional. The proof pays for the probability of finding a successful row, which can be biased by that search.

10. How Entropy Compression Closes the Gap

The predictor’s output provides a manageable domain for proposing a fresh sample from one hidden support. The first incidence test keeps opposite endpoints hit fewer than $0.2h/q$ times by a row of $h$ samples. It trims the opposite domain while retaining at least 90% of its hidden support on success. A second test samples from that retained support to trim the original side. The proof bounds rejection probabilities before conditioning on any later test or target survival.

Each pivot in a balanced tree is the middle window of its interval. Its own middle targets use both new caps. A cap is the intersection of an inherited domain with a fresh test’s passing set. Earlier windows inherit the new point cap because their points face the pivot’s later hyperplane representative. Later windows inherit the new hyperplane cap because their hyperplanes face the pivot’s earlier point representative. Tests are built before checking which actual middle targets they retain. This order allows the proof to sum expected losses along tree paths under the available conditional laws.

At a successful pivot, the caps bound how many flags the decoder must distinguish. The tree also controls the cost of specifying all the caps. Across each level, the inherited domain costs split between the two children, with a controlled additional cost per successful node. A constant-probability extraction retains a deterministic length $\ell$ comparable to $k$ and reduces the combined budget for metadata and slot sizes. A finite number of stages suffices for each fixed $\eta$. A final marking pass then gives two incompatible estimates for the entropy of the retained tuple $F$.

The $O(k)$ terms are bounded by constant multiples of $k$. The excess grows faster because $\ell$ stays comparable to $k$ and $\log\sigma$ diverges. Thus some stream avoids a consistent tuple of length $k$.

11. From Prime Fields to the Sharp Exponent

The construction gives $\lfloor q^4\log q\rfloor$ vertices and independence number below $\lfloor q(\log q)^{1+\eta}\rfloor$. Bertrand’s postulate supplies a prime within a constant factor of $t/[4(\log t)^{1+\eta}]$ for every sufficiently large integer $t$. The graph then has no independent set of size $t$. Substituting the scale of $q$ into the vertex count gives a lower bound proportional to $t^4/(\log t)^{3+4\eta}$. Choosing $4\eta<\varepsilon$ lets the extra logarithmic power absorb the constant, yielding the theorem for all sufficiently large $t$.

The paper leaves open whether a positive constant times $t^4/(\log t)^3$ is also a lower bound. Exact small values such as $R(5,5)$ are a separate question. The description theorem bounds message length, and the encoder’s search may run through exponentially many proposals. OpenAI’s release announcement gives the publication context, while the Lean scope note records the formalized inequalities and the exponent limit along the natural numbers. The Lean theorem entry point assembles the bounds and the limit.

The sharper Ramsey number bounds show what changed when the proof accounted for the information carried by a selected independent sequence. The geometry rules out five-cliques, and the compression argument makes long independent sequences impossible to guarantee. Explore more Binary Verse AI research on graph coloring and hardness, crossing numbers of complete graphs, and the limits of Weisfeiler–Leman graph refinement. For sampling and formalization, see switch-chain mixing, exact contingency-table sampling, and the Lean formalization of Fermat’s Last Theorem.