Families in posets minimizing the number of comparable pairs

Abstract

Given a poset $P$ we say a family $\mathcal{F}\subseteq P$ is centered if it is obtained by `taking sets as close to the middle layer as possible'. A poset $P$ is said to have the centeredness property if for any $M$, among all families of size $M$ in $P$, centered families contain the minimum number of comparable pairs. Kleitman showed that the Boolean lattice $\{0,1{\}}^n$ has the centeredness property. It was conjectured by Noel, Scott, and Sudakov, and by Balogh and Wagner, that the poset $\{0,1,\dots ,k{\}}^n$ also has the centeredness property, provided $n$ is sufficiently large compared to $k$. We show that this conjecture is false for all $k\ge 2$ and investigate the range of $M$ for which it holds. Further, we improve a result of Noel, Scott, and Sudakov by showing that the poset of subspaces of ${\mathbb{F}}_q^n$ has the centeredness property. Several open questions are also given.

19 pages, 6 figures