Gil Kalai’s blog

## A Diameter Problem (5)

Posted on September 16, 2008 by

### 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.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 130, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9273973703384399, "perplexity_flag": "head"}