Sharp logarithmic exponents for off-diagonal Ramsey numbers

Source and verification

This article explains family 170 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Off-diagonal Ramsey numbers

The Ramsey number $r(s,t)$ is the least integer $N$ such that every graph on $N$ vertices contains either a clique of size $s$ or an independent set of size $t$. Equivalently, every red-blue coloring of the edges of $K_N$ contains a red $K_s$ or a blue $K_t$.

Here $s$ is fixed while $t$ tends to infinity. This is the off-diagonal regime. The two manuscripts address $s=5$ and every fixed $s\ge 6$, respectively.

Manuscript claims

For every fixed integer $s\ge 5$ and every $\epsilon >0$, for all sufficiently large $t$,

$$\begin{array}{c}r(s,t)\ge \frac{t^{s-1}}{(\log t{)}^{s-2+\epsilon }},\\ r(s,t)\le C_s\frac{t^{s-1}}{(\log t{)}^{s-2}}.\end{array}$$

The first paper treats $s=5$; its companion treats fixed $s\ge 6$. (OpenAI, 2026) (OpenAI, 2026a)

This determines the logarithmic exponent:

$$\frac{\log (t^{s-1}/r(s,t))}{\log \log t}⟶s-2.$$

It does not establish a constant-factor asymptotic $r(s,t)={\Theta }_s(t^{s-1}/(\log t{)}^{s-2})$. The lower bound still permits a factor $(\log t{)}^{\epsilon }$. The threshold may depend on both $s$ and $\epsilon$, and the conclusion is not uniform when $s$ grows with $t$.

🏷️ Finite geometry supplies clique-free graphs

Set $d=s-1$. In projective $d$-space over a field with $q$ elements, a flag consists of a point $a$ lying in a hyperplane $b$. Coordinates represent the incidence condition by $a\cdot b=0$.

Sample a sequence of flags $(a_i,b_i)$. For positions $i<j$, insert an edge when

$$a_i\cdot b_j=0,a_j\cdot b_i\ne 0.$$

Although this rule uses the order of positions, the resulting edge is undirected. The asymmetry in the two incidence conditions is the feature that excludes large cliques.

Indeed, suppose $d+1$ positions form a clique, listed in increasing order. The hyperplane $b_j$ contains $a_1,\dots ,a_j$ but does not contain $a_{j+1}$. Consequently $a_{j+1}$ is outside the linear span of the preceding point representatives. Induction gives $d+1$ linearly independent vectors. Yet all of them lie in the last hyperplane $b_{d+1}$, a $d$-dimensional vector subspace of the $(d+1)$-dimensional coordinate space. This is impossible.

The purpose of the incidence rule is to enforce clique-freeness deterministically, leaving randomness to control independent sets. The projective linear-algebra lemma is part of the construction; a generic random graph would not retain this exact exclusion.

🏷️ Converting the geometric parameters

The construction uses roughly

$$N=q^d\log q$$

sampled positions and claims that its independence number is less than $q(\log q{)}^{1+\eta }$, for any fixed $\eta >0$ once $q$ is large enough.

Writing $t$ at the latter scale gives

$$N\asymp \frac{t^d}{(\log t{)}^{d-1+d\eta }}.$$

Choosing $\eta <\epsilon /d$ leaves enough room to obtain the desired lower bound with exponent $d-1+\epsilon =s-2+\epsilon$, after the source’s parameter selection and rounding. This calculation explains exactly why the factor $\log q$ in the vertex count matters.

🏷️ Independent sets selected from random data

An independent set found after the flags are exposed is not an independently sampled sequence of flags. Conditioning on its existence biases the data. The proof therefore measures the information needed to describe a putative independent sequence.

With $\sigma =\log q$ and a proposed independent-set size $k$ near $q{\sigma }^{1+\eta }$, a selected portion of length $\ell$ retains entropy at a scale

$$d\sigma \ell +\eta \ell \log \sigma -O(k).$$

Entropy here is the expected logarithm of the reciprocal probability of the data. If the independence constraints permit a shorter description than this lower bound, the alleged independent set cannot exist with the required probability.

A naive description marks exceptional flags one at a time. Its cost can be of order $q{\log }^{2}q$, too large to fit within the useful $\eta k\log \log q$ surplus. The manuscript replaces it with sparse pair descriptions and balanced trees that record where allowed geometric domains shrink. Conditional message lengths are charged only when genuinely new information is sent.

🏷️ Geometry and decoding

Independent Poisson scores organize the random choices in finite geometric domains. Rich lines and planes have special treatment. In higher fixed dimensions, repeated projection separates lower-dimensional concentrations from configurations requiring two-row descriptions of larger rank. This is the main additional work in passing from $s=5$ to all fixed $s\ge 6$.

The decoder is required to reconstruct the relevant data using the transmitted message and public tables. It cannot silently use hidden information from an earlier conditioning step. With that restriction enforced, the upper description bound has the form $d\sigma \ell +O(k)$, contradicting the extra $\eta \ell \log \sigma$ term.

Public random tables can be fixed after averaging. This gives an existence proof for suitable graphs; it does not by itself give an efficient algorithm for finding them. The sharp logarithmic exponent depends on the quantitative message accounting, not merely on the clique-free finite-geometric template.

🏷️ Key steps and proof outlines

A second-moment incidence identity controls geometric domains

Write $Q_j=1+q+\cdots +q^j$, and let $M_d$ be the point-hyperplane incidence matrix of projective $d$-space. Every point belongs to $Q_{d-1}$ hyperplanes; every two distinct points belong to $Q_{d-2}$. Therefore

$$M_d{M}_d^{\mathsf{T}}=q^{d-1}I+Q_{d-2}11^{\mathsf{T}}.$$

On vectors orthogonal to constants, its squared operator norm is exactly $q^{d-1}$. If $p_d=Q_{d-1}/Q_d$, the resulting mixing estimate is

$$|e(A,B)-p_d|A||B||\le q^{(d-1)/2}\sqrt{|A||B|}.$$

In particular, a rectangle $A\times B$ with incidence density $o(1/q)$ must have $|A||B|=O(q^{d+1})$. The proof compares its missing main term, of order $|A||B|/q$, with the square-root error. This gives an explicit limit on domains that can avoid incidences, and the weighted version also controls nonuniform conditional laws. (OpenAI, 2026b)

Selection does not destroy the entropy lower bound

Let $\sigma =\log q$, $N\asymp q^d\sigma$, and $k\asymp q{\sigma }^{1+\eta }$. There are $M=Q_d{Q}_{d-1}$ possible flags, with $\log M=(2d-1)\sigma +O(1/q)$. Suppose any rule extracts an ordered tuple $F$ of deterministic length $\ell =\Theta (k)$ from the random stream. The rule may inspect the entire stream and use auxiliary randomness.

If the stream law is bounded above by $C_0$ times the independent uniform law, then for every specified tuple $f$,

$$\mathbb{P}(F=f)\le \frac{2C_0\left(\genfrac{}{}{0ex}{}{N}{\ell }\right)}{M^{\ell }}.$$

Proof outline. The tuple must appear at some $\ell$ positions, in the original order or the allowed reversed-and-swapped order. For fixed positions its independent-stream probability is $M^{-\ell }$, including when flag values repeat. A union bound over positions proves the atom estimate without claiming the selected tuple is independent. Since entropy is at least minus the logarithm of the largest atom,

$$H(F)\ge \ell \log M-\ell \log (eN/\ell )-O(1)=d\sigma \ell +\eta \ell \log \sigma -O(k).$$

The $\eta \ell \log \sigma$ surplus is the resource the compression proof must contradict. Conditioning on an event of probability bounded below only changes $C_0$ by a constant factor, so a fixed number of such conditionings preserves the estimate.

Replace descriptions rather than accumulating them

For fixed $d\ge 5$, the companion makes the iteration quantitative. A context has entropy budget $\Lambda$ and a geometric domain budget $\Delta$. With $\beta =\eta /10^7$, define

$$D={\sigma }^{\beta }(1+\Lambda /k+\Delta {\sigma }^{-\eta }).$$

The geometry, prediction, marking, and compression lemmas produce a new context whose parameter satisfies

$$D_{\mathrm{new}}\le {\sigma }^{2\beta }+D{\sigma }^{-\eta /4}.$$

This is a contraction of the excess description cost, down to a small floor. Starting with $D_0\le \sigma$, after $T=\lceil 8/\eta \rceil$ stages,

$$D_T\le {\sigma }^{1-T\eta /4}+\frac{{\sigma }^{2\beta }}{1-{\sigma }^{-\eta /4}}\le 2{\sigma }^{2\beta }.$$

One further stage gives ${\Lambda }_{\ast }/k=o(1)$ and ${\Delta }_{\ast }q\sigma /k=o(1)$. The final marking scan consequently describes the retained tuple using entropy at most $d\sigma {\ell }_{\ast }+O(k)$, contradicting the lower bound because ${\ell }_{\ast }=\Theta (k)$ and $\log \sigma \to \infty$. (OpenAI, 2026a)

The decoder condition matters to this recurrence. The new context replaces the old one, and decoding uses only the new message and fixed public tables. Keeping hidden access to earlier contexts would invalidate its claimed entropy cost. At each stage, tables are fixed by averaging before conditioning on success, and the retained tuple has a prescribed deterministic length. Since the number of stages is fixed in advance, all retained proportions and stream-domination factors remain constants independent of $q$.

Close the quantifiers over all integers

The construction gives clique-free graphs at prime scales. The source uses a prime in a fixed-ratio interval to choose $q$ comparable with $t/(\log t{)}^{1+\eta }$. Then $N\asymp q^d\log q$ has the required size and the independence threshold is below $t$. Choosing $d\eta <\epsilon$ absorbs fixed constants into the remaining logarithmic margin. This supplies every sufficiently large integer $t$, rather than only a prime-indexed subsequence. The incidence calculation and entropy closure above explain the endpoints of the proof; the sparse description and higher-dimensional geometric compression are the research mechanisms connecting them.

See Also

• Hypercube Ramsey numbers studies a growing sparse target rather than a fixed clique.
• Ryser covering counterexamples also uses finite planes, but modifies their partitions to increase a hypergraph covering number.

🏷️ Manuscripts and verification scope

• The sharp logarithmic exponent of $r(5,t)$ — pinned manuscript and companion source.
• Sharp Logarithmic Exponents for Fixed Off-Diagonal Ramsey Numbers — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page separately selects the all-natural-t logarithmic exponent limits for s = 5 and for every fixed s at least 6, retaining epsilon-dependent thresholds. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Sharp Logarithmic Exponents for Fixed Off-Diagonal Ramsey Numbers.

🐻  OpenAI 2026b. The sharp logarithmic exponent of r(5,t).