A Diameter Problem (5)

6. First subexponential bounds. 

Proposition 1: F(d,n) \le F_k(d,n) \times F(d-k,n-k).

How to prove it: This is easy to prove: Given two sets S and T in our family \cal F, we first find a path of the form S=S_0, S_1, S_2, \dots, S_t = T where, |S_{i-1} \cap S_i| \ge k and t \le F_k(d,n). We let B_i \subset (S_{i-1} \cap S_i ) with |B_i|=k and consider the family {\cal F}'[B_i]. This is a family of (d-k)-subsets of an (n-k) set (N \backslash B_i) . It follows that we can have a path from S_{i-1} to S_i in  G({\cal F}[B_i]) of length at most F(d-k,n-k). Putting all these paths together gives us the required result. (We remind the notations at the end of this post.)

How to use it: It is not obvious how to use Proposition 1. Barnette’s argument from part 3 was about k=1, and it used something a bit more sophisticated. Applying Proposition 1 directly for k=1 does not give anything non trivial. However, when n is small compared to d and k is a small fraction of d we can say something.

Let us start with an example: n = 3d. let us choose k= d/4. Consider a path S=S_0,S_1,\dots S_t=T in G({\cal F}) from two sets S and T. Suppose also that in this path 

(*) S_i \cap T \subset S_{i+1}\cap T, for every i

Let U_1 be the last set in the path whose intersection with S has at least d/4 elements.  Let U_2 be the last set in the path whose intersection with U_1 has at least d/4 elements. I claim that S, U_1, U_2, T is a path in G_{d/4}({\cal F}).

To see this note that U_1 must contain 3d/4 new elements not already in S. Next U_2 must contain at least d/2 elements not already in S and U_1. Together the three sets S, U_1, U_2 must therefore contain at least d+3d/4+d/2 elements. This means that their union has at least 9/4d elements, hence their union contains at least d/4 elements from T and by (*) U_3 and T share at least d/4 elements. Sababa.

This argument extends to the following proposition: 

Proposition 2: F_{d/(2r-2)} F(d,rd) \le r.

So what? How to use these propositions: Remember that the bound to beat was 3^d n (actually, Larman improved it to 2^d n, but in any case, it is exponential in d.) Applying the two propositions and the trivial bound F(d,n) \le {{n} \choose {d}} we can get

Proposition 3: F(d,n) \le n^{2 \sqrt n}

Can we automatize it? Let me return to the question of whether such arguments can be automatized.  The above argument for Proposition 2 was simple but somewhat ad hoc. You can get a slightly worse upper bound by noting that if \cal F is a family of d-subsets of an n-set and n \le rd, then G_{d/2r-1}({\cal F}) does not contain an independent set of size 2r-1. Just use the fact that S_1 \cup S_2 \cup \dots \cup S_t \ge td-{{t} \choose {2}} d/(2r-1). This implies that its diameter is not larger than 4r-4. The bound on the independence set based on a standard estimetes for union of sets and the connection between the diameter and the independence number both look rather automatable. So is “thinking about” and proving Proposition 1 and deducing Proposition 3. (But I must admit that overall I am less optimistic about the ability to make these very elementary attacks on the problem automatic.)

What else? There is a little more to be said. The problem we face using Propositions 1 and 2 is that the ratio between d and n may deteriorate. Once n is large compared with d the situation is hopeless. But if we force the ratio between n and d to be bounded also for families {\cal F}'[A] we can get better (polynomial!!) bounds. I will state these bounds for polytopes keeping in mind the simple connection between the abstract problem and the diameter problem for graphs of polytopes.

Proposition: Let P  be a simple d-polytope and suppose that for every face F of P the number of facets of F is at most r \dim F. Then the diameter of the graph of P is at most d^{c(r)}. Here c(r) = K r \log r.

For r=2 it is not hard to see that G_{d/2} has a diameter at most 2 and to then deduce that the graph of the polytope has diameter at most d.


Reminder: Our Diameter problem for families of sets and some notations and basic observations.

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

More notations and a basic observation from previous parts:

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]).

We associated more general graphs to \cal F as follows: For an integer k 1 \le k \le d define G_k({\cal F}) as follows: The vertices of  G_k({\cal F}) are simply the sets in \cal F. Two vertices S and T are adjacent if |S \cap T| \ge k. Our original problem dealt with the case k=d-1.  Thus, G({\cal F}) = G_{d-1}({\cal F}).   

Let F_k(d,n) be the maximum diameter of G_k({\cal F})  in terms of k,d and n, for all families \cal F of d-subsets  of N satisfying our connectivity relations.

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

One Response to A Diameter Problem (5)

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