The logarithmic scale of off-diagonal Ramsey numbers

← All digests

Family 170 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

How large can a network be if it contains neither a small group whose members are all connected nor a large group with no connections at all? Ramsey theory says that such a network cannot grow indefinitely. The difficult part is finding the right scale of the limit.

For fixed integers $s$ and $t$, the Ramsey number $r(s,t)$ is the smallest number of vertices forcing either a complete subgraph on $s$ vertices or an independent set of size $t$. In an independent set, no two vertices are joined. Here $s$ stays fixed while $t$ tends to infinity: this is the off-diagonal problem.

The two manuscripts in this family concern every fixed $s\geq5$. They claim to identify the exponent of the logarithm in the asymptotic growth of $r(s,t)$. This is finer information than its main power of $t$, which earlier work had already determined. It still leaves room between upper and lower bounds at smaller scales.

2. Background and essential definitions

A graph here is finite, undirected and simple: there are no loops or repeated edges. Write $K_s$ for the graph with every possible edge on $s$ vertices. A graph is $K_s$-free if it contains no copy of that graph. Its independence number $\alpha(G)$ is the largest size of an independent set.

To prove a lower bound on a Ramsey number, one constructs a graph that avoids both alternatives. If a graph $G$ has $N$ vertices, contains no $K_s$, and satisfies $\alpha(G)<t$, then

$$r(s,t)>N.$$

An upper bound requires showing that every sufficiently large graph has one of the two structures. Equivalently, color each pair of vertices red when it is an edge and blue when it is not. Then $r(s,t)$ forces a red $K_s$ or a blue $K_t$.

Throughout, $\log$ denotes the natural logarithm. Constants may depend on the fixed integer $s$. The notation $o(1)$ means a quantity tending to zero as $t$ grows with $s$ held fixed. An exponent $a+o(1)$ is a statement about a limiting exponent; it does not generally identify a constant multiplying the whole expression.

For example, a factor $\log\log t$ is smaller than every fixed positive power of $\log t$, but it still grows without bound. Such a factor can be hidden inside a logarithmic exponent error tending to zero. This distinction is central to the result.

3. Development history and previous partial results

Ramsey’s 1930 theorem established the fundamental finiteness phenomenon. The elementary recursion developed in early Ramsey theory gives the binomial upper bound

$$r(s,t)\leq\binom{s+t-2}{s-1}.$$

For fixed $s$, this is of order at most $t^{s-1}$. It says nothing about the logarithmic improvement now expected at that scale.

Ajtai, Komlós and Szemerédi obtained upper bounds of the form

$$r(s,t)\leq C_s\frac{t^{s-1}}{(\log t)^{s-2}},$$

with later work sharpening their constants. On the construction side, the triangle case became a benchmark: Kim’s 1995 paper established the matching order $r(3,t)=\Theta(t^2/\log t)$. Here $\Theta$ means upper and lower bounds differing by at most constant factors.

Larger fixed cliques were much harder. Probabilistic constructions, including the local lemma and random processes that avoid creating a forbidden clique, supplied important lower bounds without reaching the upper bound’s polynomial exponent in general. Mattheus and Verstraëte’s work on $r(4,t)$ used finite geometry to obtain a lower bound of order $t^3/(\log t)^4$, bringing that case within logarithmic factors of the upper bound.

The immediate predecessor for this family is Bradač’s 2026 manuscript. For every fixed $s\geq3$, it gives a lower bound of the form

$$r(s,t)\geq c_s\frac{t^{s-1}}{(\log t)^{2s-4}}.$$

Thus the power $s-1$ of $t$ was already sharp. The remaining gap relevant here was between logarithmic exponents $2s-4$ and $s-2$. The present manuscripts claim to close that exponent gap for $s\geq5$. They build on an older line of constructions from ordered incidence relations, together with methods that show there are too few descriptions of a hypothetical large independent set.

4. What the new manuscripts claim

The common conclusion

Manuscript M1 treats $s=5$. Manuscript M2 treats every fixed $s\geq6$. Together they claim that for each fixed integer $s\geq5$ and each real $\varepsilon>0$, all sufficiently large $t$ satisfy

$$\frac{t^{s-1}}{(\log t)^{s-2+\varepsilon}} \leq r(s,t) \leq C_s\frac{t^{s-1}}{(\log t)^{s-2}}.$$

The threshold for “sufficiently large” may depend on both $s$ and $\varepsilon$. The upper bound is classical; the new claim is the nearly matching lower bound. An equivalent compact formulation is

$$r(s,t)=\frac{t^{s-1}}{(\log t)^{s-2+o(1)}}.$$

More explicitly, the exponent statement reads

$$\lim_{t\to\infty} \frac{(s-1)\log t-\log r(s,t)}{\log\log t}=s-2.$$

For $s=5$, the manuscript therefore replaces the earlier logarithmic denominator exponent six by an exponent arbitrarily close to three. The gain grows without bound with $t$, even though it does not change the main polynomial power.

The construction behind the bound

Set $d=s-1$. A central construction in the papers uses a large prime $q$ and a fixed small parameter $\eta>0$. It claims graphs with approximately

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

vertices, no $K_{d+1}$, and independence number smaller than approximately

$$q(\log q)^{1+\eta}.$$

The precise statements use integer parts. Choosing $\eta$ sufficiently small in terms of the requested $\varepsilon$, and translating between $q$ and the desired independent-set size, yields the Ramsey bound. The result is stated for all sufficiently large integer $t$, rather than only a subsequence indexed by primes.

5. Why the advance matters

Importance: 4/5. Off-diagonal Ramsey numbers are central measures of how much disorder a graph can sustain. Determining a logarithmic exponent for every fixed clique size in an infinite range is a major quantitative advance, especially after the polynomial exponents have been identified.

The scale deserves some perspective. Two bounds with the same power of $t$ can still differ by an arbitrarily large factor. Replacing a denominator $(\log t)^{2s-4}$ by $(\log t)^{s-2+\varepsilon}$ permits substantially larger graphs avoiding both forbidden structures. It narrows the uncertainty to effects smaller than any fixed positive logarithmic power.

The methodological interest is also broad. Finite geometry ensures that a clique cannot form; an information argument then limits independent sets. These two tasks pull in opposite directions, and the construction coordinates them without relying on a completely unconstrained random graph. The rating reflects both the central problem and this combination of ideas, while leaving room for stronger constant-factor or leading-constant results.

6. The main idea

Make cliques impossible by linear algebra

Work over the finite field $\mathbb F_q$, where arithmetic is performed modulo the prime $q$. A projective point represents a one-dimensional subspace of $\mathbb F_q^{d+1}$. A projective hyperplane is specified by a nonzero linear equation. A flag is an incident point–hyperplane pair: the point lies in the hyperplane.

Sample a sequence of flags $(a_i,b_i)$. Each position becomes a graph vertex, even if two positions receive the same flag. For $i<j$, place an edge when $a_i$ lies in $b_j$ but $a_j$ does not lie in $b_i$.

This asymmetric rule uses the order of the positions, although the resulting graph has ordinary undirected edges. The incidence pattern required by a clique forces an incompatible arrangement of independent vectors and hyperplanes. The paper uses this to exclude $K_{d+1}$ deterministically: every sampled sequence has the required clique restriction.

Make independent sets too expensive to describe

It remains to show that some sequence has no large independent set. An independent subsequence must obey many restrictions on its point–hyperplane incidences. Those restrictions ought to make it unusually structured, but counting all possible subsequences directly loses too much.

The manuscripts use entropy, a numerical measure of uncertainty. Suppose a rule selects a long independent subsequence whenever one exists. There are two competing ways to estimate the information needed to specify the selected flags. Random sampling supplies a lower bound on that information. Geometric restrictions supply a compressed description.

Selection changes the distribution: the chosen flags are not simply independent uniform samples. The argument must account for the information lost by selecting them. Ignoring this bias would make the compression comparison unreliable even if each individual geometric estimate were strong.

The compression repeatedly locates parts of the sequence whose allowable point and hyperplane sets have unusually few incidences. Short records then restrict where many flags could lie. A hierarchy of these records reduces the total description length; the construction replaces earlier records where needed instead of paying for every intermediate stage forever.

Higher dimensions introduce additional geometric possibilities. M2 develops projection and polynomial tools to control them, extending the strategy beyond the $s=5$ case. The intended contradiction is that a selected independent sequence would retain more information than its compressed description can carry. Consequently, some sampled graph has no independent set of the prohibited size.

7. Scope, limitations, and open questions

The statements hold for each fixed $s\geq5$. They do not give uniform estimates when the forbidden clique size grows with $t$. Nor do these two manuscripts settle the corresponding logarithmic question for $s=4$.

The lower bound contains an arbitrary fixed exponent loss $\varepsilon$. One cannot set $\varepsilon=0$ in the quantifiers: the threshold is allowed to worsen as $\varepsilon$ decreases. The conclusion therefore does not establish

$$r(s,t)=\Theta\!\left(\frac{t^{s-1}}{(\log t)^{s-2}}\right).$$

A matching constant-factor lower bound, and then a leading asymptotic constant, are stronger targets. The construction is also an existence argument using random flags and information estimates; the headline theorem does not itself provide a practical algorithm for producing optimal Ramsey graphs at a chosen size.

Finally, this family concerns ordinary graphs with a fixed forbidden clique. Related questions for hypergraphs, several colors, or different forbidden subgraphs require their own statements. The logarithmic precision achieved here should be understood within these specific parameters.

8. Sources and further reading

M1 gives the $r(5,t)$ construction and its entropy analysis. M2 develops the higher-dimensional extension and states the result for all fixed $s\geq6$. Their introductions explain the earlier ordered-incidence constructions and the remaining logarithmic gap.

For primary historical context, see Ramsey’s original paper, Kim on triangle-free Ramsey graphs, Mattheus–Verstraëte on $r(4,t)$, and Bradač on general fixed off-diagonal Ramsey numbers. The manuscripts’ bibliographies identify the classical upper-bound papers and the geometric and information-theoretic tools used in the construction.

Source manuscripts

• M1. OpenAI, The sharp logarithmic exponent of r(5,t) (September 24, 2026).
• M2. OpenAI, Sharp Logarithmic Exponents for Fixed Off-Diagonal Ramsey Numbers (September 24, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.