What is the maximum number of subsets of $S = {1, 2, . . . , 2n}$ such that no one is contained in another and no two cover whole $S$?
Proposed by Fedor Petrov
I'm p sure the ans is $\binom{2n}{n-1}$, achievable when all of the subsets $B_i$ satisfy #$(B_i)=n-1$.
You can always change the subsets with #$(B_m)<n-1$ to #$(B_m)=n-1$. But you can't always change the $B_n$ with more than $n-1$ elements, rip me maybe a construction from here, but I couldn't get it.
I think that is the answer. We can prrove it by using sperners theorem and induction. Suppose we know claim is true for $n$ and we want to show it for $n+1$. Take two groups, $A$ and $B$, s.t that subset is in group $A$ iff it has $n+1$ in it. We can bound $|A|$ with inductive hypothesis, and |B| by using sperner. This way we are done.
ghu2024 wrote:
What is the maximum number of subsets of $S = {1, 2, . . . , 2n}$ such that no one is contained in another and no two cover whole $S$?
Proposed by Fedor Petrov
The answer is ${2n\choose n-1}$, the example is given by all sets of size $n-1$.
Assume that our collection $C$ contains an $s$-set (that is, a set of size $s$) with $s>n$, and choose maximal such $s$. Let $C$ contain totally $m$ sets of size $s$. Then they have more than $m$ distinct subsets of size $s-1$ (indeed, each of them has $s$ such $(s-1)$-subsets, and each $(s-1)$-subset is counted at most $2n-s+1<s$ times.) Replace our $s$-sets to their $(s-1)$-subsets, we enlarge $C$. So, all subsets in $S$ have size at most $n$. Next, if $C$ contain an $s$-set with some $s<n-1$, choose minimal such $s$. If $S$ contains $m$ $s$-sets, replace them to their $(s+1)$-oversets. Analogously to above argument, we enlarge $C$, and note that the new $C$ still satisfies the properties.
So we achieve that $C$ contains only $n$-sets, say $x$ of them, and $(n-1)$-sets, say $y$ of them. Assume that $x+y>{2n\choose n-1}$. Put the elements of $S$ around the circle at random. Consider the sets from $C$ which are formed by an arc of $n$ or $n-1$ consecutive elements on the circle. If we have $a$ such $n$-sets and $b$ such $(n-1)$-sets, then $\mathbb{E}(a)=2n\cdot \frac{x}{{2n\choose n}}=\frac{2n^2}{n+1} \cdot \frac{x}{{2n\choose n-1}}$, $\mathbb{E}(b)=2n\cdot \frac{y}{{2n\choose n-1}}$, thus $$\mathbb{E}((n+1)a+nb)=2n^2 \frac{x+y}{{2n\choose n-1}}>2n^2.$$
So, there exists a circular order of $S$ such that $(n+1)a+nb>2n^2$. If $a=0$ we get an absurd $b>2n$. Note that $a\leqslant n$ since $C$ can not contain two complement arcs of size $n$. We get $n(a+b)>2n^2-a\geqslant 2n^2-n$, thus $a+b\geqslant 2n$. But note that for any $n$-arc in $C$ its "initial segment" (counted counterclockwise) of size $n-1$ does not belong to $C$. This already gives $a$ distinct $(n-1)$-arcs not in $C$. Analogously we get $a$ distinct "final segments" also not in $C$. But since $b=2n-a$, this all is possible only if the final segments and initial segments are the same $a$ arcs. In other words, each initial segment is also a final segment. This implies that if an arc belongs to $C$, its shift by 1 also belongs to $C$ etc, totally all $n$-arcs belong to $C$, an absurd. A contradiction proving that actually $x+y\leqslant {2n\choose n-1}$.