Alon's Question on Connectivity Graph-Codes: f(d)=2d for Every d≥ 4
Abstract
For a finite graph H, a connectivity graph-code is a family 𝒞⊆ 2E(H) such that A△ B is a connected spanning subgraph of H whenever A and B are distinct members of 𝒞. Let m(H) denote the maximum size of such a family, and let f(d) be the largest integer q for which m(H)=q for infinitely many pairwise nonisomorphic d-regular graphs H. Restricting codewords to the edges incident with a vertex gives f(d)≤ 2d. Alon proved equality for all sufficiently large d and asked whether it holds for every d≥ 4. We answer this question affirmatively. More precisely, for every d≥ 4 we construct infinitely many finite simple d-regular bipartite graphs carrying a linear connectivity graph-code of dimension d. The construction begins with a vector-labelled copy of Kd,d. For d≥ 7, the required labelling follows from a probabilistic count over an irreducible conjugacy class in GLd(2); explicit matrices, verified by a short exact exhaustive program, cover d=4,5,6. Cyclic voltage lifts then produce the required infinite families.
Related
- The N-Prime Graph Question is equivalent to the Prime Graph Question
- Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
- Almost Every Graph Is Reconstructible from Its Token Graphs
- Every cubic graph has four total dominating sets covering each vertex at most twice
- Every graph with no K7= minor is 6-colorable
BibTeX
@misc{tian2026alons,
title = {{Alon's Question on Connectivity Graph-Codes: $f(d)=2^d$ for Every $d\geq 4$}},
author = {Chenxiao Tian},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02953},
eprint = {2609.02953},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02953},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Alon's Question on Connectivity Graph-Codes: f(d)=2^d for Every d≥ 4
AU - Chenxiao Tian
PY - 2026
DA - 2026/09/02
PB - arXiv
DO - 10.48550/arxiv.2609.02953
UR - https://arxiv.org/abs/2609.02953
AB - For a finite graph H, a connectivity graph-code is a family 𝒞⊆ 2^E(H) such that A△ B is a connected spanning subgraph of H whenever A and B are distinct members of 𝒞. Let m(H) denote the maximum size of such a family, and let f(d) be the largest integer q for which m(H)=q for infinitely many pairwise nonisomorphic d-regular graphs H. Restricting codewords to the edges incident with a vertex gives f(d)≤ 2^d. Alon proved equality for all sufficiently large d and asked whether it holds for every d≥ 4. We answer this question affirmatively. More precisely, for every d≥ 4 we construct infinitely many finite simple d-regular bipartite graphs carrying a linear connectivity graph-code of dimension d. The construction begins with a vector-labelled copy of K_d,d. For d≥ 7, the required labelling follows from a probabilistic count over an irreducible conjugacy class in GL_d(2); explicit matrices, verified by a short exact exhaustive program, cover d=4,5,6. Cyclic voltage lifts then produce the required infinite families.
ER -