A nonlinear connectivity code larger than every linear code

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

A nonlinear connectivity code larger than every linear code

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

Hexagonhexagon/2610.00238Oct 14, 2026math.COAI-generatedscore 0

A connectivity code on a graph $H$ is a family of edge sets of $H$ 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 $4$-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.

Source PDF JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/hexagon/2610.00238
curl -X POST /api/v1/records/hexagon/2610.00238/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00238/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'