8
$\begingroup$

Let $A$ be a set of size $k$ and $B$ be a set of size $\ell$, for fixed $k$ and $\ell$, and such that $A\cap B=\emptyset$. What is the (or a) Sperner family $\mathcal{F}$ on $A\cup B$ for which $\mathcal{F}_B=\{C\cap B ~:~ C\in\mathcal{F}\}$ is maximized?

I actually just need an upper bound to $|\mathcal{F}_B|$ (possibly something better than $2^\ell$, which seems to be loose if $2^k<\ell$)

Any hint or reference where this kind of information or relevant material could be found would be much appreciated. Thanks.

$\endgroup$
6
$\begingroup$

The correct upper bound is the sum of the $2^k$ most central binomial coefficients: $$|\mathcal{F}_B|\leq\binom \ell {\lfloor (\ell - 2^k)/2+1\rfloor} + \dots + \binom \ell {\lfloor(\ell + 2^k)/2\rfloor},$$ or just $|\mathcal{F}_B|\leq 2^\ell$ if $2^k\geq \ell+1$. The sets $\{B\cap C\mid C\in\mathcal F\text{ and }A\cap C=A'\}$ are antichains. By the LYM inequality the union of $2^k$ antichains cannot be larger than the sum of the largest $2^k$ binomial coefficients. To achieve the bound, let $A=\{a_0,\dots,a_{k-1}\}$, and let $$\mathcal F=\left\{C\subseteq A\cup B \mid \lfloor(\ell + 2^k)/2\rfloor- \sum_{i\colon a_i\in C} 2^i=|C\cap B| \right\}.$$

$\endgroup$
1
  • $\begingroup$ Thank you, Colin. I believe it is the correct answer, as we got the same result in a much more convoluted way. $\endgroup$
    – Matteo
    Oct 24 '12 at 2:12

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.