My Mathematical Dialogue with Jürgen Eckhoff

Jürgen Eckhoff, Ascona 1999

Jürgen Eckhoff is a German mathematician working in the areas of convexity and combinatorics. Our mathematical paths have met a remarkable number of times. We also met quite a few times in person since our first meeting in Oberwolfach in 1982. Here is a description of my mathematical dialogue with Jürgen Eckhoff:

Summary 1) (1980) we found independently two proofs for the same conjecture; 2) (1982) I solved Eckhoff’s Conjecture; 3) Jurgen (1988) solved my conjecture; 4) We made the same conjecture (around 1990) that Andy Frohmader solved in 2007,  and finally  5) (Around 2007) We both found (I with Roy Meshulam, and Jürgen with Klaus Peter Nischke) extensions to Amenta’s Helly type theorems that both imply a topological version.

(A 2009 KTH lecture based on this post or vice versa is announced here.)

Let me start from the end: 

5. 2007 – Eckhoff and I  both find related extensions to Amenta’s theorem.

Nina Amenta

Nina Amenta proved a remarkable extension of Helly’s theorem. Let \cal F be a finite family with the following property:

(a) Every member of \cal F is the union of at most r pairwise disjoint compact convex sets.

(b) So is every intersection of members of \cal F.

(c) |{\cal F}| > r(d+1).

If every r(d+1) members of \cal F has a point in common, then all members of \cal F have a point in common!

The case r=1 is Helly’s theorem, Grünbaum and Motzkin proposed this theorem as a conjecture and proved the case r=2. David Larman  proved the case r=3.

roy

Roy Meshulam

Roy Meshulam and I studied a topological version of the theorem, namely you assume that every member of F is the union of at most r pairwise disjoint contractible compact sets in $R^d$ and that all these sets together form a good cover – every nonempty intersection is either empty or contractible. And we were able to prove it!

Eckhoff and Klaus Peter Nischke looked for a purely combinatorial version of Amenta’s theorem which is given by the old proofs (for r=2,3) but not by Amenta’s proof. An approach towards such a proof was already proposed by Morris in 1968, but it was not clear how to complete Morris’s work. Eckhoff and Nischke were able to do it! And this also implied the topological version for good covers.

The full results of Eckhoff and Nischke and of Roy and me are independent. Roy and I showed that if the nerve of \cal G is d-Leray then the nerve of \cal F is ((d+1)r-1)-Leray. Eckhoff and showed that if the nerve of \cal G has Helly number d, then the nerve of \cal F has Helly number (d+1)r-1. Amenta’s argument can be used to show that if the nerve of \cal G is d-collapsible then the nerve of F is  ((d+1)r-1)-collapsible.

Here, a simplicial comples K is d-Leray if all homology groups H_i(L) vanishes for every i \ge d and every induced subcomplex L of K.

Roy and I were thinking about a common homological generalization which will include both results but so far could not prove it.

 

And now let me move to the beginning:

1. 1981 – we give different proofs for the Perles-Katchalski Conjecture

Katchalski

Meir Katchalski

The Perles-Katchalski conjecture asserts that:

Suppose you have a family of n convex sets in R^n  such that no more than m of them have a point in common (m>d). Then the maximum number of intersecting (d+1)-tuples of sets from the family is: {{n} \choose {d+1}} - {{n-m+d} \choose {d+1}}.
An extreme example is this: Take m-d copies of R^n 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: {{n} \choose {d+1}} - {{n-m+d} \choose {d+1}}.

This conjecture was proposed by Katchalski and Perles around 1980.

 

perles

Micha A. Perles

Both Eckhoff and I solved this conjecture in different ways in 1981. My solution used linear algebra techniques and a notion of collapsibility. Jurgen’s solution was elementary and used a stronger form of collapsibility; his proof is similar to McMullen’s proof of the “upper bound theorem” for polytopes that uses a strong version of shellability. A simple version of my approach based on a “skew two-family theorem” was found by Noga Alon and me and it led Noga and I to a new proof of the upper bound theorem for polytopes, again based on shellability. (We had a series of posts related to the Katchalski-Perles conjecture and enumeration of high dimensional trees.)

Alon_Noga

Noga

2. 1983 – I solve Eckhoff’s conjecture

Eckhoff proposed a complete characterization of f-vectors of nerves of families of convex sets, and solved the planar case. I solved it in my Ph. D. thesis.  It is a little complicated to formulate but it is close in spirit (but is easier) to the g-conjecture that we are discussing here (and here and here).

3. 1988 –  Eckhoff solves my conjecture

Let K be the nerve of a family of standard boxes in {\bf R}^d. Standard boxes have Helly number 2: For a family of standard boxes if every two boxes have a point in common, then all boxes in the family have a point in common. (We say that such a family has Helly number 2.)  We can ask: suppose that no k+1 boxes have a point in common, what is the maximum number of j-tuples of boxes with non-empty intersection.

I conjectured that an extreme family looks like this: You take k-1 copies of R^d and then you take hyperplanes. An equal number (or as close as possible to an equal number) of parallel hyperplane orthogonal to each standard basis element.

Before moving to the last item, let me mention that Jürgen’s work and mine intersect also in more mundane ways. My work with Anders Björner on face numbers and Betti numbers of cell complexes relies on earlier works by Eckhoff and Wegner, my paper with Noga Alon on (p,q) theorems for hyperplane transversals extends an earlier result by Eckhoff: Finally, both Eckhoff and I proposed extensions to Tverberg’s theorem. Eckhoff’s well known “partition conjecture” (disproved by Boris Bukh), and my less known conjecture on the dimension of Tverberg’s points can be found in a post about seven problems around Tverberg’s theorem.

4. Around 1990 – We make independently the same conjecture that Andy Frohmader solves in 2007

In 2007 Andy Frohmader solved a Kruskal-Katona type conjecture that Jurgen and I made around 1990. Here is the paper! As Hendrik Van Maldeghem describes in his review of Andy’s paper: “This conjecture states that, for any graph G with clique number r (where r is the number of vertices in the largest clique of G), there exists a simplicial complex \Delta of dimension r+1 (hence the maximal faces have r elements) whose 1-skeleton, as a graph, has chromatic number r (a so-called balanced complex), and which has equally as many faces of size i as G has cliques of size i, for all i, 0\leq i\leq r.”

frohmader

Andy Frohmader

This result has the important consequence that the entries of the clique vector of any graph satisfy the same inequalities as the entries of the face vector of a balanced simplicial complex (the clique vector is the sequence of natural numbers whose i th entry is the number of cliques of size i-1; similarly for the face vector of a simplicial complex). A characterization (extending the Kruskal-Katona’s theorem) for f-vectors of balanced simplicial complexes was proved by Frankl, Füredi and me.

There are still some important questions related to this conjecture. Frohmader showed that the f-vector of a (d-1)-dimensional clique complex of a graph is the f-vector of a (d-1)-dimensional simplicial complex whose vertices can be properly colored by d colors. Now if the clique complex has the Cohen-Macaulay property, can we achieve it also for the colored complex? Or if the clique complex is r-Leray (see below) can we achieve it also for the colored complex? And can we make sure that the colored complex has the same Betti numbers as the clique complex?

 

About these ads
This entry was posted in Combinatorics, Convex polytopes, Open problems and tagged , , , , , . Bookmark the permalink.

One Response to My Mathematical Dialogue with Jürgen Eckhoff

  1. Paul says:

    Curious paper about one-way functions

    http://hal.archives-ouvertes.fr/hal-01020088

    Do you think so?

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