Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2306.09315 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929317851693056 |
|---|---|
| author | Cho, Matthew Dochtermann, Anton Inagaki, Ryota Oh, Suho Snustad, Dylan Zacovic, Bailee |
| author_facet | Cho, Matthew Dochtermann, Anton Inagaki, Ryota Oh, Suho Snustad, Dylan Zacovic, Bailee |
| contents | We study chip-firing on a signed graph $G_ϕ$, employing a general theory of chip-firing on invertible matrices introduced by Guzmán and Klivans. Here a negative edge designates an adversarial relationship, so that firing a vertex incident to such an edge leads to a loss of chips at both endpoints. The chip-firing rule for $G_ϕ$ is described by its reduced Laplacian matrix $L_{G_ϕ}$, which also defines the critical group ${\mathcal K}(G_ϕ)$. The valid chip configurations are given by the lattice points of a rational cone determined by $G_ϕ$ and the underlying graph $G$. This gives rise to notions of critical as well as $z$-superstable configurations, both of which are counted by the determinant of $L_{G_ϕ}$. We establish general results regarding these configurations, focusing on efficient methods of verifying the underlying properties. We then study the critical groups of signed graphs in the context of vertex switching and Smith normal forms. We use this to compute the critical groups of various classes of signed graphs including signed cycles, wheels, complete graphs, and fans, in the process generalizing results of Biggs and others. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_09315 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Chip-firing and critical groups of signed graphs Cho, Matthew Dochtermann, Anton Inagaki, Ryota Oh, Suho Snustad, Dylan Zacovic, Bailee Combinatorics 05C50, 05C22, 20K01, 91A46 We study chip-firing on a signed graph $G_ϕ$, employing a general theory of chip-firing on invertible matrices introduced by Guzmán and Klivans. Here a negative edge designates an adversarial relationship, so that firing a vertex incident to such an edge leads to a loss of chips at both endpoints. The chip-firing rule for $G_ϕ$ is described by its reduced Laplacian matrix $L_{G_ϕ}$, which also defines the critical group ${\mathcal K}(G_ϕ)$. The valid chip configurations are given by the lattice points of a rational cone determined by $G_ϕ$ and the underlying graph $G$. This gives rise to notions of critical as well as $z$-superstable configurations, both of which are counted by the determinant of $L_{G_ϕ}$. We establish general results regarding these configurations, focusing on efficient methods of verifying the underlying properties. We then study the critical groups of signed graphs in the context of vertex switching and Smith normal forms. We use this to compute the critical groups of various classes of signed graphs including signed cycles, wheels, complete graphs, and fans, in the process generalizing results of Biggs and others. |
| title | Chip-firing and critical groups of signed graphs |
| topic | Combinatorics 05C50, 05C22, 20K01, 91A46 |
| url | https://arxiv.org/abs/2306.09315 |