A Diameter Problem (5)

6. First subexponential bounds.

Proposition 1: $F(d,n) \le F_k(d,n) \times F(d-k,n-k).$

How to prove it: This is easy to prove: Given two sets $S$ and $T$ in our family $\cal F$ , we first find a path of the form $S=S_0, S_1, S_2, \dots, S_t = T$ where, $|S_{i-1} \cap S_i| \ge k$ and $t \le F_k(d,n)$ . We let $B_i \subset (S_{i-1} \cap S_i )$ with $|B_i|=k$ and consider the family ${\cal F}'[B_i]$ . This is a family of $(d-k)$ -subsets of an $(n-k)$ set ( $N \backslash B_i$ ) . It follows that we can have a path from $S_{i-1}$ to $S_i$ in $G({\cal F}[B_i])$ of length at most $F(d-k,n-k)$ . Putting all these paths together gives us the required result. (We remind the notations at the end of this post.)

How to use it: It is not obvious how to use Proposition 1. Barnette’s argument from part 3 was about $k=1$ , and it used something a bit more sophisticated. Applying Proposition 1 directly for $k=1$ does not give anything non trivial. However, when $n$ is small compared to $d$ and $k$ is a small fraction of $d$ we can say something.

Let us start with an example: $n = 3d$ . let us choose $k= d/4$ . Consider a path $S=S_0,S_1,\dots S_t=T$ in $G({\cal F})$ from two sets $S$ and $T$ . Suppose also that in this path

(*) $S_i \cap T \subset S_{i+1}\cap T$ , for every $i$ .

Let $U_1$ be the last set in the path whose intersection with $S$ has at least $d/4$ elements. Let $U_2$ be the last set in the path whose intersection with $U_1$ has at least $d/4$ elements. I claim that $S, U_1, U_2, T$ is a path in $G_{d/4}({\cal F})$ .

To see this note that $U_1$ must contain $3d/4$ new elements not already in $S$ . Next $U_2$ must contain at least d/2 elements not already in $S$ and $U_1$ . Together the three sets $S, U_1, U_2$ must therefore contain at least $d+3d/4+d/2$ elements. This means that their union has at least $9/4d$ elements, hence their union contains at least $d/4$ elements from $T$ and by (*) $U_3$ and $T$ share at least $d/4$ elements. Sababa.

This argument extends to the following proposition:

Proposition 2: $F_{d/(2r-2)} F(d,rd) \le r$ .

So what? How to use these propositions: Remember that the bound to beat was $3^d n$ (actually, Larman improved it to $2^d n$ , but in any case, it is exponential in $d$ .) Applying the two propositions and the trivial bound $F(d,n) \le {{n} \choose {d}}$ we can get

Proposition 3: $F(d,n) \le n^{2 \sqrt n}$ .

Can we automatize it? Let me return to the question of whether such arguments can be automatized. The above argument for Proposition 2 was simple but somewhat ad hoc. You can get a slightly worse upper bound by noting that if $\cal F$ is a family of $d$ -subsets of an n-set and $n \le rd$ , then $G_{d/2r-1}({\cal F})$ does not contain an independent set of size $2r-1$ . Just use the fact that $S_1 \cup S_2 \cup \dots \cup S_t \ge td-{{t} \choose {2}} d/(2r-1)$ . This implies that its diameter is not larger than $4r-4$ . The bound on the independence set based on a standard estimetes for union of sets and the connection between the diameter and the independence number both look rather automatable. So is “thinking about” and proving Proposition 1 and deducing Proposition 3. (But I must admit that overall I am less optimistic about the ability to make these very elementary attacks on the problem automatic.)

What else? There is a little more to be said. The problem we face using Propositions 1 and 2 is that the ratio between $d$ and $n$ may deteriorate. Once $n$ is large compared with $d$ the situation is hopeless. But if we force the ratio between $n$ and $d$ to be bounded also for families ${\cal F}'[A]$ we can get better (polynomial!!) bounds. I will state these bounds for polytopes keeping in mind the simple connection between the abstract problem and the diameter problem for graphs of polytopes.

Proposition: Let $P$ be a simple $d$ -polytope and suppose that for every face $F$ of $P$ the number of facets of $F$ is at most $r \dim F$ . Then the diameter of the graph of $P$ is at most $d^{c(r)}$ . Here $c(r) = K r \log r$ .

For $r=2$ it is not hard to see that $G_{d/2}$ has a diameter at most 2 and to then deduce that the graph of the polytope has diameter at most $d$ .

Reminder: Our Diameter problem for families of sets and some notations and basic observations.

Consider a family $\cal F$ of subsets of size d of the set N={1,2,…,n}.

Associate to $\cal F$ a graph $G({\cal F})$ as follows: The vertices of $G({\cal F})$ are simply the sets in $\cal F$ . Two vertices $S$ and $T$ are adjacent if $|S \cap T|=d-1$ .

For a subset $A \subset N$ let ${\cal F}[A]$ denote the subfamily of all subsets of $\cal F$ which contain $A$ .

MAIN ASSUMPTION: Suppose that for every $A$ for which ${\cal F}[A]$ is not empty $G({\cal F}[A])$ is connected.

MAIN QUESTION: How large can the diameter of $G({\cal F})$ be in terms of $d$ and $n$ .

Let us denote the answer by $F(d,n)$ .

More notations and a basic observation from previous parts:

Let ${\cal F'}[A]$ be the family obtained from ${\cal F}[A]$ by removing the elements of A from every set. Note that $G({\cal F}[A]) = G({\cal F}' [A])$ . Therefore, the diameter of $G({\cal F}[A])$ is at most $F(d',n')$ , where $d'= d-|A|$ and $n'$ is the number of elements in the union of all the sets in $G({\cal F}'[A])$ .

We associated 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})$ .

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.

About these ads

One Response to A Diameter Problem (5)

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

	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Jon Awbrey on Influence, Threshold, and…