Timeline for Mod $2$ of $\#PM(G)$ for arbitrary G?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 15, 2019 at 19:48 | comment | added | Turbo | Thank you that helped. | |
| Jul 15, 2019 at 19:39 | comment | added | darij grinberg | Are you asking about the number of perfect matchings modulo $2$ ? Because in that case, as @NoamD.Elkies suggested, that number (or, rather, a number congruent to it modulo $2$) can be computed as the Pfaffian of the skew adjacency matrix (= the result of replacing all $1$s by $-1$s below the diagonal of the adjacency matrix) of the graph. Thus, it can also be computed as the determinant of this matrix (in fact, the determinant is the square of the Pfaffian, and therefore congruent to the Pfaffian modulo $2$). See Theorem 12.81 in Nicholas Loehr, Bijective Combinatorics, 1st edition 2011. | |
| Jul 13, 2019 at 13:40 | comment | added | Turbo | @NoamD.Elkies Since I do not know I want to clarify. It seems $Pf(A)^2=det(A)$ for skew-symmetric $A$ and since signs are removed here $A$ is not skew-symmetric. However $\mod 2$ signs do not matter. So just $det(A)\bmod 2$ gives necessary $\#PM(G)\bmod 2$ of graph $G$ whose adjacency is $A$? | |
| Jul 13, 2019 at 7:22 | history | edited | YCor |
edited tags
|
|
| Jul 13, 2019 at 0:15 | comment | added | Noam D. Elkies | The Hafnian <en.wikipedia.org/wiki/Hafnian> is congruent mod 2 to the Pfaffian (same terms but no +/- signs) and gives the number of matchings in general, as the permanent does for a bipartite graph (and indeed the permanent and determinant are likewise congruent mod 2). The special property of planar graphs is that the +/- signs are all the same so the Pfaffian gives the actual number, not just the parity. | |
| Jul 12, 2019 at 23:31 | comment | added | Turbo | @NoamD.Elkies Thank you but link references planar graphs. | |
| Jul 12, 2019 at 22:59 | comment | added | Noam D. Elkies | Same formula, via the Pfaffian mod 2? en.wikipedia.org/wiki/Pfaffian | |
| Jul 12, 2019 at 22:11 | history | asked | Turbo | CC BY-SA 4.0 |