{
  "id": "2301.13305",
  "version": "v1",
  "published": "2023-01-30T21:54:31.000Z",
  "updated": "2023-01-30T21:54:31.000Z",
  "title": "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 $[n]=\\{1,2, \\ldots ,n\\}$ is the graph on $[n]$ whose set of edges are all edges that belong to exactly one of the two graphs $G_1,G_2$. Let $H$ be a fixed graph with an even (positive) number of edges, and let $D_H(n)$ denote the maximum possible cardinality of a family of graphs on $[n]$ containing no two members whose symmetric difference is a copy of $H$. Is it true that $D_H(n)=o(2^{n \\choose 2})$ for any such $H$? We discuss this problem, compute the value of $D_H(n)$ up to a constant factor for stars and matchings, and discuss several variants of the problem including ones that have been considered in earlier work.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-01-30T21:54:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "94B25"
    ],
    "keywords": [
      "graph-codes",
      "symmetric difference",
      "constant factor",
      "earlier work",
      "cardinality"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}