{
  "id": "1605.06360",
  "version": "v1",
  "published": "2016-05-20T13:59:33.000Z",
  "updated": "2016-05-20T13:59:33.000Z",
  "title": "Eigenvalues of subgraphs of the cube",
  "authors": [
    "Béla Bollobás",
    "Jonathan Lee",
    "Shoham Letzter"
  ],
  "comment": "27 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the problem of maximising the largest eigenvalue of subgraphs of the hypercube $Q_d$ of a given order. We believe that in most cases, Hamming balls are maximisers, and our results support this belief. We show that the Hamming balls of radius $o(d)$ have largest eigenvalue that is within $1 + o(1)$ of the maximum value. We also prove that Hamming balls with fixed radius maximise the largest eigenvalue exactly, rather than asymptotically, when $d$ is sufficiently large. Our proofs rely on the method of compressions.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-05-20T13:59:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "largest eigenvalue",
      "hamming balls",
      "maximum value",
      "results support",
      "fixed radius maximise"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 27,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}