Timeline for Chip-firing clocks
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 6, 2021 at 1:10 | comment | added | Sam Hopkins | So for the co-Eulerian graphs there is a combinatorial formula for the maximum $m=\sum \pi_i$ (note by the digraph Matrix-Tree theorem these $\pi_i$ are also the determinants of the corresponding reduced matrix we get by crossing out the $i$th row/column). But is there a combinatorial interpretation of the solution $x$ to $Hx = \mathbf{1} \mod m$ in this case? That would be very nice... | |
| Apr 6, 2021 at 0:18 | comment | added | lambda | Okay, I'm no longer optimistic: the undirected 4-cycle has a clock mod 2 but not mod 4. | |
| Apr 5, 2021 at 23:09 | comment | added | Sam Hopkins | So at least for the strongly connected digraphs $G$ with Laplacian cokernel $\mathbb{Z}$, which are called "co-Eulerian" by Farrell and Levine, the answer is nice: the maximum $m$ for which an $m$-clock exists is $m=\langle \pi, \mathbf{1}\rangle$ where $\pi$ is a primitive element of the kernel. In fact as they explain in the linked paper, this $\pi$ can be described as $\pi_i=$ number of oriented spanning trees of $G$ rooted at $i$. | |
| Apr 5, 2021 at 22:57 | comment | added | lambda | @WillSawin Ah, of course you're right, though I'd still like to be optimistic that it's true under some reasonable hypothesis. | |
| Apr 5, 2021 at 22:15 | comment | added | Sam Hopkins | The "co-Eulerian" digraphs of Farrell and Levine (pi.math.cornell.edu/~levine/coEulerian.pdf) may be relevant for Will's last comment. | |
| Apr 5, 2021 at 22:04 | comment | added | Will Sawin | @lambda This is not necesarily true. For example, if you take any directed graph and double every edge, i.e. double every entry in $H$, it is not possible to solve $Hx =1$ mod $2$, so $k$ cannot be even, but the kernel of $H^T$ is unchanged. It is true when the cokernel of the Laplacian $H^t$ is torsion-free. | |
| Apr 5, 2021 at 21:32 | comment | added | Sam Hopkins | Yes, in general for undirected graphs it will be the gcd of the sizes of the components. | |
| Apr 5, 2021 at 21:31 | comment | added | lambda | On that note, I of course really meant it equals the number of vertices for a connected undirected graph. | |
| Apr 5, 2021 at 21:23 | comment | added | Sam Hopkins | @lambda: yes, that would be the ideal situation, if the maximum $k$ for which a $k$-clock exists was the gcd of $\langle v, \mathbf{1}\rangle$ for $v\in\mathrm{ker}(H^t)$. I think it's possible to give a combinatorial description of the generators of $\mathrm{ker}(H^t)$ (and by the way if $G$ is strongly connected then this kernel should be generated by a single primitive vector). | |
| Apr 5, 2021 at 21:18 | comment | added | lambda | If there exist clocks modulo coprime numbers $k$ and $\ell$ then there is also one mod $k\ell$ by the chinese remainder theorem, and clearly a clock mod $k$ will also work mod any divisor of $k$. So the finiteness actually implies there is some $m$ such that the integers for which clocks exist are exactly the divisors of $m$. Your argument shows that $m$ divides $\langle v, \mathbf 1 \rangle$ for all $v \in \operatorname{Ker} H^T$. So I guess the optimistic conjecture would be that it equals the gcd of these. (For undirected graphs this is just the number of vertices.) | |
| Apr 5, 2021 at 18:01 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
added 499 characters in body
|
| S Apr 5, 2021 at 17:45 | history | answered | Sam Hopkins | CC BY-SA 4.0 | |
| S Apr 5, 2021 at 17:45 | history | made wiki | Post Made Community Wiki by Sam Hopkins |