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?

One Response to Diameter Problem (4)

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

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Google+ account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

	Gil Kalai on Beyond the g-conjecture…
	ianagol on Beyond the g-conjecture…
	j.c. on Beyond the g-conjecture…
	barysorokerlior on Beyond the g-conjecture…
	Gil Kalai on Beyond the g-conjecture…
	barysorokerlior on Beyond the g-conjecture…
	Beyond the g-conject… on Extremal Combinatorics IV:…
	Beyond the g-conject… on F ≤ 4E
	Beyond the g-conject… on Exciting News on Three Dimensi…
	Beyond the g-conject… on A Mysterious Duality Relation…
	Beyond the g-conject… on Euler’s Formula, Fibonac…
	Beyond the g-conject… on Convex Polytopes: Seperation,…