on new lower bounds of R(3, k)

Overview

In 2025, the lower bound on the off-diagonal Ramsey number $R(3,k)$ improved twice in rapid succession — first from $\frac{1}{4}$ to $\frac{1}{3}$ by Campos, Jenssen, Michelen, and Sahasrabudhe (Campos et al., 2025), and then from $\frac{1}{3}$ to $\frac{1}{2}$ by Hefty, Horn, King, and Pfender (Hefty et al., 2025). Together, these papers close the gap to the conjectured constant. The story illustrates a principle: the nibble, the dominant technique since Kim (1995), can be replaced — first partially, then entirely — by structured blow-ups of small random graphs.

🏷️ Background: $R(3,k)$

The Ramsey number $R(s,t)$ is the smallest $N$ such that every $N$-vertex graph contains either a clique of size $s$ or an independent set of size $t$. For $s=3$ fixed and $k=t\to \infty$, the bounds are:

$$\left(\frac{1}{4}+o(1)\right)\frac{k^2}{\log k}\le R(3,k)\le \left(1+o(1)\right)\frac{k^2}{\log k}$$

as of 2013. The upper bound is due to Shearer (1983) (Shearer, 1983), building on the semi-random method of Ajtai, Komlós, and Szemerédi (1980) (Ajtai, Komlós & Szemerédi, 1980). The lower bound originates with Kim (1995) (Kim, 1995) (constant $c\approx 1/160$), and was improved to $\frac{1}{4}$ in 2013 independently by Bohman and Keevash (Bohman & Keevash, 2021) and by Fiz Pontiveros, Griffiths, and Morris (Fiz Pontiveros, Griffiths & Morris, 2020), via a celebrated analysis of the triangle-free process — a random process that adds edges one by one, uniformly from those that do not create a triangle, until no such edges remain.

The triangle-free process terminates with edge density $\sim \frac{1}{\sqrt{2}}\sqrt{\frac{\log n}{n}}$ and independence number $\sim \sqrt{2}\sqrt{n\log n}$, yielding the constant $\frac{1}{4}$. Fiz Pontiveros, Griffiths, and Morris conjectured that this constant is sharp. It is not.

🏷️ First bite: the seeded nibble (Campos et al., $\frac{1}{3}$)

Campos, Jenssen, Michelen, and Sahasrabudhe (Campos et al., 2025) broke the $\frac{1}{4}$ barrier by observing that the triangle-free process is too random — one can obtain a denser graph by trading some randomness for structure.

The key insight

In the triangle-free process at density $p$, the probability that a pair $e=xy$ remains open (can be added without creating a triangle) is roughly $(1-p^2{)}^n\approx e^{-p^{2}n}$. The process saturates when $e^{-p^{2}n}\approx p$, which gives $p\approx \sqrt{\frac{\log n}{2n}}$ — the familiar density. But if we start from a seed graph that already contains a fraction of the edges while keeping most pairs open, the subsequent process can reach a higher final density.

The seed step. Sample a random graph on $n/(\log n{)}^2$ vertices at density $p_0={\alpha }_0\sqrt{\frac{\log n}{n}}$, remove a few edges to make it triangle-free, then blow it up by a factor of $r=(\log n{)}^2$. After this blow-up, almost every pair is still open — the density is too low relative to the blow-up factor to close many pairs. Concretely,

$$\mathbb{P}(e\text{ open after seed})\approx (1-p_0^2{)}^{n/r}=1-o(1).$$

The modified nibble. The authors then run a steered variant of the triangle-free process on top of the seed. Unlike the original process, where the trajectory is determined by the random edge choices, here the process is manually guided to follow a simpler differential equation, avoiding the intricate martingale analysis that made the Bohman–Keevash and Fiz Pontiveros–Griffiths–Morris papers so technical.

The seed and the nibble together produce a graph of final density $p_0+p_1$ with ${\alpha }_0={\alpha }_1=\frac{1}{\sqrt{6}}$, giving total density $\sqrt{\frac{2}{3}}\sqrt{\frac{\log n}{n}}$ and independence number $\sim \sqrt{\frac{3}{2}}\sqrt{n\log n}$, which yields $R(3,k)\ge (\frac{1}{3}+o(1))\frac{k^2}{\log k}$.

Heuristic: why $\frac{1}{3}$ and not more?

Let $p_0={\alpha }_0\sqrt{\frac{\log n}{n}}$ (seed density) and $p_1={\alpha }_1\sqrt{\frac{\log n}{n}}$ (nibble density). A pair $e$ with endpoints in different parts of the partition can be closed in three ways: by two edges from the seed (probability $\approx 1-(1-p_0^2{)}^{n/r}\approx 0$), by two edges from the nibble ($\approx 1-e^{-p_1^{2}n}$), or by one from each ($\approx 1-e^{-2p_0{p}_{1}n}$). The total probability a pair is closed is

$$\approx 1-\exp (-(2p_0{p}_1+p_1^2)n).$$

The process saturates when this probability balances the current density, giving the constraint

$$({\alpha }_0+{\alpha }_1{)}^2-{\alpha }_0^2=\frac{1}{2}.$$

For the independence number, the dominant contribution comes from $k$-sets that intersect $k$ different parts of the partition. A calculation shows $\alpha (G)\le \sqrt{3/2}\sqrt{n\log n}$ when ${\alpha }_0={\alpha }_1=1/\sqrt{6}$, yielding the constant $\frac{1}{3}$.

The Campos et al. paper already conjectured that $\frac{1}{2}$ is the correct constant (Conjecture 2.1 in their paper). They noted that a better seed could potentially reach $\frac{1}{2}$, and speculated about a Cayley sum graph construction over ${\mathbb{F}}_2^d$ as a candidate. The Hefty et al. paper proved the $\frac{1}{2}$ lower bound just a few months later — but not by finding a better seed. Instead, they eliminated the nibble entirely.

🏷️ Second bite: no nibble at all (Hefty et al., $\frac{1}{2}$)

Hefty, Horn, King, and Pfender (Hefty et al., 2025) asked: why run a nibble at all? The nibble’s role in the Campos et al. construction is to add the second half of the edges while destroying the large independent sets created by the blow-up. But a nibble is technically demanding — one must track the evolution of degrees, codegrees, and open pairs over many rounds.

What if the second half of the edges also came from a blow-up of a small random graph?

The construction. Choose $s={\log }^{2}n$, $m=n/s$, and $p=\frac{1}{2}\sqrt{\frac{\log n}{n}}$.

1. Sample two independent $G(m,p)$ graphs $G_R$ (red) and $G_B$ (blue).
2. Choose a random injection $\pi :V(G)\to V_R\times V_B$. Each vertex in $V_R$ or $V_B$ has about $s$ preimages (its fiber).
3. Lift edges: ${\tilde{E}}_R=\{uv:{\pi }_R(u){\pi }_R(v)\in E(G_R)\}$ and symmetrically for ${\tilde{E}}_B$. Each blow-up is individually triangle-free, and together they have edge density $(2+o(1))p=(1+o(1))\sqrt{\frac{\log n}{n}}$.
4. Delete one edge from every triangle. Monochromatic triangles lose the lexicographically last edge. For 2-colored triangles (two red + one blue, or vice versa), delete the edge whose color appears only once.

Why this works

Each deleted edge lies between the endpoints of roughly $s$ monochromatic paths of length 2 — so each deletion destroys about $s$ triangles. The factor $s={\log }^{2}n$ is exactly the gain in efficiency over the standard edge-deletion method (which would delete one edge per triangle). A larger $s$ gives a larger efficiency gain, but also makes the graph less random. At $s={\log }^{2}n$, the balance works.

Comparison with Campos et al. The Campos construction is: seed blow-up → modified nibble. The Hefty construction is: blow-up 1 → blow-up 2 (overlaid). Both use the idea that a blow-up of a small $G(m,p)$ carries a “positive proportion” of the final density while keeping the graph sufficiently pseudorandom to control independent sets. The crucial difference is that the second stage — the nibble in Campos, the second blow-up in Hefty — is vastly simpler to analyze in the latter case, because it inherits the same structural decomposition as the first stage.

The independence number analysis

For a $k$-set $I$ with $k=(1+\epsilon )\sqrt{n\log n}$, let ${\ell }_R=|{\pi }_R(I)|$, ${\ell }_B=|{\pi }_B(I)|$. Ignoring deleted edges, $I$ is independent in $\tilde{E}(G)$ iff both projections ${\pi }_R(I)$ and ${\pi }_B(I)$ are independent in $G_R$ and $G_B$.

Vertices $v\in V_R\cup V_B$ are classified by $|X_v(I)|=|I\cap N_v|$:

• Huge ($>\sqrt{n\log n}/\log \log n$): at most $\sim 2\log \log n$ vertices; their contribution dominates but is controlled by degree bounds.
• Large ($n^{1/4+\epsilon }$ to $t_1$): bounded by inclusion-exclusion with codegree bounds.
• Medium ($n^{2\epsilon }$ to $n^{1/4+\epsilon }$): an unlikely dense subgraph argument.
• Small ($\le n^{2\epsilon }$): McDiarmid’s inequality over independent neighborhood variables.

The probability that $I$ is independent (after edge deletions) is at most $\exp (-p(f({\ell }_R,{\ell }_B)-o(k^2)))$, where $f$ counts the “open pairs” not forced by the revealed structure. A union bound over the three regimes of ${\ell }_R+{\ell }_B$ shows the expected number of independent $k$-sets is $o(1)$.

🏷️ The Trajectory in One Table

Year	Constant $c$	Authors	Method
1995	$\frac{1}{160}$	Kim	nibble
2013	$\frac{1}{4}$	Bohman–Keevash; Fiz Pontiveros–Griffiths–Morris	triangle-free process (full analysis)
2025	$\frac{1}{3}$	Campos–Jenssen–Michelen–Sahasrabudhe	seed blow-up + modified nibble
2025	$\frac{1}{2}$	Hefty–Horn–King–Pfender	two blow-ups, no nibble

The upper bound remains Shearer’s $(1+o(1))\frac{k^2}{\log k}$, and the conjecture — stated independently by both groups — is that $\frac{1}{2}$ is the truth.

🏷️ Beyond $R(3,k)$

The “two bites” construction is flexible. The same paper proves a matching lower bound for hypergraph Ramsey numbers:

Hypergraph stars

$R(S_4^{(3)},S_k^{(3)})=\left(\frac{1}{2}-o(1)\right)\frac{k^2}{\log k}$, improving the constant from Mubayi and Spanier (Mubayi & Spanier, 2025) and settling a conjecture of Conlon, Fox, He, Mubayi, Suk, and Verstraëte (Conlon et al., 2023).

The construction has since been applied to:

• Cycle-complete Ramsey numbers $r(C_{\ell },K_k)$ for odd $\ell \ge 9$ — the first polynomial improvement over the edge-deletion threshold (Campos et al., 2025b).
• The odd Hadwiger conjecture — disproved by Kühn, Sauermann, Steiner, and Wigderson (Kühn et al., 2025) using a variation of the construction where the complement’s large chromatic number replaces the small independence number.

The $\frac{1}{2}$ barrier

In the Hefty et al. construction, $\alpha (G)$ and the average degree asymptotically agree — both are $\sim \sqrt{n\log n}$. In any triangle-free graph, $\alpha (G)\ge \Delta (G)\ge \frac{2e(G)}{n}$, so any construction where $\alpha \approx \Delta$ cannot beat $\frac{1}{2}$ without a fundamentally different phenomenon: independence number smaller than average degree. This is why the conjectured constant $\frac{1}{2}$ is a natural barrier.

📚 References

🐻  Ajtai, M., Komlós, J. & Szemerédi, E. 1980. A note on Ramsey numbers. Journal of Combinatorial Theory, Series A 29(3), 354–360.

🐻  Bohman, T. & Keevash, P. 2021. Dynamic concentration of the triangle-free process. Random Structures & Algorithms 58(2), 221–293.

🐻  Campos, M., Jenssen, M., Michelen, M. & Sahasrabudhe, J. 2025a. A new lower bound for the Ramsey numbers R(3,k).

🐻  Campos, M., Jenssen, M., Michelen, M., Pfender, F. & Sahasrabudhe, J. 2025b. A polynomial improvement for the odd cycle-complete Ramsey numbers.

🐻  Conlon, D., Fox, J., He, X., Mubayi, D., Suk, A. & Verstraëte, J. 2023. Hypergraph Ramsey numbers of cliques versus stars. Random Structures & Algorithms 63(3), 610–623.

🐻  Fiz Pontiveros, G., Griffiths, S. & Morris, R. 2020. The triangle-free process and the Ramsey number R(3,k). Memoirs of the American Mathematical Society 263(1274).

🐻  Hefty, Z., Horn, P., King, D. & Pfender, F. 2025. Improving R(3,k) in just two bites.

🐻  Kim, J.H. 1995. The Ramsey number R(3,t) has order of magnitude t^2/\log t. Random Structures & Algorithms 7(3), 173–207.

🐻  Kühn, M., Sauermann, L., Steiner, R. & Wigderson, Y. 2025. Disproof of the odd Hadwiger conjecture.

🐻  Mubayi, D. & Spanier, N. 2025. K₄⁻-free triple systems without large stars in the complement.

🐻  Shearer, J.B. 1983. A note on the independence number of triangle-free graphs. Discrete Mathematics 46(1), 83–87.