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

Continue reading →