Linear graph-code cardinality bounds for even H
Open problem: tighter bounds for linear graph-codes · arXiv:2301.13305
Status partial high confidence
Versteegen (2023, arXiv:2310.19891) made significant progress on this problem: for any fixed graph H with an even number of edges, the maximum size of a linear H-code is O(2^{\binom{n}{2}} / \log n), and for almost all such H there exists \varepsilon_H > 0 giving the stronger bound 2^{\binom{n}{2}/n^{\varepsilon_H}}. These are substantially tighter than the original Ramsey-based bounds from the source paper. However, tight bounds matching a lower construction are not yet established in general, so the full problem remains open.
Cited literature (1)
-
Proves that for any fixed graph H with an even number of edges the maximum size of a linear H-code is O(2^{\binom{n}{2}}/\log n), and for almost all such H obtains the stronger polynomial-suppression bound 2^{\binom{n}{2}/n^{\varepsilon_H}}, directly addressing the open problem from Alon (2301.13305).
Reviewer notes. The open problem asks for tight (matching upper and lower) bounds; Versteegen's paper gives substantially improved upper bounds but full tightness for general H is still open. The published version appeared in Random Structures & Algorithms (2025).
Context
The paper notes that for any fixed graph $H$ with an even number of edges the maximum size of a linear $H$-code is $o\bigl(2^{\binom{n}{2}}\bigr)$, but the proof via Ramsey's Theorem yields very weak quantitative bounds. Theorem 1.6 gives a tight result for the family $\mathcal{K}$ of all cliques as a model for what such tight results could look like.
Source paper
Graph-codes
Noga Alon · 2023-02-06
https://arxiv.org/abs/2301.13305
PDF source