A Diamater Problem for Families of Sets.

Posted on July 30, 2008 by Gil Kalai

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:
    August 1, 2008 at 6:05 pm

    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?

    Reply
  2. Gil says:
    August 2, 2008 at 1:00 pm

    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.

    Reply
  3. Yosef says:
    August 4, 2008 at 11:44 pm

    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?

    Reply
  4. Yosef's Roommate says:
    August 6, 2008 at 1:56 am

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

    Reply
  5. Gil says:
    August 10, 2008 at 8:07 pm

    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.

    Reply
  6. MM says:
    August 14, 2008 at 10:27 pm

    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.

    Reply

  7. Pingback: A Diameter problem (7): The Best Known Bound « Combinatorics and more

  8. Discoking says:
    March 6, 2010 at 12:31 am

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

    Reply
  9. ddd says:
    August 9, 2011 at 11:47 am

    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.

    Reply

  10. Pingback: Updates and plans III. | Combinatorics and more

Leave a reply to MM Cancel reply