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
    Oct 28, 2017 at 3:37
  • $\begingroup$ @GerhardPaseman Truly you are wise in the ways of science! $\endgroup$
    – Igor Rivin
    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
    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
    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
    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
    Oct 28, 2017 at 10:23
  • $\begingroup$ Yes, I was bumbling on my phone. I deleted the other answer, thanks. $\endgroup$
    – Tony Huynh
    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
    Oct 29, 2017 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.