{
  "id": "2309.09788",
  "version": "v1",
  "published": "2023-09-18T14:05:09.000Z",
  "updated": "2023-09-18T14:05:09.000Z",
  "title": "Exponentially many graphs are determined by their spectrum",
  "authors": [
    "Illya Koval",
    "Matthew Kwan"
  ],
  "comment": "26 pages, 5 figures",
  "categories": [
    "math.CO",
    "math.SP"
  ],
  "abstract": "As a discrete analogue of Kac's celebrated question on \"hearing the shape of a drum\", and towards a practical graph isomorphism test, it is of interest to understand which graphs are determined up to isomorphism by their spectrum (of their adjacency matrix). A striking conjecture in this area, due to van Dam and Haemers, is that \"almost all graphs are determined by their spectrum\", meaning that the fraction of unlabelled $n$-vertex graphs which are determined by their spectrum converges to $1$ as $n\\to\\infty$. In this paper we make a step towards this conjecture, showing that there are exponentially many $n$-vertex graphs which are determined by their spectrum. This improves on previous bounds (of shape $e^{c\\sqrt{n}}$), and appears to be the limit of \"purely combinatorial\" techniques. We also propose a number of further directions of research.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-09-18T14:05:09.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "vertex graphs",
      "practical graph isomorphism test",
      "adjacency matrix",
      "discrete analogue",
      "van dam"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 26,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}