A Diameter Problem (2)

2. The connection with Hirsch’s Conjecture

The Hirsch Conjecture asserts that the diameter of the graph G(P) of a d-polytope P with n facets is at most n-d. Not even a polynomial upper bound for the diameter in terms of d and n is known. Finding good upper bounds for the diameter of graphs of d-polytopes is one of the central open problems in the study of convex polytopes. If d is fixed then a linear bound in n is known, and the best bound in terms of d and n is n^{\log d+1}. We will come back to these results later.

One basic fact to remember is that for every d-polytope P, G(P) is a connected graph. As a matter of fact, a theorem of Balinski asserts that G(P)$ is d-connected.

The combinatorial diameter problem I mentioned in an earlier post (and which is repeated below) is closely related. Let me now explain the connection. 

Let P be a simple d-polytope. Suppose that P is determined by n inequalities, and that each inequality describes a facet of P. Now we can define a family \cal F of subsets of {1,2,…,n} as follows. Let E_1,E_2,\dots,E_n be the n inequalities defining the polytope P, and let F_1,F_2,\dots, F_n be the n corresponding facets. Every vertex v of P belongs to precisely d facets (this is equivalent to P being a simple polytope). Let S_v be the indices of the facets containing v, or, equivalently, the indices of the inequalities which are satisfied as equalities at v. Now, let \cal F be the family of all sets S_v for all vertices of the polytope P.

The following observations are easy.  

(1) Two vertices v and w of P are adjacent in the graph of P if and only if |S_v \cap S_w|=d-1. Therefore, G(P)=G({\cal F}).

(2)  If A is a set of indices. The vertices v of P such that A \subset S_v are precisely the set of vertices of a lower dimensional face of P. This face is described by all the vertices of P which satisfies all the inequalities indexed by i \in A, or equivalently all vertices in P which belong to the intersection of the facets F_i for i \in A.

Therefore, for every A \subset N if {\cal F}[A] is not empty the graph G({\cal F}[A]) is connected – this graph is just the graph of some lower dimensional polytope. This was the main assumption in our abstract problem.

Remark: It is known that the assertion of the Hirsch Conjecture fails for the abstract setting. There are examples of families where the diameter is as large as n-(4/5)d.

1. A Diameter problem for families of sets

Let me draw your attention to the following problem:

Consider a family \cal F of subsets of size d of the set N={1,2,…,n}.

Associate to \cal F a graph G({\cal F}) as follows: The vertices of  G({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T|=d-1.

For a subset A \subset N let {\cal F}[A] denote the subfamily of all subsets of \cal F which contain A

MAIN ASSUMPTION: Suppose that for every A for which {\cal F}[A] is not empty G({\cal F}[A]) is connected.

MAIN QUESTION:   How large can the diameter of G({\cal F}) be in terms of d and n.

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

5 Responses to A Diameter Problem (2)

  1. jozsef says:

    Dear Gil,

    Thank for the exciting post! I have a question; Don’t you have a stronger assumption (if needed) that G(F[A]) is at least |F[A]|-connected?

  2. Andy D says:

    Hi Gil,
    Yes, very nice posts!

    By the ‘abstract setting’ for which HC fails, do you mean the ‘Main Question’ at the end of the post? If not, what are best known bounds for the Main Question?
    Thanks!

  3. Gil Kalai says:

    Dear Jozsef, yes, we can make this stronger assumption but I do not know how to use it. (I am also not entirely sure it is really stronger.)

    Dear Andy, right, there are examples for the “main question” where the diameter is n-4d/5 (or so). These examples arise from graphs of unbounded simple polyhedra.

  4. Pingback: A Diameter Problem (5) « Combinatorics and more

  5. Pingback: A Diameter problem (7): The Best Known Bound « 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