Timeline for Chip-firing clocks
Current License: CC BY-SA 4.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12, 2021 at 19:21 | vote | accept | James Propp | ||
| Apr 6, 2021 at 3:14 | vote | accept | James Propp | ||
| Apr 12, 2021 at 19:21 | |||||
| Apr 6, 2021 at 3:11 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
deleted 1 character in body
|
| Apr 5, 2021 at 17:38 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 408 characters in body
|
| Apr 5, 2021 at 17:21 | history | edited | Will Sawin | CC BY-SA 4.0 |
added 554 characters in body
|
| Apr 5, 2021 at 17:15 | comment | added | Sam Hopkins | @JamesPropp: If you throw away the free abelian part in the definition of critical group, then your example has trivial critical group. | |
| Apr 5, 2021 at 17:12 | comment | added | James Propp | I’m also wrong about the cokernel. You have to restrict the action of the map to the codimension-1 subspace ${\bf 1}^\perp$ to get the cokernel to be finite. Isn’t this one definition of the critical group? | |
| Apr 5, 2021 at 17:12 | comment | added | Sam Hopkins | The transpose is not a big issue. But I do think that you're still wrong about the cokernel, it should be $\mathbb{Z}$. The reason you get $18$ clocks is because $\#\mathrm{Hom}(\mathrm{coker}(H),\mathbb{Z}/18) = \#\mathrm{Hom}(\mathbb{Z},\mathbb{Z}/18)=18$, and once you had $1$ you know you'd have this many, as Will explained. But the reason you got any at all was because you found a solution $H (0,1,11) = (1, 19, -53) = (1,1,1) \mod 18$. | |
| Apr 5, 2021 at 17:08 | comment | added | James Propp | Yes, I should’ve taken the transpose, to be consistent with what I wrote earlier. | |
| Apr 5, 2021 at 16:47 | comment | added | Sam Hopkins | What is true is that $(11,5,2)$ generates the kernel of (the transpose of) your matrix, which is I think where the $18$ in your example comes from. | |
| Apr 5, 2021 at 16:43 | comment | added | Sam Hopkins | @JamesPropp: are you sure about that cokernel? First of all I think that since the rows are defining chip-firing equivalence, you really want to compute the cokernel of the transposed matrix. But either way, my computer is telling me that the elementary divisors (i.e. Smith Normal Form) of the matrix are $(1,1,0)$ so that it's cokernel is $\mathbb{Z}$. Definitely $\mathbb{Z}$ is a component of the cokernel since your matrix is singular (as all Laplacians will be: the rows sum to zero)... | |
| Apr 5, 2021 at 16:40 | comment | added | Will Sawin | @JamesPropp I expect one can show that for a random matrix, the obstruction map from the $k$-torsion in the cokernel of the Laplacian to $\mathbb Z/k$ is random in a precise sense. So this is possible when the cokernel has $k$-torsion but gets more and more unlikely as the $k$-torsion grows. | |
| Apr 5, 2021 at 16:30 | comment | added | James Propp | Here’s an example: Consider an irreducible Markov chain with whose transition matrix, rescaled to have integer entries, has Laplacian $$\left( \begin{array}{ccc} -1 & 1 & 0 \\ 1 & -3 & 2 \\ 3 & 2 & -5 \end{array} \right).$$ The cokernel of this matrix is $\mathbb{Z}/18\mathbb{Z}$, and it has 18 clocks given by linear functions of the form $(x,y,z) \mapsto ax+by+cz$ (mod 18) with $(a,b,c)$ of the form $(a,a+1,a+11)$ (mod 18). | |
| Apr 5, 2021 at 15:32 | comment | added | Sam Hopkins | @JamesPropp: you should look at the comment of lambda. I think it is a much simpler way of thinking about the problem. | |
| Apr 5, 2021 at 15:31 | comment | added | Will Sawin | @JamesPropp If there is a unique stationary distribution, $k$ divides the lcm of the denominators of the probabilities in it, and $k$ is relatively prime to the order of the torsion part of the cokernel, then there is a always a mod $k$ clock. | |
| Apr 5, 2021 at 15:30 | comment | added | Will Sawin | @JamesPropp No. A simple example is a graph on two vertices, $1$ and $2$ with $a$ edges from $1$ to $2$ and $b$ edges from $2$ to $1$ (and self-loops, I guess, to make it outdegree-regular). The cokernel is $\mathbb Z \times \mathbb Z/ \gcd(a,b)$, but one can check that there is a clock of order $k$ if and only if $k$ divides $a+b$ and is prime to $\gcd(a,b)$, using the fact that $\gcd(a,b) (1,-1)$ is equal to the Laplacian applied to a vector whose sum of digits is a unit modulo $a+b$. | |
| Apr 5, 2021 at 15:25 | comment | added | James Propp | If the cokernel is cyclic of order $k$, is there always a mod-$k$ clock? | |
| Apr 5, 2021 at 4:03 | comment | added | Sam Hopkins | It would be interesting if there were a simple way given a graph $G$ to produce a list of the $k$ for which such $f$ exist. I might think about this... | |
| Apr 5, 2021 at 3:24 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
deleted 7 characters in body
|
| Apr 5, 2021 at 3:23 | comment | added | Will Sawin | @SamHopkins Just take $n_i=0$ : ) | |
| Apr 5, 2021 at 3:21 | comment | added | Sam Hopkins | A small nitpick is that since the Laplacian might have some kernel, the cokernel may have some $\mathbb{Z}^r$ component. | |
| Apr 5, 2021 at 3:19 | comment | added | Will Sawin | @SamHopkins I put in the correct criterion one gets from thinking about group cohomology (whose expression doesn't really need group cohomology in this case). This reverses the problem - instead of checking existence by giving an explicit list of $n$ numbers, one can check nonexistence by giving an explicit list of $2n$ numbers - but doesn't give a completely satisfying answer. I don't know if a more satisfying answer is possible. | |
| Apr 5, 2021 at 3:16 | history | edited | Will Sawin | CC BY-SA 4.0 |
deleted 106 characters in body
|
| Apr 5, 2021 at 2:59 | comment | added | Sam Hopkins | Indeed I think the linear requirement makes it a tricky question... | |
| Apr 5, 2021 at 2:58 | comment | added | Will Sawin | @SamHopkins Oh, sorry, I missed the "linear" thing. Will revise... | |
| Apr 5, 2021 at 2:58 | comment | added | Sam Hopkins | Is the $f(x)$ you defined in the 6th paragraph linear though? | |
| Apr 5, 2021 at 2:48 | history | answered | Will Sawin | CC BY-SA 4.0 |