Gil Kalai’s blog

## Helly, Cayley, Hypertrees, and Weighted Enumeration III

Posted on July 3, 2008 by

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:

$\sum |H_{d-1}(K,{\bf Z})|^2 = n^{{n-2} \choose {d}},$

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 ${n-1} \choose {d}$, 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 $det (A \cdot A^{tr})$ directly, and compare the result to a computation based on the Cauchy-Binet Formula.

The eigenvalues of $A \cdot A^{tr}$ 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 $A \cdot A^{tr}$ is indeed $n^{{n-2} \choose {d}}$.

The many square determinants correspond to d-dimensional simplicial complexes K on our labelled set of vertices, which satisfy $f_{d-1}(K) = {{n} \choose {d}}$ and $f_d(K) = {{n-1} \choose {d}}$. 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 $H_{d-1}(K)$, 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 $n \times 2^n$ matrix A, whose columns are all +1 -1 vectors of length n. Computing $det A A^{tr}$, via Cauchy-Binet Formula (or by other easy methods) asserts that the expected value $(det (B))^2$ for all $n \times n$  +1/-1 matrices behaves roughly like $(n!)$. 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 $|H_{d-1}(K,{\bf Z})|^2$ for Q-acyclic complexes counted by the formula, is asymptotically larger than $((d+1)/e)^{{n-2} \choose {d}}$; 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 would be to try to save MacMahon’s conjecture regarding space partitions of the number n. This conjecture is about enumerating spacial arrays of numbers that sum up to n. The conjecture is true for small values of n but fails for larger values. Can subtle weights come to the rescue?  (MacMahon’s conjecture extends the formulas for ordinary partitions and for plane partitions.)

### 16. Incidence matrices

Perles’ observation in the beginning of this story was about the rank of the incidence matrices modulo 2 of k-subsets versus (k+1) subsets of an n element set. This was the starting point for a work by Linial and Rothschild. They asked:  What is the rank of the incidence matrix of $N \choose r$ versus $N \choose k$ modulo p? and gave a complete answer for p=2. Richard Wilson gave a complete answer for general values of p and came quite close  to presenting the “Smith form” of these matrices. Frumkin and Yakir gave representation-theoretic interpretation of Wilson’s result and proved “q-analogs”. Namely they replaced k-subsets of an n-element set by k-dimensional linear (and in a later work affine) subspaces of an n dimensional linear space over a field with q elements. They gave a complete formula when p and q are prime.

### 17. Duality and Self-Dual trees

Here is a very nice notion of duality that occurs in many places. Start with a simplicial complex K on a set X of vertices. Take the family F of all the complements to all sets in K. (This is not a simplicial complex, it is closed under supersets and not under subsets.) Now, take the family K* of all  subsets of X not in F. Formally, $K^*=2^X \backslash$ {$X \backslash S: S \in K$}.

K* is a simplicial complex again. It is the Alexander dual of algebraic topology, and the “blocker” of polyhedral combinatorics.

If n=2d+2 the duals of our hypertrees are also d-dimensional.  Molly Maxwell counted self-dual hypertrees with the same weights we used, and for odd dimensions the count gives precisely the square root of $n^{{n-2} \choose {d}}$. She deduced it from a more general theorem on matroids duality. For even values of d this is not the case but something may still work.

For d=1 the number of self-dual trees (simply stars) on 4 vertices is four the square root of 16 the total number of labelled trees. There is a theorem of Tutte extending this to self dual trees inside self dual planar maps. For d=3 and 8 vertices, the weighted number of all hypertrees is $8^{20}$ and by Maxwell’s theorem the weighted number of self dual ones is $8^{10}$. For d=2, n=6 - the weighted number of hypertrees is $6^6$ and if we exclude the triangulations of the real projective plane we get $6^3$. For d=4 the total weighted sum of hypertrees with 10 vertices is $10^{70}$, and somehow, a clever weighted sum of the self dual ones should give you $10^{35}$.

### 18. The Perles-Katchalski conjecture and associated eumeration problem

The assertion of the Perles-Katchalski conjecture holds for general classes of simplicial complexes described by homological properties, and we can ask again if the extremal examples enumerate nicely.

Let $\cal K$ be the class of (d+r)-dimensional simplicial complexes with the properties that

(L) For every induced subcomplex K’, $H_i(K',Q)=0, i \ge d$

Now, the homological extension of the Perles-Katchalski Theorem asserts that a (d+r)-dimensional simplicial complex K with n vertices satisfying condition (L) has at most  ${{n} \choose {d} } - {{n-r-1} \choose {d}}$ d-dimensional faces.(For r=0 we need not worry about induced subcomplexes since, in this case, non trivial d-th homology for a subcomplex immediately extends to the whole complex.

We can try to “enumerate” simplicial complexes with n labelled vertices satisfying property (L) with precisely ${{n} \choose {d} } - {{n-r-1} \choose {d}}$ d-dimensional faces. (All these complexes will have the same number of i-faces for every i.)

We can expect that an appropriate enumeration of these objects (probably those containing a specific r-face), will give us a formula of the form $m^{{n-2-r} \choose {d}}$, where m is the number of r-dimensional faces of such a simplicial complex K. For the case d=1, no weights are needed and this speculation reduces to a formula of Beineke and Pippert for counting “k-trees”. (We may even expect finer enumeration formulas according to degree-sequences of r-faces; This is known for “k-trees”. See the following paper by C. Rényi and A. Rényi.)

### 19. Adin’s colorful extension.

Ron Adin extended the weighted enumeration of hypertrees to “colored complexes”, thus confirming (with extra weights added) another conjecture of Bolker.

### 20. Gelfand’s question.

Ron Adin gave a lecture about his work in a Stockholm ’89 meeting in combinatorics which was one of the earliest meetings with many participans from Russia, among them Gelfand, Vershik, Zelevinskii, Serganova, and others. Gelfand was excited about combinatorics (or what he regarded as combinatorics) at the time and was quite interested in Adin’s result. One question he asked me was: why is it that in combinatorics there is so much emphasis on graphs compared to higher dimensional objects.

I personally like the combinatorics of high dimensional objects but I could think of three answers. (Gelfand was quite satisfied with them).

a) For many purposes moving from sets to graphs represents a major conceptual jump, more than moving up from graphs to higher dimensional objects.

b) Higher dimensional objects can often be represented by graphs.

c) Many of the miracles of graph theory fail at higher dimensions.

(And here is a post by David Epstein titled “why graphs?”)

Another memory from the 89 conference is this: Israel Gelfand has a somewhat wide-spanned competative nature. Gelfand looked at Ron Adin and asked me: “He is orthodox isn’t he?”, “yes” I replied. Gelfand thought a little and then said: “But not as orthodox as my Dima.”

### Like this:

This entry was posted in Combinatorics, Convexity, Open problems, Probability. Bookmark the permalink.

### 5 Responses to Helly, Cayley, Hypertrees, and Weighted Enumeration III

1. Richard Stanley says:

Gil asks about saving MacMahon’s conjecture on space (or solid) partitions using subtle weights. If the weights are allowed to be subtle enough then there is an answer of sorts. The enumeration of plane partitions follows from the Cauchy identity

$\sum s_\lambda(x)s_\lambda(y) = \prod_{i,j\geq 1} (1 - x_i y_j)^{-1}$

for Schur functions. We substitute $x_i=q^{i-1}$ and $y_i=q^i$ to get MacMahon’s generating function on the right. On the left we get pairs of weighted tableaux that can be merged into a plane partition. (This proof is due to Bender and Knuth.) It is not unreasonable to replace the right-hand side by

$\prod_{i,j,k\geq 1}(1 - x_i y_j z_k)^{-1}.$

If we set $x_i=y_i=q^{i-1}$ and $z_i=q^i$ then we get MacMahon’s incorrect conjectured generating function for solid partitions. What about the left-hand side? If we expand in terms of Schur functions we get

$\sum_{\lambda,\mu,\nu} g_{\lambda,\mu,\nu} s_\lambda(x) s_\mu(y) s_\nu(z),$

where $g_{\lambda,\mu,\nu}$ is the notoriously intractable “Kronecker coefficient,” i.e., the multiplicity of the irreducible character $\chi^\lambda$ of $S_n$ in the tensor (or pointwise) product of $\chi^\mu$ and $\chi^\nu$. Thus solid partitions are replaced by certain triples of tableaux weighted by $g_{\lambda,\mu,\nu}$. This is probably too subtle for most people’s taste, especially since we don’t end up with any kind of solid partition. However, it is a rather natural extension of the elegant proof of Bender and Knuth and suggests why solid partitions may remain forever intractable.

2. Gil Kalai says:

Dear Richard, many thanks!

3. Pingback: Plans and Updates « Combinatorics and more

4. Pingback: A Beautiful Garden of Hypertrees « Combinatorics and more

5. Gil Kalai says:

I think that the “correct” class of simplicial complexes that extends both our hypertrees and Beineke and Pippert’s “k-trees” is the class of Bi-Cohen-Macauly simplicial complexes K. Namely simplicial complexes K such that both K and its Alexander dual are Cohen Macaulay. See, e.g., the paper of Gunnar Floystad, Jon Eivind Vatne
http://arxiv.org/abs/math/0209061

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 45, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.884949266910553, "perplexity_flag": "middle"}