Sperner's theorem

Every antichain in

P ([n])

has at most

(⌊ n /2 ⌋ n)

members. Equality is attained only by a full middle level, with either middle level possible when

n

is odd.

Littlewood-Offord inequality ( $# {ϵ : ∥ \sum_{i} ϵ_{i} x_{i} - a ∥ < 1} \leq (⌊ n /2 ⌋ n)$ )

For vectors of norm at least one, the number of signed sums in an open unit ball is at most the central binomial coefficient. In one dimension this follows from the antichain bound. In Euclidean spaces a separated block decomposition for vector subset sums supplies the same bound without assuming all vectors have positive projection in one common direction. Signed sums are counted with multiplicity, by their sign choices.

For real coefficients of absolute value at least one, an open interval of length four contains at most the sum of the two largest binomial coefficients of signed sums. The corresponding subset family has no three-element inclusion chain. Its Lubell mass is therefore at most two, giving the bound by allocating mass to the two largest levels. Unit coefficients attain it at a center midway between the two chosen sum levels.

x_{i}

of length at least one, their labeled subset sums can be partitioned into pairwise distance-at-least-one blocks, with

(r n) - (r - 1 n)

blocks of size

n - 2 r + 1

. To extend a separated block by a vector

x

, choose its member

y

minimizing inner product with

x

. The translated block together with

y

remains separated, since

(z + x - y) \cdot x \geq ∥ x ∥^{2}

. The untransformed block with

y

removed remains separated too. Block sizes change from

ℓ

ℓ + 1, ℓ - 1

(⌊ n /2 ⌋ n)

nonempty blocks.

The maximum antichains in the Boolean lattice are exactly its full middle levels. For even

n

there is one such level, and for odd

n

either middle level works. The LYM inequality first confines a maximum antichain to those levels; connectedness of the regular inclusion bipartite graph rules out a mixture of the two odd middle levels.

There are no discussions about this article yet.

Sperner's theorem is a result in combinatorics that deals with families of subsets of a finite set. Specifically, it states that if you have a set $ S $ with $ n $ elements, the largest family of subsets of $ S $ that can be chosen such that no one subset is contained within another (i.e.