Diameter Problem (4)

Posted on September 9, 2008 by

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? 

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

One Response to Diameter Problem (4)

  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:

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

Cancel

Connecting to %s