{
  "id": "1301.6296",
  "version": "v4",
  "published": "2013-01-26T23:27:15.000Z",
  "updated": "2024-01-15T01:54:33.000Z",
  "title": "On expanders from the action of GL(2,Z)",
  "authors": [
    "James R. Lee"
  ],
  "comment": "This is an unpublished note. It is essentially identical to v3 from 2013. I am placing it here so that it can be reliably referenced",
  "categories": [
    "math.CO",
    "math.SP"
  ],
  "abstract": "Consider the undirected graph $G_n=(V_n, E_n)$ where $V_n = (Z/nZ)^2$ and $E_n$ contains an edge from $(x,y)$ to $(x+1,y)$, $(x,y+1)$, $(x+y,y)$, and $(x,y+x)$ for every $(x,y) \\in V_n$. Gabber and Galil, following Margulis, gave an elementary proof that ${G_n}$ forms an expander family. In this note, we present a somewhat simpler proof of this fact, and demonstrate its utility by isolating a key property of the linear transformations $(x,y) -> (x+y,x), (x,y+x)$ that yields expansion. As an example, consider any invertible, integral matrix $S \\in GL_2(Z)$ and let $G^S_n = (V_n, E^S_n)$ where $E^S_n$ contains, for every $(x,y) \\in V_n$, an edge from $(x,y)$ to $(x+1,y)$, $(x,y+1)$, $S(x,y)$, and $S^T(x,y)$, where $S^T$ denotes the transpose of $S$. Then {G_n^S} forms an expander family if and only if a related infinite graph has positive Cheeger constant. This latter property turns out to be elementary to analyze and can be used to show that {G_n^S} are expanders precisely when the trace of S is non-zero and S is not equal to its transpose. We also present some other generalizations.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-02-07T18:39:22.000Z",
      "comment": "This has been withdrawn and will be reposted in another form. This expository note happens to reproduce arguments very similar to those of Berger and Shalom for proving property (T) for SL_2(Z) \\ltimes Z^2",
      "journal": null,
      "doi": null
    },
    {
      "version": "v4",
      "updated": "2024-01-15T01:54:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "somewhat simpler proof",
      "positive cheeger constant",
      "related infinite graph",
      "elementary proof",
      "linear transformations"
    ],
    "tags": [
      "expository article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.6296L"
    }
  }
}