Helly’s Theorem, “Hypertrees”, and Strange Enumeration I

1. Helly’s theorem and Cayley’s formula

Helly’s theorem asserts: For a family of n convex sets in , n > d, if every d+1 sets in the family have a point in common then all members in the family have a point in common.

Cayley’s formula asserts: The number of  trees on n labelled vertices is .

In this post (in two parts) we will see how an extension of Helly’s theorem has led to high dimensional analogs of Cayley’s theorem.

  

left: Helly’s theorem demonstrated in the Stanford Encyclopedia of Philosophy (!), right: a tree 

2. Background

This post is based on my lecture at Marburg. The conference there was a celebration of new doctoral theses in discrete mathematics, so I decided to devote my lecture to my own graduate years. I studied at the Hebrew University of Jerusalem and my supervisor was Micha. A Perles. I did my master’s thesis and some research as an undergraduate with Micha’s supervision, and it is correct to say that Perles educated me as a mathematician.

Among my older “academic brothers” are Meir Katchalski, Michael Kallay (in Hebrew we have the same last name), and Nati Linial who graduated a couple of years before me. Noga Alon was an academic twin, and, among academic brothers whose graduate years overlapped with mine, were Ido Shemer and Yaakov Kupitz. Later, Perles and I had three joint graduate student,, the first of whom was Ron Adin. We had (and still do) a lovely “combinatorics and convexity seminar” on Monday mornings, and many other mathematical activities.

3. The Katchalski-Perles conjecture

Suppose you have a family of n convex sets in  such that no more than m of them have a point in common (m>d). What is the maximum number of intersecting (d+1)-tuples of sets from the family?

The proposed extreme example was this: Take m-d copies of itself and n-m+d hyperplanes in general position. Among the hyperplanes, at most d have non empty intersection. Therefore, altogether you will not have more than m sets in the family with non-empty intersection. So the proposed answer is: .

This conjecture was proposed by Katchalski and Perles around 1980. Note the following two extreme cases of the conjecture: If m=n-1 you go back to Helly’s theorem. The other extreme case is m=d+1, and in the rest of this post we will discuss this case.

4. Nerves and face numbers

The nerve N of a family of sets   in an abstract simplicial complex whose vertices are labelled with {1,2,…,n} which record the intersection pattern of the sets. S belongs to the nerve if . The nerve is a simplicial complex, namely a family of sets closed under taking subsets. Another piece of useful notation is this: for a simplicial complex K, denote by the number of i-faces of K. An i-face is simply a set with For the nerve N of a family of sets, is the number of (i+1)-tuples of sets in the family with non empty intersection.

5. Collapse of nerves

Suppose we have a family of n convex sets in and no d+2 of them have a point in common. A theorem of Wegner asserts that the nerve N of the family can be collapsed to its (d-1)-dimensional skeleton. In other words, we can delete all the d-dimensional faces (sets of size d+1) from the complex by repeating the following operation, which is called an elementary collapse.

Find a (d-1)-face that belongs to a unique d-face and delete both these faces from the simplicial complex.

In particular, this implies that the d-th homology of the nerve (say with coefficients modulo 2) vanishes. This vanishing of homology follows also (even in the greater generality of nerves of good covers of a subset of  ) from the nerve lemma.

6. Perles’ observation

Now consider the incidence matrix A between (d-1)-faces and d-faces of the nerve N. Think about this matrix over the field of two elements Z/2. Namely, A is a matrix whose rows correspond to (d-1)-faces of N, and whose columns correspond to d-faces of N, and the entry is 1 if the d-face that corresponds to the row contains the (d-1)-face corresponding to the column, and 0 otherwise. The d-th homology with Z/2 coefficients corresponds to linear dependencies among the columns. (Because we assumed that there are no faces of dimension >d.)

Our nerve has n vertices. (Because the family of convex sets has n members.) If you take the incidence matrix for all possible (d-1)-faces (d-subsets) and all possibled-faces (=(d+1)-subsets) the rank of this matrix is . To see that the rank is not larger, note that the rows corresponding to sets containing ‘n’, linearly depend on the other rows. To see that the rank is not smaller note that rows corresponding to all d-sets not containing n together with columns corresponsing to all (d+1)-sets containing ‘n’ give us an identity square matrix of size .

Now, for the incidence matrix A coming from the nerve N of our family of convex sets, we know that the columns are linearly independent. Therefore, an upper bound on the rank gives us the same upper bound on the number of columns. This proves that a family of n convex sets in whose nerve N satisfies (i.e., no d+2 sets in the family have a point in common), satisfies .  This is Perles’ proof of the case m=d+1 of his conjecture with Katchalski.

What are the cases of equality?, we can ask.

7. What are hypertrees and a conjecture about their number

For the very special case of d=1, m=3, the topological condition of being collapsible (or of vanishing first homology group) gives us the family of forests. If we insist on having we get the family of trees. Those are nice objects that we like! (and like to count.) (Nerves N of families of intervals on the line, no three of them intersect, with , are special types of trees called caterpillars.) Also, for larger dimensions, if we have equality    it follows (using the Euler-Poincaré formula) that the (reduced) Betti numbers of N vanish.

So we can speculate that collapsible complexes, or perhaps acyclic simplicial complexes K of dimension d which satisfy  are some sort of “hypertrees” and that we should try to enumerate them á la Cayley. Some inspections suggest that their number should be: .

Cayley’s theorem, the case of at most 4 vertices. This picture (from Wikipedia) describes the labelled trees on 2,3 and 4 vertices. On 4 labelled vertices there are four 2-dimensional “hypertrees”, each corresponding to taking 3 out of the 4 triangles in the boundary of a tetrahedron. This agrees with the conjectural formula.

8. Why the conjecture cannot work

The first place to try this conjecture is when the dimension is 2. The conjecture is true when n is at most 5. With six vertices there are some difficulties. The number of collapsible two dimensional simplicial complexes with complete first dimensional skeletons on 6 verticesis 46608. This comes 48 short of the conjecture which is = 46656. There are also 12 triangulations of the real 2-dimensional projective plane. Their status is negotiable. We may consider them as two dimensional hypertrees since their second homology groups vanish. But even with them we are short. All other simplicialcomplexes with 6 vertices, 10 triangles and complete one-dimensional skeletons have non zero second homology and are disqualified as hypertrees. Ethan Bolkercame to the same conjecture several years earlier while studying generalization of the transportation polytopes. He had also made similar conjectures for multicolored “hypertrees”. But the case n=6 convinced Bolker that these conjectures are false.

The 6-vertex triangulation of is obtained by identifying opposite verices in the Icosahedron. The group of automorphism of this triangulation has 60 elements and therefore there are 12 such triangulations on 6 labeled vertices.

There is something even worse. The ratio between the number of “hypertrees” according to our conjecture and the total number of simplicial complexes with precisely d-faces (and complete (d-1)-dimensional skeletons), behaves like . For d>1 this is a huge number. If any sort of enumeration of hypertrees gives the formula we conjectured, this ratio should better have been below 1.

We have strong evidence against a  conjecture.

What can we do???  (…to be continued)

(few typos corrected, June 18)

Update: I saw a slightly similar tree in Tel Aviv…