Even-edge graphs and H-code density

Question 1.1 · arXiv:2301.13305

arXiv Question high confidence— first stated 2023-02-06

Author: Noga Alon

Status partial medium confidence

The full Question 1.1 — whether $d_H(n)\to 0$ for every fixed graph $H$ with an even number of edges — remains open for general H-codes. Versteegen (arXiv:2310.19891, 2023) proved the analogous statement for the linear variant: if $H$ has an even number of edges then the density of a linear graph code avoiding $H$ is $O(2^{\binom{n}{2}}/\log n)$, and for almost all such $H$ it is at most $2^{\binom{n}{2}/n^{\varepsilon_H}}$ for some $\varepsilon_H>0$. This constitutes partial progress on Alon's question but does not settle it for non-linear codes.

Cited literature (1)

partial Upper bounds for linear graph codes (2023)

Leo Versteegen · Random Structures & Algorithms · arXiv:2310.19891

Proves that linear H-codes with H having an even number of edges have density O(1/log n), and for almost all such H an exponentially smaller density bound; explicitly described as progress on Alon's question.

Reviewer notes. Versteegen's partial result is for the linear subproblem (codes closed under symmetric difference); it does not imply the general case since linear codes form a strict subset of all H-codes. The paper was published in Random Structures & Algorithms (Wiley) in 2025. The pre-existing 'Structured Codes of Graphs' by Alon and Gujgiczer (arXiv:2202.06810, SIAM J. Discrete Math. 2023) predates the graph-codes paper and is not a follow-up. The full non-linear question appears to remain open as of May 2026.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Let $\mathcal{H}$ be a family of graphs closed under isomorphism. Is it true that $d_{\mathcal{H}}(n)$ tends to $0$ as $n$ tends to infinity if and only if $\mathcal{H}$ contains a graph with an even number of edges? Equivalently: is it true that for any fixed graph $H$ with an even number of edges, $d_H(n)$ tends to $0$ as $n$ tends to infinity?

Context

The authors define $d_H(n)$ as the maximum fraction of all graphs on $[n]$ forming an $H$-code (a family with no two members whose symmetric difference is a copy of $H$). If every member of $\mathcal{H}$ has an odd number of edges then $d_{\mathcal{H}}(n) \geq 1/2$, motivating the question of whether containing an even-edge graph is exactly the condition that forces $d_{\mathcal{H}}(n) \to 0$. The question is stated as the central open problem and noted in the concluding remarks to remain wide open.

Source paper

Graph-codes
Noga Alon · 2023-02-06
https://arxiv.org/abs/2301.13305 PDF source