Helly’s Theorem, “Hypertrees”, and Strange Enumeration II: The Formula

In the first part of this post we discussed an appealing conjecture regaring an extension of Cayley’s counting trees formula. The number of d-dimensional “hypertrees” should somehow add up  to n^{{n-2} \choose {d}}. But it was not clear to us which complexes we want to count and how. This counting problem started from a Helly type conjecture proposed by Katchalski and Perles.
For d=2 n=6 the situation was confusing. We had 46608 complexes that were collapsible. Namely, for these complexes it is possible to delete all triangles one at a time by removing in each step a triangle T and an edge E which is contained only in T. Once all triangles are removed we are left with a spanning tree on our 6 vertices. (Five out of the 15 edges survive).  In addition, there were 12 simplicial complexes representing 6-vertex triangulations of the real projective plane. 
We will continue the discussion in this part, show how the conjecture can be saved and at what cost. We will also discuss the solution of the Perles-Katchalski conjecture –  a Helly’s type conjecture that we started with.   In the third part we will explain the proof and mention further related results and problems, discuss higher Laplacians and their spectrum, and mention a few related probabilistic problems.  

 We ended part one with the question “What can we do?”

8. How to make the conjecture work

With such a nice conjecture we should not take no for an answer. To make the conjecture work we need to count each of the twelve 6-vertex triangulations of the real projective plane, four times. Four is the square of the number of elements in H_1(RP^2). This is the difference in higher dimensions, a Q-acyclic complex need not be Z-acyclic. Homology groups can have non trivial torsion.  In our case H_{d-1}(K) can be a non trivial finite group.
Here is the theorem:   

\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 and more), which one (or more) would you expect to extend to the high dimensional case? We will answer this question in part III. Can you guess?
Like in the case of trees we can extend the result and count these “hypertrees” according to the vertex degrees. The degree d(i) of vertex i, is the number of d-faces containing it. The more general formula asserts that:
\sum |H_{d-1}(K,{\bf Z})|^2 x_1^{d(1)} x_2^{d(2)} \dots x_n^{d(n)} =  x_1^{{n-2} \choose {d-1}} x_2^{{n-2} \choose {d-1}} \dots x_n^{{n-2} \choose {d-1}} (x_1+x_2+ \dots x_n)^{{n-2} \choose {d}}.
Again the sum is over all Q-acyclic d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton.

9. The Perles Katchalski conjecture

The Perles-Katchalski conjecture was solved independently by Jurgen Eckhoff and by me. Let \cal F  be a family of n convex sets in R^d, and let K be the nerve of the family. (The simplicial complex that records non empty intersections). If \dim K \le d+r then f_d(K) \le {{n} \choose {d+1}} - {{n-r} \choose {d+1}}. (f_d(K) is the number of d-faces of the nerve K and it is the number of (d+1)-tuples of sets in the family with non empty intersection.)
Equality holds, for example, for the nerve of the following example mentioned in Part I:  Take r copies of R^n itself and n-r hyperplanes in general position.
Both proofs relied on collapsability properties of the nerve. My solution used incidence matrices which extend those coming from homology theory. Eckhoff’s solution was purely geometric/combinatorial. The theorem extends further when collapsability is replaced by a homological more general condition.  

10. Contractible non-Collapsible simplicial complexes

A simplicial complex K is collapsible if it can be reduced to a point by repeatedly applying elementary collapses. An elementary collapse is the deletion of two faces F and G. G is a minimal face, and F is a face of codimension one in G which is not included in any other maximal face. Collapsible simplicial complexes are contractible and it is not obvious at all that there are contractible non collapsible complexes. Here are 2 famous examples.

We can ask: Among the 2-dimensional simplicial complexes with n vertices and {n-1} \choose {2} triangles, are most contractible complexes non-collapsible? are most Z-acyclic complexes not contractible, and are most Q-acyclic complexes not Z-acyclic? Probably the answer is yes to all three problems but it is not known.

Dunce hat: a contractible non-collapsible simplicial complex (above) and some other dunce hats (below)

Bing’s house: a contractible but non-collapsible complex.

About these ads
This entry was posted in Combinatorics, Convexity and tagged , , . Bookmark the permalink.

4 Responses to Helly’s Theorem, “Hypertrees”, and Strange Enumeration II: The Formula

  1. Pingback: Plans and Updates « Combinatorics and more

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

  3. Pingback: Lawler-Stroock-Kozdron’s combined Proof for the Matrix-Tree theorem and Wilson’s Theorem | Combinatorics and more

  4. Pingback: More around Borsuk | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s