## 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?