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.

About these ads

9 thoughts on “A Diamater Problem for Families of Sets.

  1. 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. 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. 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. 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. 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. Pingback: A Diameter problem (7): The Best Known Bound « Combinatorics and more

  7. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s