Diameter Problem (4)

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

One thought on “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:

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