0
$\begingroup$

The question is simply: let $|S| = n,$ how big can a subset $I$ of $2^S$ be such that for any $A, B \in I,$ $A\not\subset B$ (so, this is an independent set in the graph whose vertices are subsets, and edges correspond to inclusion in some direction). It is clear that $|I| \geq \binom{n} {\lfloor \frac{n}{2} \rfloor},$ but is that sharp?

Update As Gerhard points out, the answer is YES. Now a followup: what about a family which has no $k$-element chain $A\subset B \subset \dotsc \subset C?$

Improve this question
$\endgroup$
5
  • $\begingroup$ Sperner sets. Gerhard "Yes, Antichains Are That Big" Paseman, 2017.10.27. $\endgroup$
    – Gerhard Paseman
    Commented Oct 28, 2017 at 3:37
  • $\begingroup$ @GerhardPaseman Truly you are wise in the ways of science! $\endgroup$
    – Igor Rivin
    Commented Oct 28, 2017 at 3:54
  • 1
    $\begingroup$ There is a very nice recent survey of progress on these kinds of problems, by Griggs and Li, at link.springer.com/chapter/10.1007%2F978-3-319-24298-9_14. Thm 1.2 covers your updated question. $\endgroup$
    – David Galvin
    Commented Oct 28, 2017 at 4:24
  • $\begingroup$ Not so sure about the follow up. I would guess the union of k-1 antichains, which gives a naive upper bound of (k-1) times the middle binomial coefficient. Gerhard "Slight Improvements Available Upon Request" Paseman, 2017.10.27. $\endgroup$
    – Gerhard Paseman
    Commented Oct 28, 2017 at 5:31
  • $\begingroup$ @GerhardPaseman Yes, I had surmised the naive bound, but wonder if it is sharp. I will try to find D. Galvin's reference... $\endgroup$
    – Igor Rivin
    Commented Oct 28, 2017 at 5:34

1 Answer 1

Reset to default
5
$\begingroup$

To address the updated question, a family of subsets of $[n]$ is called $k$-Sperner if it does not contain a chain of length $k+1$. By taking all sets whose size lies in the middle $k$ values of $[n]$, there exist $k$-Sperner families who size is the sum of the $k$ middle bịnomial coefficients. Erdős proved that this bound is tight in this paper (see Theorem 5). The extremal example is also essentially unique (for parity reasons there may be two intervals of middle $k$ values).

Improve this answer
$\endgroup$
3
  • $\begingroup$ It seems you've accidentally posted two answers ... $\endgroup$
    – Glorfindel
    Commented Oct 28, 2017 at 10:23
  • $\begingroup$ Yes, I was bumbling on my phone. I deleted the other answer, thanks. $\endgroup$
    – Tony Huynh
    Commented Oct 28, 2017 at 10:24
  • 1
    $\begingroup$ Also, the OP should have a look at the LYM inequality. It implies his original question (Sperner's Theorem) and it's generalisation to chains of length k (first proved by Erdős). $\endgroup$
    – Jon Noel
    Commented Oct 29, 2017 at 8:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .