{
  "id": "2308.07653",
  "version": "v1",
  "published": "2023-08-15T09:02:45.000Z",
  "updated": "2023-08-15T09:02:45.000Z",
  "title": "Connectivity Graph-Codes",
  "authors": [
    "Noga Alon"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The symmetric difference of two graphs $G_1,G_2$ on the same set of vertices $V$ is the graph on $V$ whose set of edges are all edges that belong to exactly one of the two graphs $G_1,G_2$. For a fixed graph $H$ call a collection ${\\cal G}$ of spanning subgraphs of $H$ a connectivity code for $H$ if the symmetric difference of any two distinct subgraphs in ${\\cal G}$ is a connected spanning subgraph of $H$. It is easy to see that the maximum possible cardinality of such a collection is at most $2^{k'(H)} \\leq 2^{\\delta(H)}$, where $k'(H)$ is the edge-connectivity of $H$ and $\\delta(H)$ is its minimum degree. We show that equality holds for any $d$-regular (mild) expander, and observe that equality does not hold in several natural examples including powers of long cycles and products of a small clique with a long cycle.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-15T09:02:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05D40",
      "94B25"
    ],
    "keywords": [
      "connectivity graph-codes",
      "symmetric difference",
      "long cycle",
      "spanning subgraph",
      "small clique"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}