Our Diameter problem for families of sets
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.
We will call a family satisfying this assumption “hereditarily connected”.
MAIN QUESTION: How large can the diameter of be in terms of and ?
We denote the answer by .
For let be the family obtained from by removing from every set. Since , the diameter of is at most .
8. A slight generalization
Let be an hereditarily connected family of -subsets of a set . Let be a subset of . The length of a path of sets modulo Y (where for every ) is the number of such that both and are subsets of . (In other words, in we consider edges between subsets of Y as having length 1 and other edges as having length 0.)
Let be the largest diameter of an hereditarily connected family of -subsets of an arbitrary set modulo a set Y , with .
Since we can always take we have .
9. A quasi-polynomial upper bound
We will now describe an argument giving a quasi-polynomial upper bound for . This is an abstract version of a geometric argument of Kleitmen and me.
Let be a hereditarily connected family of -subsets of some set , let , , and let and be two sets in the family.
Claim: We can always either
1) find paths of length at most modulo Y from to -subsets of whose union has more than elements.
or
2) we can find a path of this length modulo Y from to .
Proof of the claim: Let be the set of elements from that we can reach in steps modulo Y from . (Let me explain it better: is the elements of in the union of all sets that can be reached in steps modulo Y from . Or even better: is the intersection of with the union of all sets in which can be reached from in steps modulo Y. )
The distance of from modulo Z is at most .
Now, if we are in case 1).
If then there is a path from to modulo Z of length . If this path reaches no set containing a point in we are in case 1). (Because this path is actually a path of length from to modulo Y). Otherwise, we reached via a path of length modulo Y from a set containing a point in , in contradiction to the definition of . Walla.
Corollary: .
By a path of length modulo Y we reach from at least elements in , (or ). By a path of length modulo Y we reach from at least elements in , (or ). So unless we can go from to in steps modulo Y we can reach more than elements from both and by paths of length modulo Y ,hence there is some element we can reach from both.
In other words in steps modulo Y we go from to and from to so that and share an element .
But the distance from to modulo Y (which is the same as the distance modulo Y from to in is at most . (We use here the fact that ) Ahla!
To solve the recurrence, first for convenience replace by . (You get a weaker inequality.) Then write to get and to get which gives which in turn gives and . Sababa!
This is the last post in the series. The proof presented here is an abstract version of a geometric proof for graphs of polytopes by Kalai and Kleitman. Different paths to weaker quasi-polynomial upper bounds can be found here. These bounds are linear when is fixed. A similar (even a bit simpler) argument under an even more general context was found by Razborov. (But I don’t remember it at present.) The argument above extends to the directed case. But finding an actual pivot rule for the simplex algorithm which comes close to this bound is out of reach.
I conjecture that is polynomial (and that this holds for and even in the greater generality considered by Razborov). I also conjectured before that it is not a polynomial, but changed my mind. So frankly, I do not have a clue. Remember that it is even possible that .
Summary of earlier posts: Part 1 describes the problem. (It is repeated here.) Part 2 describe the connection to the Hirsch Conjecture. Part 3 describes linear bound when is fixed. It also raises the question if past (or future) developements on the problem can be quasi-automatize. Part 5 follows a question from part 4 and describes a subexponential upper bound. Part 6 describes further the connection with linear programming and with shellability, and poses a directed version of the problem.
Pingback: The Polynomial Hirsch Conjecture: A proposal for Polymath3 « Combinatorics and more