Timeline for Is there Matrix-Tree theorem for counting the bases of a connected matroid?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 4, 2020 at 3:13 | comment | added | Jeremy Martin | In general the number of bases is not the "right" invariant. The core example is the matroid represented by the columns of the top boundary map of the $d$-dimensional skeleton of the $n$-vertex simplex. In 1983 Kalai proved, using Binet-Cauchy, that the "count" of bases is $n^{\binom{n-2}{d}}$ (which reduces to Cayley's theorem for the case $d=1$) --- but you need to weight each basis by the square of the size of the codimension-1 homology of the simplicial complex it generates, and this group starts to be nontrivial at $n=6$ and $d=2$. | |
| Oct 3, 2020 at 1:01 | comment | added | lambda | Regarding maximal vs nonmaximal minors: if the matrix has an $n \times n$ identity matrix as a submatrix then every subdeterminant is (up to sign) equal to a maximal one and the conditions are equivalent. But since you have some invertible $n \times n$ submatrix (with determinant $\pm 1$ by assumption) you can multiply on the left by the inverse to get such a submatrix while leaving the maximal minors unchanged up to sign. So the matroid is still regular in this case. | |
| Oct 2, 2020 at 22:28 | comment | added | Gjergji Zaimi | Am I correct in assuming that there are complexity theoretic reasons for the lack of a general result of this sort? Google seems to suggest that counting bases is #P-complete in general. | |
| Oct 2, 2020 at 22:20 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
deleted 3 characters in body
|
| Oct 2, 2020 at 22:18 | comment | added | lambda | One way to do better than regular matroids is to allow complex matrices where all subdeterminants are zero or have modulus 1. The same Cauchy--Binet argument shows $\det(MM^*)$ counts bases. The matroids representable by this kind of matrix are the sixth-root-of-unity matroids. | |
| Oct 2, 2020 at 20:01 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
added 147 characters in body
|
| Oct 2, 2020 at 13:58 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
edited body
|
| Oct 2, 2020 at 13:52 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
added 1057 characters in body
|
| Oct 2, 2020 at 9:36 | vote | accept | Fedor Petrov | ||
| Oct 2, 2020 at 9:11 | history | answered | Sam Hopkins | CC BY-SA 4.0 |