### 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*

*having length 1 and other edges as having length 0.)*

**Y**asLet 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**from . Or even better: is the intersection of with the union of all sets in which can be reached from in steps

*Y***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**. Otherwise, we reached via a path of length

*Y)***modulo**from a set containing a point in , in contradiction to the definition of .

*Y***Walla**.

**Corollary: **.

By a path of length **modulo Y ** we reach from at least elements in , (or ). By a path of length

**modulo**we reach from at least elements in , (or ). So unless we can go from to in steps

*Y***modulo**we can reach more than elements from both and by paths of length

*Y***modulo**,hence there is some element we can reach from both.

*Y*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**from to in is at most . (We use here the fact that )

*Y***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