Diameter Problem (4)

Posted on September 9, 2008 by Gil Kalai

Let us consider another strategy to deal with our diameter problem. Let us try to associate other graphs to our family of sets.

Recall that we consider a family \cal F of subsets of size d of the set N= \{ 1,2,\dots, n \}.

Let us now associate  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}). Barnette proof presented in the previous part refers to G_1({\cal F}) and to paths in this graph.  

As before for a subset A \subset N let {\cal F}[A] denote the subfamily of all subsets of \cal F which contain A. Of course, the smaller k is the more edges you have in G_k({\cal F}). It is easy to see that assuming that G_1({\cal F[A]}) is connected for every A for which {\cal F}[A] is not empty already implies our condition that G({\cal F[A]}) is connected for every A for which {\cal F}[A] is not empty.

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.

Here is a simple claim:

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

Can you prove it? Can you use it? 

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

1 Response to Diameter Problem (4)

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

Leave a comment