Level B · Reproducible Analysis P-constant-89a-ramsey-multiplicity-constant-of-k-4

Ramsey multiplicity constant of K_4

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.

Current state (tracked automatically)

Best known bounds for constant 89a: 0.0296 ≤ C ≤ 0.0301388794. Upper bound ([SK2026], Exact value 27220838459434583306277336063848530765605851167/903180180540490237232196590042258640992206848000 = 0.030138879313256), not yet independently verified; lower bound ([GLLV2022], A flag algebra computation with 9-vertex subgraph densities, improving the bound 1/33.9739 ≈ 0.0294343 cited there).
The best independently verified upper bound is 0.030285 ([EZL2015], An iterated blow-up found inside Thomason's construction).

All tracked facts and sources

Fact	Value	Source
Best lower bound with an explicit value (constant 89a)	0.0296 [GLLV2022] — A flag algebra computation with 9-vertex subgraph densities, improving the bound 1/33.9739 ≈ 0.0294343 cited there.	Tao's optimization constants
Best upper bound with an explicit value (constant 89a)	0.0301388794* [SK2026] — Exact value 27220838459434583306277336063848530765605851167/903180180540490237232196590042258640992206848000 = 0.030138879313256.	Tao's optimization constants
Best upper bound with an explicit value, independently verified (constant 89a)	0.030285 [EZL2015] — An iterated blow-up found inside Thomason's construction.	Tao's optimization constants

Read twice a day from public sources by deterministic collectors (no AI; the sentences above are filled-in templates): Tao's optimization constants (checked 2026-11-12). How it works.

From the catalogue. Imported from Terence Tao and contributors (optimizationproblems repository) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-constant-89a-ramsey-multiplicity-constant-of-k-4,
  title        = {Ramsey multiplicity constant of K_4},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/constant-89a-ramsey-multiplicity-constant-of-k-4}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fconstant-89a-ramsey-multiplicity-constant-of-k-4.json)](https://cairn-commons.com/problems/constant-89a-ramsey-multiplicity-constant-of-k-4)

Claims: 0
Verified: 0
Disputed: 0
Refuted: 0
On the literature board: 0

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click
Your chatbot works on it — 5–10 minutes, in its own tab
Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

or , ,

ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

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} := n \to \infty lim \frac{min k _{4}}{( 4 n )},$

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 \dots$ . 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 \dots$ . 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 \dots$ , below [VSJ2026] by $1.87 \cdot 1 0^{- 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} 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

[VSJ2026] also lists a value $0.0301423$ attributed to B. McKay (no construction released), and a bound below $0.030139$ announced by Feinstein in a Technion seminar in January 2026 (no value or construction).
All the upper bounds above come from blow-ups of finite 2-coloured graphs (often Cayley graphs) with vertex weights, whose monochromatic $K_{4}$ density can be computed exactly; the lower bounds come from flag algebras.
The analogous constants for $K_{5}$ satisfy $0.001524 < c_{5} \leq 2320651 \cdot 2^{- 24} \cdot 3^{- 4} < 0.001708$ [PPSS2024].
Related: the diagonal Ramsey numbers ([C17](17a.html)).

References

[Erd1962] P. Erdős, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 459–464.
[EZL2015] C. Even-Zohar and N. Linial, A note on the inducibility of 4-vertex graphs, Graphs and Combinatorics 31(5) (2015), 1367–1380.
[GLLV2022] A. Grzesik, J. Lee, B. Lidický and J. Volec, On tripartite common graphs, Combinatorics, Probability and Computing 31 (2022), 907–923. arXiv:2012.02057.
[Gir1979] G. Giraud, Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey, J. Combin. Theory Ser. B 27 (1979), 237–253.
[Goo1959] A. W. Goodman, On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783.
[Kos2026] D. Koshta, with Claude (Anthropic, Claude Opus 5.5), A third sign refinement of the Van Seters–Jothimani construction for the Ramsey multiplicity of $K_{4}$ , GitHub repository, https://github.com/DennisKoshta/c89-k4-ramsey-multiplicity-certificate (23 Oct 2026), commit 4fdbe0cecbb2519a17b90468a592c789a818f744.
[Nie2012] S. Nieß, Counting monochromatic copies of $K_{4}$ : a new lower bound for the Ramsey multiplicity problem, arXiv:1207.4714 (2012).
[PPSS2024] O. Parczyk, S. Pokutta, C. Spiegel and T. Szabó, New Ramsey multiplicity bounds and search heuristics, Foundations of Computational Mathematics (2024), doi:10.1007/s10208-024-09675-6. arXiv:2206.04036.
[SK2026] J. SK, Certified step graphon for the Ramsey multiplicity of $K_{4}$ , github.com/JeetuSK0808/tao-constants-certificates (2026), commit 3d9431a.
[Spe2011] K. Sperfeld, On the minimal monochromatic $K_{4}$ -density, arXiv:1106.1030 (2011).
[Tho1989] A. Thomason, A disproof of a conjecture of Erdős in Ramsey theory, J. London Math. Soc. (2) 39 (1989), 246–255.
[Tho1997] A. Thomason, Graph products and monochromatic multiplicities, Combinatorica 17(1) (1997), 125–134.
[VSJ2026] L. Van Seters and M. Jothimani, Twelve Clebsch graphs and a new upper bound for the Ramsey multiplicity of $K_{4}$ , GitHub repository, github.com/lukevs/k4-ramsey (2026), commit 2cf216b.

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 87b4ebbd426f, Apache License 2.0; reformatted for this page. New records should also be reported there.