Diameter Problem (3)

3. What we will do in this post and and in future posts

We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply to the diameter of graphs of simple d-polytopes.

All the methods I am aware of for providing upper bounds are fairly simple.

(1) You think about a strategy from moving from one set to another,

(2) You use this strategy to get a recursive bound,

(3) You solve the recursion and hope for the best.

What I would like you to think about, along with reading these posts, is the following questions:

(a) Can I come up with a different/better strategy for moving from one set to the other?

(b) Can I think about a mathematically more sophisticated way to get an upper bound for the diameter?

(c) Can this process of finding a strategy/writing the associated recurrence/solving the recurrence be automatized? The type of proofs we will describe are very simple and this looks like a nice example for a “quasi-automatic” proof process.

Let me repeat the problem and prove to you a nice upper bound:

Reminder: Our Diameter problem for families of sets

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$ .

Let us denote the answer by $F(d,n)$ .

4. A one line observation.

What the upper bound $F(d,n)$ tells us about the diameter of $G({\cal F}[A])$ ? Let ${\cal F'}[A]$ be the family obtained from ${\cal F}[A]$ by removing the elements of A from every set. Note that $G({\cal F}[A]) = G({\cal F}' [A])$ . Therefore, the diameter of $G({\cal F}[A])$ is at most $F(d',n')$ , where $d'= d-|A|$ and $n'$ is the number of elements in the union of all the sets in $G({\cal F}'[A])$ .

5. Linear bounds for a fixed dimension

Let’s use the following strategy to move from one set to the other.

Given two sets S and T in $\cal F$ we first try to move from S to T using a different type of path. $S_0, S_1, S_2, \dots, S_t$ , where this time $|S_i \cap S_{i+1}| \ge1$ . We will choose such a path with t being as small as possible.

Let $w_i \in S_{i-1} \cap S_{i}, i=1,2,\dots ,t$ . We will consider the families ${\cal F}_i = {\cal F}'[w_i]$ .

The one line observation tells us that the diameter of $G({\cal F}_i)$ is bounded from above by $F(d-1,n_i),$ where $n_i$ the number of elements in the union $X_i$ of all the sets in ${\cal F}_i$ .

We want to prove an upper bound on $F(d,n)$ of the form $c_d \cdot d$ . For this purpose, let us have a closer look at these $n$ sets $X_1, X_2, \dots, X_n$ .

Claim: $X_i \cap X_j = \emptyset$ if $j-i > 2$ .

Proof: Suppose that $y \in (X_i \cap X_j)$ and $j-i>2$ . So there is a set $R \in {\cal F}$ which contains $w_i$ and $y$ , and there is a set $U \in {\cal F}$ which contains both $w_j$ and $y$ . Now we can shortcut! We replace the segment $S_i, S_{i+1}, \dots S_j$ by $S_{i-1},R,U,S_j$ . This will give us a shorter path of the peculiar type we consider here.

The claim implies that every element of N is included in at most three $S_i$ s. We are done! If $F(d-1,n) \le c_{d-1}n$ then we get that the distance between $S$ and $T$ in $G({\cal F})$ is at most $\sum F(d-1,n_i) \le c_{d-1} \sum n_i \le c_{d-1} 3n$ . This gives us $F(d,n) \le 3^d n$ .

This argument is due to Barnette.

Reminder: 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 polytopeP, 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.

About these ads

One Response to Diameter Problem (3)

Pingback: A Diameter problem (7): The Best Known Bound « Combinatorics and more

	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Jon Awbrey on Influence, Threshold, and…

Diameter Problem (3)

3. What we will do in this post and and in future posts