{
  "id": "1405.0113",
  "version": "v1",
  "published": "2014-05-01T08:23:05.000Z",
  "updated": "2014-05-01T08:23:05.000Z",
  "title": "Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields",
  "authors": [
    "Swee Hong Chan",
    "Henk D. L. Hollmann",
    "Dmitrii V. Pasechnik"
  ],
  "comment": "I+24 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A maximal minor $M$ of the Laplacian of an $n$-vertex Eulerian digraph $\\Gamma$ gives rise to a finite group $\\mathbb{Z}^{n-1}/\\mathbb{Z}^{n-1}M$ known as the sandpile (or critical) group $S(\\Gamma)$ of $\\Gamma$. We determine $S(\\Gamma)$ of the generalized de Bruijn graphs $\\Gamma=\\mathrm{DB}(n,d)$ with vertices $0,\\dots,n-1$ and arcs $(i,di+k)$ for $0\\leq i\\leq n-1$ and $0\\leq k\\leq d-1$, and closely related generalized Kautz graphs, extending and completing earlier results for the classical de Bruijn and Kautz graphs. Moreover, for a prime $p$ and an $n$-cycle permutation matrix $X\\in\\mathrm{GL}_n(p)$ we show that $S(\\mathrm{DB}(n,p))$ is isomorphic to the quotient by $\\langle X\\rangle$ of the centralizer of $X$ in $\\mathrm{PGL}_n(p)$. This offers an explanation for the coincidence of numerical data in sequences A027362 and A003473 of the OEIS, and allows one to speculate upon a possibility to construct normal bases in the finite field $\\mathbb{F}_{p^n}$ from spanning trees in $\\mathrm{DB}(n,p)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-01T08:23:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C20",
      "05C50",
      "20K01"
    ],
    "keywords": [
      "finite field",
      "circulant matrices",
      "sandpile groups",
      "related generalized kautz graphs",
      "construct normal bases"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.0113C"
    }
  }
}