«
»

A Diamater Problem for Families of Sets.

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 on July 30, 2008 at 4:40 pm and is filed under Combinatorics, Convex polytopes, Open problems. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

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

  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.

  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?

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

  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.

  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.

  7. A Diameter problem (7): The Best Known Bound « Combinatorics and more Says:
    December 1, 2008 at 3:07 am

    [...] of earlier posts: Part 1 describes the problem. (It is repeated here.) Part 2 describe the connection to the Hirsch [...]

Leave a Reply