<p>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\}.$$</p>

CC BY-SA 3.0
2012-10-24T02:12:34.047Z
Thank you, Colin. I believe it is the correct answer, as we got the same result in a much more convoluted way.
Matteo
CC BY-SA 3.0
2012-10-24T00:07:58.820Z
2012-10-24T00:13:19.513Z
2012-10-24T00:13:19.513Z
Colin McQuillan
<p>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? </p>

<p>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&lt;\ell$)</p>

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

<reference-request><co.combinatorics>
Sperner family that maximizes the subsets of a partition
Matteo
# Sperner family that maximizes the subsets of a partition

(Asked by: username_0 on 2012-10-22)

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.

**Tags:** reference-request, co.combinatorics


---

## 1 answers

### Answer by username_1 on 2012-10-24. Score: 6 | Accepted answer

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\}.$$

> **Comments:**
> **username_0**: Thank you, Colin. I believe it is the correct answer, as we got the same result in a much more convoluted way.  

---

