A Diamater Problem for Families of Sets.

Let me draw your attention to the following problem:

Consider a family $\cal F$ of subsets of size d of the set N={1,2,…,n}.

Associate to $\cal F$ a graph $G({\cal F})$ as follows: The vertices of $G({\cal F})$ are simply the sets in $\cal F$. Two vertices $S$ and $T$ are adjacent if $|S \cap T|=d-1$.

For a subset $A \subset N$ let ${\cal F}[A]$ denote the subfamily of all subsets of $\cal F$ which contain $A$

MAIN ASSUMPTION: Suppose that for every $A$ for which ${\cal F}[A]$ is not empty $G({\cal F}[A])$ is connected.

MAIN QUESTION:   How large can the diameter of $G({\cal F})$ be in terms of $d$ and $n$.

This entry was posted in Combinatorics, Convex polytopes, Open problems. Bookmark the permalink.

10 Responses to A Diamater Problem for Families of Sets.

1. Yosef says:

If D(n, d) is the maximum diameter in terms of n and d, easy to see D(n, d) \geq D(n-1, d-1). Is there any easy inequalities that make D grow?

2. Gil says:

Dear Yosef,
Right. If you start with a family of (d-1)-subsets of a set of size n-1, and add a new element to the ground set and to every set in the family, you reach a new family with parameters n and d with precisely the same graph. I am not aware of general inequalities of this form which makes D grows substantially quicker than what follows from the inequality you have stated.

3. Yosef says:

I was wondering if set-complements allow you to say that D(n, d) = D(n, n-d). I haven’t been able to show that the connected criterion must carry over to the complements in G(F'[A]), is it so?

4. Yosef's Roommate says:

The desired complementary behavior fails; consider F = { {1,2}, {2,3}, {3,4}, {4,5} }. Then we have:
F’ = { {1,2,3}, {1,2,5}, {1,4,5}, {3,4,5} }
Which does not supply a connected graph for A = {3}.

So far, I only have the trivial D(n,d) \geq D(n-k,d) + D(k,d) + d, for any choice of d \leq k \leq n-d, and d \geq 2.

This, plus D(n,d) \geq D(n-1,d-1) guarantees that D(n,d) \geq n-d . (This is not a particularly interesting revelation; this result can also be achieved by choosing F = { {1,2,…d}, {2,3,…,d+1}, …, {n-d+1,n-d+2,…,n} }.)

5. Gil says:

Yosef and Yosef’s Roomate

Indeed moving to complements is interesting. The connectivity condition is not preserved but is replaced by the condition that the induced family ${\cal G}=$ ${\cal F}_{|M}$ on every subset M of N, satisfies the condition that $G({\cal G})$ is connected. If we require connectivity both for families ${\cal F}[A]$ and for families ${\cal F}_{|M}$ then the maximum diameter (for $n \ge 2d$) is $2d$.

6. MM says:

Has this been resolved? It seems like for d=2 and d=3, it is impossible to improve on the bound Yousef’s Roomate gave.

7. Discoking says:

Great Blog!……There’s always something here to make me laugh…Keep doing what ya do 🙂

8. ddd says:

imberland Chaussures de ont maintenant ete dans le marche pour 25 annees.Ils ont ete des fashionalbe pour les decennies.Des aviateurs qui ont porte des Regions boisees pour rester aussi chaud que possible pendant Premiere guerre mondiale, les ventilateurs de Timberland comprennent une variete vaste de gens aux surfeurs qui aimaient porter des Timberland sur la plage, aux femmes a la mode qui ont commence a porter des Timberland pendant leur renaissance en 2003.Les Timberland Chaussures ont aussi ete concues pour fournir surtout confort, securite de fonctionnement et protection aux professionnels aimez des ingenieurs, ouvriers du batiment dans leur travail. Les bottes de Timberland Pas Cher sont les meilleures comme port de plein air.