6
$\begingroup$

Let $T=\{1,2,\dots,2n+1\}$. What is the largest $k$ such that we can choose $k$ subsets of size $n$ and $k$ subsets of size $n+1$ of $T$ so that no chosen subset contains another?

$k=\binom{2n}{n-1}$ is possible: Choose all sets of size $n$ containing $1$, and all sets of size $n+1$ not containing $1$. Does it follow from Sperner's theorem that this is the best possible?

$\endgroup$
3
  • $\begingroup$ It should follow. I am not seeing what the challenge is here. Can you explain your difficulty? Gerhard "One Plus One Equals Two?" Paseman, 2019.05.22. $\endgroup$ May 22, 2019 at 16:00
  • $\begingroup$ The challenge is how it follows. Sperner says that there can be at most $\binom{2n+1}{n}$ pairwise non-containing subsets, but $2\binom{2n}{n-1} < \binom{2n+1}{n}$. $\endgroup$
    – doe
    May 22, 2019 at 16:07
  • $\begingroup$ Indeed. I had an off by one error, and did not check for it. The next step then is to look at the bipartite graph and induce an edge coloring by the connected vertex coloring. Thanks for explaining. Gerhard "Now I See The Challenge" Paseman, 2019.05.22. $\endgroup$ May 22, 2019 at 16:18

3 Answers 3

4
$\begingroup$

Let $\mathcal{A}$ be any collection of subsets of $\{1,\dots,m\}$ such that no subset in $\mathcal{A}$ is contained in another. Let $a_i$ be the number of $i$-element subsets in $\mathcal{A}$. A complete characterization of the sequences $(a_0,a_1,\dots)$ appears as Theorem 2.2 in https://pdfs.semanticscholar.org/da0b/1a3430e4be45119921b8b8a6578b355bb2f6.pdf. In principle it should be possible to use this result to answer your question, but I did not work out the details.

$\endgroup$
0
4
$\begingroup$

Like Richard Stanley, I also did not work out the details. I also can't say if you can prove it from Sperner's theorem. Here is why I think there is no larger $k$.

Split the bipartite graph into two based on whether they contain the element 1 or not. You will see the collection of n+1 sets fanout into the n-sets when they don't have the element 1, and the fanout goes the other way for the sets that do have 1. Your current solution shows the sets at the narrow end of each fanout. Suppose you want to improve upon it.

This means you will have to take (say) some sets from the n+1 camp, and replace them with even more sets in the other camp (and likewise for the n sets). But however you arrange the n+1 sets in the other camp, if they are all contained in a subset of size less than 2n+1, they will fan out to cover more subsets of size n than they replace, so whatever you choose has to cover the whole set of size 2n+1.

So now you have to pick j many subsets from 2n+1 elements of size n+1 that cover exactly j subsets of size n: this means each subset of size n has to be covered by n+1 subsets, which is all possible covers of that n set. This means any for any n set covered by one of your j cboices, you also need to cover another n set formed from this n set J by swapping any one element in J for another not in J. But now this closure condition means your j elements have to cover all n sets. That's too many. So it can't be done.

Gerhard "Look Ma, I Can Fly!" Paseman, 2019.05.22.

$\endgroup$
2
$\begingroup$

Here's another approach: Given families $\mathcal{A}$ and $\mathcal{B}$ of $n$-sets and $(n+1)$-sets (respectively) that obey the condition, replace $\mathcal{B}$ with the family $\mathcal{B}'$ of complements of sets in $\mathcal{B}$.

Now the condition that no set in $\mathcal{A}$ is contained in one in $\mathcal{B}$ becomes that every set in $\mathcal{A}$ intersects non-trivially with every set in $\mathcal{B}'$. Such a system is called cross-intersecting.

Now you can apply combinatorial shifting to $\mathcal{A}$ and $\mathcal{B}'$, and show that it preserves the intersection property. This reduces showing the proof of your inequality to shifted families, where it is likely to be much easier. (I haven't worked out all the details here.)

$\endgroup$
1
  • $\begingroup$ (Something equivalent to shifting also looks to be involved in @GerhardPaseman's answer.) $\endgroup$ May 22, 2019 at 18:47

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.