Ramsey multiplicity constant of $K_4$

Description of constant

For a 2-colouring of the edges of the complete graph $K_n$, let $k_4$ be the number of $4$-element vertex sets whose six edges all have the same colour. The Ramsey multiplicity constant of $K_4$ is

\[C_{89} := \lim_{n\to\infty} \frac{\min k_4}{\binom{n}{4}},\]

where the minimum is over all 2-colourings of the edges of $K_n$ (the limit exists by an averaging argument). Equivalently, $C_{89}$ is the minimum density of monochromatic copies of $K_4$ in a 2-edge-coloured graphon. It is often written $c_4$, $m_4$ or $C(K_4)$.

Erdős conjectured that the uniformly random colouring is optimal, i.e. $C_{89} = 2^{1-6} = 1/32$ [Erd1962]; Thomason disproved this [Tho1989]. For triangles the analogous constant is $1/4$ [Goo1959], and $K_4$ is the smallest complete graph for which the value is unknown.

Known upper bounds

Bound Reference Comments
$1/32 = 0.03125$ [Erd1962] Uniformly random colouring. Erdős conjectured that this is sharp.
$1/33 \approx 0.030303$ [Tho1989] Disproof of Erdős’s conjecture: iterated blow-ups of a 2-colouring of a core graph built from quadratic forms over a finite field.
$0.030291$ [Tho1997] Graph (XOR) products of small graphs, with a computer search for the core graph.
$0.030285$ [EZL2015] An iterated blow-up found inside Thomason’s construction.
$4551721 \cdot 2^{-24} \cdot 3^{-2} < 0.030145$ [PPSS2024] Theorem 1.1: the sequence of blow-ups of a 2-coloured Cayley graph on $768$ vertices, found by search heuristics. A construction on $384$ vertices also beats $0.03015$.
$0.0301388876$* [VSJ2026] Exact value $8450462766487926638466333426306607129/280384030360880691940646801777885184000 = 0.030138887566\ldots$. The vertices of the [PPSS2024] graph split into twelve families of $64$, each a blown-up Clebsch graph; two fractional inter-family patterns are made adjustable and then refined into a weighted blow-up with $3840$ classes. A Lean proof and an independent exact recount are supplied in a self-hosted repository (commit 2cf216b); the construction is reported as found by an AI research system. Asterisked: self-hosted and not independently replayed here.
$0.0301388794$* [SK2026] Exact value $27220838459434583306277336063848530765605851167/903180180540490237232196590042258640992206848000 = 0.030138879313256\ldots$. Gradient refinement of the [VSJ2026] step graphon: the same $3840$ blocks of equal weight; the red probabilities between blocks, grouped into $16045$ symmetry classes of block pairs, are moved by $120$ projected-gradient steps and rounded to multiples of $2^{-20}$. The density is computed exactly over every block (the integer numerator modulo $9$ primes, combined by CRT, plus a check prime). Data and checker at commit 3d9431a of [SK2026]. Asterisked: self-hosted and not independently replayed.
$0.0301388857$* [Kos2026] Exact value $1126728298914655736634696330762614467/37384537381450758925419573570384691200 = 0.0301388856953\ldots$, below [VSJ2026] by $1.87 \cdot 10^{-9}$ (exact margin $1049256017227412221891173997253/560768060721761383881293603555770368000$). One more balanced sign refinement of the final $3840$-class [VSJ2026] step graphon: every class is split in two, with amplitudes $\pm\min(w, 1-w)$ whose signs are chosen by ascent on the cubic term of the [VSJ2026] sign-refinement identity. The result is a $7680$-class step graphon with entries in $2^{-16}\mathbb{Z}$, whose monochromatic $K_4$ density was counted exactly by two independently written programs (the second, written from the witness format alone, also reproduces the [VSJ2026] value exactly). The repository holds only the amplitudes and a script that rebuilds the witness from the [VSJ2026] table (witness SHA-256 e37d811da4e8c261f30046c5453bb9c63fd9e9700989a33fccc948074c2b2a47). Asterisked: self-hosted.

Known lower bounds

Bound Reference Comments
$1/46 \approx 0.0217$ [Gir1979] As reported in [Spe2011] and [Nie2012].
$1/35 \approx 0.02857$ [Spe2011] Razborov’s flag algebra method.
$204603019/7112448000 > 0.0287$ [Nie2012] Flag algebras.
$1/33.77 \approx 0.0296$ [GLLV2022] A flag algebra computation with $9$-vertex subgraph densities, improving the bound $1/33.9739 \approx 0.0294343$ cited there.

Additional comments

References

Contribution notes

Prepared with Claude Code (Anthropic): it located the sources, checked each bound and quotation against the cited source, and drafted the page. A float64 re-evaluation of the [VSJ2026] step graphon (one representative block per symmetry class) reproduces $0.03013888757$; that row stays asterisked until it is replayed exactly. The [SK2026] row (the submitter’s) was found by a gradient search written with Claude Code and certified by a separate exact evaluator, also written with Claude Code. Prepared with Claude Code (Anthropic): it located the sources, checked each bound and quotation against the cited source, and drafted the page. A float64 re-evaluation of the [VSJ2026] step graphon (one representative block per symmetry class) reproduces $0.03013888757$; that row stays asterisked until it is replayed exactly.

The [Kos2026] row was found and prepared with Claude (Anthropic, Claude Opus 5.5), directed by Dennis Koshta, who takes responsibility for the submission: the amplitude search, the exact evaluator, the witness format, the rebuild script and the text. The witness was checked by a separate Claude agent with its own exact verifier, written from the witness format specification without access to the search code. No human mathematician has checked the argument.

← Back to the table of constants