This is the third and last part of the journey from a Helly type conjecture of Katchalski and Perles to a Cayley’s type formula for “hypertrees”. (On second thought I decided to divide it into two devoting the second to probabilistic questions.) This part will include several diversions, open problems, and speculations.

### 11. How to make it work – the matrix tree theorem

Our high dimensional extension to Cayley’s theorem reads:

where the sum is over all d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton, and which are Q-acyclic, namely all their (reduced) homology groups with rational coefficients vanish.

Looking at the various proofs of Cayley’s formula (there are many many many beautiful proofs), the proof that I know to apply is the one based on the matrix tree theorem.

Consider the signed incidence matrix A’ between all (d+1)-subsets and all d-subsets of {1,2,…,n} that represents the boundary operator of simplicial homology. The rank of this matrix is , and just like in the ordinary matrix tree theorem you delete rows to be left with linearly independent rows. Here you delete all rows corresponding to sets containing ‘n’ and you are left with a matrix A. Now we compute the determinant of directly, and compare the result to a computation based on the Cauchy-Binet Formula.

The eigenvalues of are the eigenvalues of the d-th Laplacian of the complete d-dimensional simplicial complex with n vertices. It is easy to inspect what they are and the determinant of is indeed .

The many square determinants correspond to d-dimensional simplicial complexes K on our labelled set of vertices, which satisfy and . Now if K has non-vanishing d-th homology, the determinant is zero. If K is a Q-acyclic simplicial complex (i.e., its (reduced) homology groups with rational coefficients are trivial) then it has a non zero determinant. So far, it is like trees, but next comes a surprise. The contribution of K is the square of the number of elements in , the (d-1)th homology group of K. This torsion group is finite, but for d >1 it need not be trivial.

Emily Peters presents the matrix-tree theorem. From “The Sarong Theorem Archive” – an electronic archive of images of people proving theorems while wearing sarongs.

### 12. An even simpler use of Cauchy-Binet worth knowing

Consider the matrix A, whose columns are all +1 -1 vectors of length n. Computing , via Cauchy-Binet Formula (or by other easy methods) asserts that the expected value for all +1/-1 matrices behaves roughly like . This was observed by Turan and Szekeres who also found a formula for the sum of the fourth powers of all 0-1 n by n matrices. See a leter paper by Turan. (I am not aware of a similar formula for the fourth power of the size of the homology groups for hypertrees.) Much is known about the determinant and related properties of random 0-1 matrices and the analogy between torsion in the homology groups of random complexes and determinants of random matrices looks like a good analogy.

### 13. Torsion

One consequence of the formula compared to the total number of available simplicial complexes is that the torsion group is typically huge. (For d>1, the expected value of for Q-acyclic complexes counted by the formula, is asymptotically larger than ; I am not aware of explicit examples with such a huge torsion group.)

How should we think about torsion in homology? It seems that thinking about the size of the torsion as a behaving like the determinant of a random matrix, may give a good intuition for many cases.

### 14. Extending other proofs for Cayley’s theorem?

Cayley’s counting trees theorem has many wonderful proofs. Can any other proof extend to the case of Q-acyclic simplicial complexes? For example, one proof relies on the exponential theorem that relates the exponential generating functions for connected and general graphs with a certain property P. (Followed by the Lagrange inversion formula.) Is there an analog of the exponential formula when connectivity is replaced by higher homology? Is there any analog of Prüfer sequences? I am not aware of any other proof that works.

### 15. Weights to the rescue of other conjectures?

Can we use subtle weights to save other promising but false enumerative conjectures? The farthest reaching fantasy in this direction Continue reading →