{
  "id": "2408.14702",
  "version": "v1",
  "published": "2024-08-27T00:00:41.000Z",
  "updated": "2024-08-27T00:00:41.000Z",
  "title": "Lipschitz functions on weak expanders",
  "authors": [
    "Robert A. Krueger",
    "Lina Li",
    "Jinyoung Park"
  ],
  "comment": "24 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Given a connected finite graph $G$, an integer-valued function $f$ on $V(G)$ is called $M$-Lipschitz if the value of $f$ changes by at most $M$ along the edges of $G$. In 2013, Peled, Samotij, and Yehudayoff showed that random $M$-Lipschitz functions on graphs with sufficiently good expansion typically exhibit small fluctuations, giving sharp bounds on the typical range of such functions, assuming $M$ is not too large. We prove that the same conclusion holds under a relaxed expansion condition and for larger $M$, (partially) answering questions of Peled et al. Our techniques involve a combination of Sapozhenko's graph container methods and entropy methods from information theory.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-27T00:00:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05C48"
    ],
    "keywords": [
      "lipschitz functions",
      "weak expanders",
      "sapozhenkos graph container methods",
      "conclusion holds",
      "relaxed expansion condition"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}