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 of subsets of size
of the set
.
Let us now associate 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,
. Barnette proof presented in the previous part refers to
and to paths in this graph.
As before for a subset let
denote the subfamily of all subsets of
which contain
. Of course, the smaller
is the more edges you have in
. It is easy to see that assuming that
is connected for every
for which
is not empty already implies our condition that
is connected for every
for which
is not empty.
Let be the maximum diameter of
in terms of
and
, for all families
of
-subsets of
satisfying our connectivity relations.
Here is a simple claim:
Can you prove it? Can you use it?
Pingback: A Diameter problem (7): The Best Known Bound « Combinatorics and more