K₄ graph-code density vanishing
Informal question: is $d_{K_4}(n) = o(1)$? · arXiv:2301.13305
Status partial medium confidence
The question whether $d_{K_4}(n) = o(1)$ for general graph codes remains open as of May 2026. Versteegen (arXiv:2310.19891, 2023) made partial progress by proving that any linear graph code on $n$ vertices containing no copy of a graph $H$ with an even number of edges has size $O(2^{\binom{n}{2}}/\log n)$, which settles the analogue for linear codes; however, the general (non-linear) case of the question from Conjecture 1.1 / Question 1.1 of arXiv:2301.13305 is not resolved by this work. Several further papers cite arXiv:2301.13305 (including Gishboliner–Jin–Sudakov 2312.06610, Conlon–Lee–Versteegen 2404.17467, and Rancourt–Dodos–Tyros 2602.03298) but none were verified to resolve the full question.
Cited literature (1)
-
Proves that a linear graph code on $n$ vertices with no copy of $H$ (even number of edges) has size $O(2^{\binom{n}{2}}/\log n)$, settling the linear-code variant of the $d_{K_4}(n)=o(1)$ question but leaving the general non-linear case open.
Reviewer notes. The Semantic Scholar citation list for arXiv:2301.13305 returned 20 citing papers (as of May 2026). The most directly relevant verified follow-up is arXiv:2310.19891 (Versteegen), which addresses only linear graph codes. The papers arXiv:2312.06610, arXiv:2404.17467, and arXiv:2602.03298 also cite the source paper but their specific results regarding $d_{K_4}(n)=o(1)$ were not verified within the 5-call budget. The lower bound $d_{K_4}(n) \geq 1/n^{o(1)}$ is established within the source paper itself via Hunter–Mubayi.
Context
In the concluding remarks the authors single this out as an interesting special case of Question 1.1. The companion question of whether $d_{K_4}(n) \geq 1/n^{o(1)}$ is answered affirmatively within the paper by appealing to an edge-coloring construction of Hunter and Mubayi [5] (modifying [11] and [4]); the upper-bound direction $d_{K_4}(n) = o(1)$ remains open.
Notes. The lower bound $d_{K_4}(n) \geq 1/n^{o(1)}$ is established in the paper; only the question of whether $d_{K_4}(n) = o(1)$ remains open.
Source paper
Graph-codes
Noga Alon · 2023-02-06
https://arxiv.org/abs/2301.13305
PDF source