6. First subexponential bounds.
Proposition 1:
How to prove it: This is easy to prove: Given two sets and
in our family
, we first find a path of the form
where,
and
. We let
with
and consider the family
. This is a family of
-subsets of an
set (
) . It follows that we can have a path from
to
in
of length at most
. 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 , and it used something a bit more sophisticated. Applying Proposition 1 directly for
does not give anything non trivial. However, when
is small compared to
and
is a small fraction of
we can say something.
Let us start with an example: . let us choose
. Consider a path
in
from two sets
and
. Suppose also that in this path
(*) , for every
.
Let be the last set in the path whose intersection with
has at least
elements. Let
be the last set in the path whose intersection with
has at least
elements. I claim that
is a path in
.
To see this note that must contain
new elements not already in
. Next
must contain at least d/2 elements not already in
and
. Together the three sets
must therefore contain at least
elements. This means that their union has at least
elements, hence their union contains at least
elements from
and by (*)
and
share at least
elements. Sababa.
This argument extends to the following proposition:
Proposition 2: .
So what? How to use these propositions: Remember that the bound to beat was (actually, Larman improved it to
, but in any case, it is exponential in
.) Applying the two propositions and the trivial bound
we can get
Proposition 3: .
What else? There is a little more to be said. The problem we face using Propositions 1 and 2 is that the ratio between and
may deteriorate. Once
is large compared with
the situation is hopeless. But if we force the ratio between
and
to be bounded also for families
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 be a simple
-polytope and suppose that for every face
of
the number of facets of
is at most
. Then the diameter of the graph of
is at most
. Here
.
For it is not hard to see that
has a diameter at most 2 and to then deduce that the graph of the polytope has diameter at most
.
Reminder: Our Diameter problem for families of sets and some notations and basic observations.
Consider a family of subsets of size d of the set N={1,2,…,n}.
Associate to a graph
as follows: The vertices of
are simply the sets in
. Two vertices
and
are adjacent if
.
For a subset let
denote the subfamily of all subsets of
which contain
.
MAIN ASSUMPTION: Suppose that for every for which
is not empty
is connected.
MAIN QUESTION: How large can the diameter of be in terms of
and
.
Let us denote the answer by .
More notations and a basic observation from previous parts:
Let be the family obtained from
by removing the elements of A from every set. Note that
. Therefore, the diameter of
is at most
, where
and
is the number of elements in the union of all the sets in
.
We associated more general graphs to as follows: For an integer
define
as follows: The vertices of
are simply the sets in
. Two vertices
and
are adjacent if
. Our original problem dealt with the case
. Thus,
.
Let be the maximum diameter of
in terms of
and
, for all families
of
-subsets of
satisfying our connectivity relations.
Pingback: A Diameter problem (7): The Best Known Bound « Combinatorics and more