Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields
<p>A maximal minor M of the Laplacian of an n-vertex Eulerian digraph Γ gives rise to a finite group Zn−1/Zn−1M known as the sandpile (or critical) group S(Γ) of Γ. We determine S(Γ) of the generalized de Bruijn graphs Γ = DB(n, d) with vertices 0, ..., n − 1 and arcs (i, di + k) for 0 ≤ i ≤ n...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2014
|
| _version_ | 1797106766699298816 |
|---|---|
| author | Chan, SH Hollmann, HDL Pasechnik, DV |
| author_facet | Chan, SH Hollmann, HDL Pasechnik, DV |
| author_sort | Chan, SH |
| collection | OXFORD |
| description | <p>A maximal minor M of the Laplacian of an n-vertex Eulerian
digraph Γ gives rise to a finite group Zn−1/Zn−1M known as
the sandpile (or critical) group S(Γ) of Γ. We determine S(Γ)
of the generalized de Bruijn graphs Γ = DB(n, d) with vertices
0, ..., n − 1 and arcs (i, di + k) for 0 ≤ i ≤ n − 1 and 0 ≤ k ≤
d − 1, and closely related generalized Kautz graphs, extending
and completing earlier results for the classical de Bruijn and
Kautz graphs.</p>
<p>Moreover, for a prime p and an n-cycle permutation matrix
X ∈ GLn(p) we show that S(DB(n, p)) is isomorphic to the
quotient by (X) of the centralizer of X in PGLn(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 Fpn from spanning trees in DB(n, p).</p> |
| first_indexed | 2024-03-07T07:05:40Z |
| format | Journal article |
| id | oxford-uuid:0936627a-7dfb-49fb-b24d-486614cebe79 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:05:40Z |
| publishDate | 2014 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:0936627a-7dfb-49fb-b24d-486614cebe792022-05-11T14:35:18ZSandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fieldsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0936627a-7dfb-49fb-b24d-486614cebe79EnglishORA DepositElsevier2014Chan, SHHollmann, HDLPasechnik, DV<p>A maximal minor M of the Laplacian of an n-vertex Eulerian digraph Γ gives rise to a finite group Zn−1/Zn−1M known as the sandpile (or critical) group S(Γ) of Γ. We determine S(Γ) of the generalized de Bruijn graphs Γ = DB(n, d) with vertices 0, ..., n − 1 and arcs (i, di + k) for 0 ≤ i ≤ n − 1 and 0 ≤ k ≤ d − 1, and closely related generalized Kautz graphs, extending and completing earlier results for the classical de Bruijn and Kautz graphs.</p> <p>Moreover, for a prime p and an n-cycle permutation matrix X ∈ GLn(p) we show that S(DB(n, p)) is isomorphic to the quotient by (X) of the centralizer of X in PGLn(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 Fpn from spanning trees in DB(n, p).</p> |
| spellingShingle | Chan, SH Hollmann, HDL Pasechnik, DV Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields |
| title | Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields |
| title_full | Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields |
| title_fullStr | Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields |
| title_full_unstemmed | Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields |
| title_short | Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields |
| title_sort | sandpile groups of generalized de bruijn and kautz graphs and circulant matrices over finite fields |
| work_keys_str_mv | AT chansh sandpilegroupsofgeneralizeddebruijnandkautzgraphsandcirculantmatricesoverfinitefields AT hollmannhdl sandpilegroupsofgeneralizeddebruijnandkautzgraphsandcirculantmatricesoverfinitefields AT pasechnikdv sandpilegroupsofgeneralizeddebruijnandkautzgraphsandcirculantmatricesoverfinitefields |