1
$\begingroup$

We say a system $S$ is semi-independent of subsets of $X$ if it contains no three sets $A,B,C$ such that $A\subset B \subset C$. Show that 1. $\mid S \mid \leq 2{{n}\choose{\lfloor n/2\rfloor}}$ where $n=\mid X \mid$ and 2. For odd $n$, the estimate in 1 cannot be improved.

I want to use the Sperner's theorem to prove this statement but I don't know how to proceed. https://en.wikipedia.org/wiki/Sperner%27s_theorem

Any idea how to tackle this problem?

$\endgroup$
1
$\begingroup$

HINT: Let $S^+$ be the set of $A\in S$ that are not proper subsets of any $B\in S$, and let $S^-$ be the set of $A\in S$ that are not proper supersets of any $B\in S$. (In other words, if you view $\langle S,\subseteq\rangle$ as a partial order, $S^+$ is the set of maximal elements, and $S^-$ is the set of minimal elements.) The semi-independence of $S$ ensures that $S=S^+\cup S^-$. What can you say about the cardinalities of $S^+$ and $S^-$?

For the second question you can make use of the fact that $\left\lfloor\frac{n}2\right\rfloor<\left\lceil\frac{n}2\right\rceil$ when $n$ is odd.

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