8
$\begingroup$

Given a set $A$ of $n$ elements and an positive integer $k\le n$, what is the size of the largest Sperner family $\mathcal{F}$ of subsets of $A$ such that $\mathcal{F}$ contains a set $B\subseteq A$ of size $k$?

I wonder whether it is just the family made of all subsets of $A$ of size $k$ (and why) or one can build a larger one.

$\endgroup$
2
  • 4
    $\begingroup$ If $k$ is much smaller than $n$, we can build set systems that contain a $k$-subset and larger than $\binom{n}{k}$. Keep the $k$-set apart. There will be a sperner family of length $\binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}$. Then, append the $k$-set to it. (for example note that when $n=10,k=2$, this gives a longer antichain). But we need not stop here, much more subsets can be appended. The final answer might be broken into cases depending on $k$. Thanks for a good problem, it deserves special attention. $\endgroup$
    – talegari
    Jun 8 '14 at 17:04
  • $\begingroup$ @talegari: thank you (again)! $\endgroup$
    – Matteo
    Jun 8 '14 at 18:01
0
$\begingroup$

If k is much smaller than n, we can build set systems that contain a k-subset and larger than $\binom{n}{k}$. Keep the k-set apart. There will be a sperner family of length $\binom{n-k}{\lfloor \frac{n-k}{2} \rfloor}$. Then, append the k-set to it. (for example note that when $n=10,k=2$, this gives a longer antichain). But we need not stop here, much more subsets can be appended. The final answer might be broken into cases depending on k. Thanks for a good problem, it deserves special attention.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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