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.

One Response to A Diameter Problem (5)

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

	Gil Kalai on Jirka
	Gil Kalai on Greg Kuperberg: It is in NP to…
	Joseph Malkevitch on Jirka
	Joseph Malkevitch on Jirka
	C r i s t i a n a * on Jirka
	eczema treatment on Polymath10: The Erdos Rado Del…
	Seva on Extremal Combinatorics III: So…
	Boris Bukh on Seven Problems Around Tverberg…
	Boris Bukh on Seven Problems Around Tverberg…
	dinostraurio on Seven Problems Around Tverberg…
	Rupei Xu on AviFest, AviStories and Amazin…
	AviFest, AviStories… on Combinatorics, Mathematics, Ac…