HEXAGONbeta

A nonlinear connectivity code larger than every linear code

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.IT — Information Theory

Contributed by Matěj Kripner ↗, Václav Rozhoň ↗, Robert Šámal ↗, Martin Šindelář, Adrián Zámečník

Version 1 / Oct 14, 2026 / CC BY 4.0

Abstract

A connectivity code on a graph HH is a family of edge sets of HH whose pairwise symmetric differences are connected spanning subgraphs. Alon asked whether a nonlinear connectivity code can ever be larger than every linear one on the same graph. We answer this affirmatively: we construct a 44-regular graph on fifteen vertices on which the largest connectivity code has nine members and the largest linear connectivity code has eight. The code is obtained by lifting a quaternary code of length six with pairwise agreement one through clique gadgets.

Provenance statement

This work was produced within the Bolzano project (https://bolzano.app), using AI systems for mathematical research and manuscript preparation. The listed authors contributed to the project and the preparation of this release. The manuscript received only limited human checking. Text origin: primarily AI-generated. Human understanding: some parts of this contribution have been checked and understood by a human. The manuscript received only limited human checking. The prior automated editorial and literature checks do not constitute human verification. No exact earlier separation located in the October 11 literature review; absolute priority is not certified.

Tools used

Bolzano team
Bolzano

References

  1. N. Alon, A. Gujgiczer, J. Körner, A. Milojević, and G. Simonyi, Structured codes of graphs , SIAM Journal on Discrete Mathematics 37 (2023), no. 1, 379--403. https://doi.org/10.1137/22M1487989.DOI
  2. N. Alon, Connectivity graph-codes , Random Structures & Algorithms 65 (2024), no. 3, 451--459. https://doi.org/10.1002/rsa.21222. Revised author manuscript: https://web.math.princeton.edu/~nalon/PDFS/GCII3.pdf.DOI
  3. N. Alon, Graph-codes , European Journal of Combinatorics 116 (2024), article 103880. https://doi.org/10.1016/j.ejc.2023.103880. https://arxiv.org/abs/2301.13305.DOI
  4. N. Alon, Graph-codes: questions, results and methods , Japanese Journal of Mathematics (2026), published online 12 July 2026. https://doi.org/10.1007/s11537-026-2536-1.DOI
  5. B. Bai, Y. Gao, J. Ma, and Y. Wu, Phase transitions of structured codes of graphs , SIAM Journal on Discrete Mathematics 38 (2024), no. 2, 1902--1914. https://doi.org/10.1137/23M1614572. Preprint: https://arxiv.org/abs/2307.08266v1.DOI
  6. A. Berger and Y. Zhao, K4K_4-intersecting families of graphs , Journal of Combinatorial Theory, Series B 163 (2023), 112--132. https://doi.org/10.1016/j.jctb.2023.07.005.DOI
  7. D. Ellis, Y. Filmus, and E. Friedgut, Triangle-intersecting families of graphs , Journal of the European Mathematical Society 14 (2012), no. 3, 841--885. https://doi.org/10.4171/JEMS/320.DOI
  8. L. Gishboliner, Z. Jin, and B. Sudakov, Difference-isomorphic graph families , Journal of Combinatorial Theory, Series B 180 (2026), 25--61. https://doi.org/10.1016/j.jctb.2026.06.001.DOI
  9. A. R. Hammons, P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, The Z4\mathbb Z_4-linearity of Kerdock, Preparata, Goethals, and related codes , IEEE Transactions on Information Theory 40 (1994), no. 2, 301--319. https://doi.org/10.1109/18.312154.DOI
  10. A. W. Nordstrom and J. P. Robinson, An optimum nonlinear code , Information and Control 11 (1967), no. 5--6, 613--616. https://doi.org/10.1016/S0019-9958(67)90835-2.DOI
Show all 13 referencesShow fewer references
  1. M. Plotkin, Binary codes with specified minimum distance , IRE Transactions on Information Theory 6 (1960), no. 4, 445--450. https://doi.org/10.1109/TIT.1960.1057584.DOI
  2. C. Tian, Maximal connectivity graph-codes exist in every degree at least four: f(d)=2df(d)=2^d for all d≥4d\geq4, answering a question of Alon , arXiv:2609.02953v1, 2 September 2026, Section 6(c). Listed on arXiv as Alon's Question on Connectivity Graph-Codes: f(d)=2df(d)=2^d for Every d≥4d\geq4 . https://arxiv.org/abs/2609.02953v1.arXiv
  3. L. Versteegen, Upper bounds for linear graph codes , Random Structures & Algorithms 66 (2025), no. 1, article e21263. https://doi.org/10.1002/rsa.21263. https://arxiv.org/abs/2310.19891.DOI

Version history

  1. v1Submitted by Václav RozhoňInitial depositCurrentOct 14, 2026