Lagmental Vicfred

Sperner's Theorem Finds the Largest Boolean Antichain by Vicfred

tags: mathematics, posets, Mobius functions, extremal set theory

The middle layer of the subset lattice is the largest family with no containment relation. This is a compact note, but the quantifiers and hypotheses stay on the page.

The mathematical object

A finite poset \((P,\le)\) has intervals \([x,y]\) and an incidence algebra. Chains, antichains, and order ideals reveal different slices of its comparability structure.

$$ \mathcal A\subseteq2^{[n]},\qquad A\nsubseteq B\ \text{for distinct }A,B\in\mathcal A $$

I read the first line as input and the second as output. The symbols \(\forall\) and \(\exists\) are not interchangeable, and neither may be upgraded silently to \(\Longleftrightarrow\).

$$ |\mathcal A|\le\binom n{\lfloor n/2\rfloor} $$

One explicit computation

Here is a concrete symbolic test. Reading it from left to right reveals which transformation is reversible and which is only an implication.

$$ \sum_{A\in\mathcal A}\frac1{\binom n{|A|}}\le1\qquad\text{(LYM inequality)} $$

Why the identity matters

The aligned summary deliberately puts the datum and conclusion on different rows. Mathematically, this is the distinction between specifying an object and proving a property of it.

$$ \begin{aligned} \mathsf{D}\;&:\quad \mathcal A\subseteq2^{[n]},\qquad A\nsubseteq B\ \text{for distinct }A,B\in\mathcal A,\\[5pt] \mathsf{C}\;&:\quad |\mathcal A|\le\binom n{\lfloor n/2\rfloor}. \end{aligned} $$

Where it can fail

Width and height refer to antichains and chains in the poset, not to geometric dimensions of a drawing.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] |\mathcal A|\le\binom n{\lfloor n/2\rfloor} \end{gathered}} $$

The important habit is to remember what was fixed before the calculation began and what was proved only afterward. The final display preserves that order.

This article was posted on Fri 30 September 2022. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.