Skip to main content
3 of 3
replaced http://mathoverflow.net/ with https://mathoverflow.net/

This example is more closely related to a question of mine, but I'll give it here anyway.

A graded poset $P$ is Sperner if no antichain is larger than the largest level $P_i$ of $P$. This property is named after Sperner, who proved that the Boolean posets $B_n$ of subsets of $\{ 1, 2, ... n \}$ are Sperner. the Boolean posets $B_n$ are also rank-symmetric because they satisfy $(B_n)_i = (B_n)_{n-i}$, i.e. ${n \choose i} = {n \choose n-i}$ and unimodal because the sequence $(B_n)_i$ is at first increasing and then decreasing.

Let $G$ be a group acting on $\{ 1, 2, ... n \}$. Then $G$ acts on $B_n$ in the obvious way by order- and grade-preserving automorphisms. Define the quotient poset $B_n/G$ in the obvious way, which inherits the grading on $B_n$. It's not hard to see that $B_n/G$ is also rank-symmetric.

Theorem: $B_n/G$ is unimodal and Sperner.

The only known proofs of this theorem are algebraic (the one I know uses linear algebra), and even for special cases a purely combinatorial proof is not known. For example, in the case that $n = ab$ is a product of two positive integers and $G = S_b \wr S_a$ we recover the poset $L(a, b)$ of Young diagrams that fit into an $a \times b$ box; then the above theorem implies that the coefficients of the q-binomial coefficient ${a + b \choose b}_q$ are unimodal. This was first proven by Sylvester in 1878, and a combinatorial proof was not found until 1989. A combinatorial proof of the Sperner property is still not known. This example is all the more remarkable because the statement that $L(m, n)$ is Sperner requires almost no mathematics to understand.

Edit: I should probably provide a reference. This material is from some notes on algebraic combinatorics by Stanley.

Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741