What are some applications of Sperner style theorems?

Question

I'm currently working through "Combinatorics of Finite Sets" by Ian Anderson, mostly to improve at a style of mathematics that I've historically been quite bad at, and I find myself wondering why this sort of work actually matters outside of intrinsic interest - the two books I have on this subject are this and Bollobas, and neither of them seem to have so much of a hint at the motivations for studying this other than because we can.

In particular things like Sperner's Theorem (the one about counting antichains, not the one about triangulations of simplices) are neat but I can't see any really interesting consequences of it, either in combinatorics, other areas of mathematics or outside of mathematics altogether. Are there?

I'm aware of the Littlewood-Offord problem, but it doesn't seem any more applicable than Sperner's theorem itself and it's more or less the only application I've found.

I'm not wedded to examples just about Sperner's theorem. I'd be happy with anything "related" - any of the generalisations of it, the Lubell–Yamamoto–Meshalkin inequality, etc.

Answer 1

To give an idea of how real-life applications may arise outside mathematics, let's consider a "testing" problem of some sort. I'll set up a problem to solve first, so Sperner's theorem doesn't appear until much later in this post. What I describe is the basic theory behind Intel's X-compact. If you wish, a more engineer-friendly description can be found in

S. Mitra and K. S. Kim, X-compact: An efficient response compaction technique, IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 23 (2004) 421-432.

So, let's say you've got a bunch of $n$-bit vectors and want to know if they're all exactly the ones you actually want. More formally, you are given two ordered (multi-) sets $S = (\boldsymbol{s}_0,\dots,\boldsymbol{s}_{x-1})$, $T = (\boldsymbol{t}_0,\dots,\boldsymbol{t}_{x-1})$ $\subseteq \mathbb{F}_2^n$ of $n$-dimensional binary vectors over the finite field $\mathbb{F}_2$ of order $2$, where their sizes $\vert S\vert = \vert T\vert = x$ are the same. Your task is to check if for any $0 \leq i \leq x-1$, it holds that $\boldsymbol{s}_i = \boldsymbol{t}_i$, i.e., $S$ and $T$ are completely the same list of vectors.

You may simply assume that $S$ is the list of vectors you asked for and $T$ is what you are actually given. It may sound trivial to check whether a pair of lists of binary vectors are the same. However, if the number $x$ of vectors in $S$ (and also in $T$) is huge and/or if the number $n$ of bits in each vector is humongous, it can be hopeless to check each and every bit one by one.

To make this hypothetical problem more concrete, you may think of a brand-new CPU you, as an engineer, designed. You want to make sure that your newly designed CPU behaves as expected no matter what input you throw at it. Let's say, your CPU has $1,000,000$ input pins and $1,000,000$ output pins. So, there are $2^{1000000}$ possible input patters that may get into the input pins, and you want to make sure that your CPU responds correctly to any possible input.

In this example, $S$ is the list of expected responses to the $2^{1000000}$ possible input patters. And $T$ is the corresponding actual behaviors of your CPU, i.e., the actual output bits from the output pins. So $T$ is also the list of $1000000$-dimensional vectors of cardinality $2^{1000000}$.

Since we have only $10^{80}$ or so atoms in our entire universe, I think it is now clear how absurdly impossible to first make the golden list $S$ of correct responses and then compare actual output $T$ against it bit by bit; if you want to be practical, the size of your golden list better be at the very most in the order of the number of atoms on Earth, not gazillions of times the number of atoms in our galaxy.

The first thing you should do is to reduce the insane number $2^{1000000}$ to something more sober. This may be done by, for example, limiting the input patters to really important ones you definitely, absolutely want to check. Also, because you are the CPU designer who devised the product, you know how wires and stuff are (supposed to be) connected in the CPU, so you might be able to come up with a clever, small set of input patterns to test which reveals all practically important design flaws and manufacturing faults.

So, after all those efforts, you now have a reduced golden list $S'$ of sane but still very large size. (This was already in the order of gigabytes for an ordinary CPU in an run-of-the-mill PC about a decade ago.) So, $T$ is also automatically reduced in size, and now you have $T'$ of very large but not crazy large size. The next task is to reduce the "$1,000,000$," i.e., the dimension of each vector in $S'$ (and $T'$). This is where Sperner's theorem comes in handy (at least in the simplest case).

In an abstract language, what we want to do is devise a good map $h: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^m$ (where $m$ is much smaller than $n$) and hash each vector $\boldsymbol{s}_i \in S'$ and corresponding actual output vector $\boldsymbol{t}_i \in T'$ to shorter vectors $h(\boldsymbol{s}_i), h(\boldsymbol{t}_i)$ in such a way that if $\boldsymbol{s}_i \not= \boldsymbol{t}_i$, then $h(\boldsymbol{s}_i) \not= h(\boldsymbol{t}_i)$. This way, we only need to compare the hashed vectors, and hence the golden list $S'$ can be made smaller.

Of course, because $n > m$, this is asking the impossible. So, we settle for "being able to detect pretty much all discrepancies that can practically happen." To make this condition more mathematics-friendly, let's consider the situation where your CPU is well designed and very stable against potential fault, so that if there is any unexpected behavior (i.e., $\boldsymbol{s}_i \not= \boldsymbol{t}_i$ for some $i$), the discrepancy between the correct and actual responses is just $1$ bit (or equivalently, if $\boldsymbol{s}_i \not= \boldsymbol{t}_i$, then only one of the $n$ pairs of bits is different).

If this were all there to the problem of testing a CPU's behavior, you could simply use a linear map $h$ from $\mathbb{F}_2^n$ to $\mathbb{F}_2^m$ defined by an $m \times n$ matrix $H$ over $\mathbb{F}_2$ in which no columns are the $m$-dimensional zero vector $\boldsymbol{0}$. Indeed, it is easy to see that for any $\boldsymbol{s}, \boldsymbol{e} \in \mathbb{F}_2^n$ with $\operatorname{wt}(\boldsymbol{e}) = 1$, we have $$H(\boldsymbol{s}+\boldsymbol{e})^T \not= H\boldsymbol{s}^T.$$ So, our hashing would simply be "multiplying $H$," which shrinks $n$-dimensional vectors into $m$-dimensional vectors. This is very nice because a linear hashing circuit is simple hardware-wise and runs very fast.

Now, the thing is that because modern CPUs are very complicated, you can't always perfectly predict its behavior even if you have its exact blueprint. So, for some input patterns, the correct, expected output from certain output pins are "not determined," represented by symbol $X$. In other words, some bits of some vectors in $S'$ are $X$ rather than $0$ or $1$.

Let's see how this affects our linear hashing. For the sake of simplicity, let $n=7$ and $m=3$. Take the following linear map $H$ defined by $$H = \left(\begin{array}{ccccccc} 1001101\\ 0101011\\ 0010111 \end{array}\right).$$ Assume that the expected behavior is $\boldsymbol{s}_i = (1,1,0,0,X,0,1)$. Since the sums and multiplications involving unknown behavior $X$ are again unknown (except when we take the product of $X$ and $0$, which would surely be $0$). So, our hashed vector $h(\boldsymbol{s}_i)$ is $$H\boldsymbol{s}_i^T = (X,0,X)^T.$$ Obviously, because the $X$'s mask two bits in the resulting hash value, we have to detect any discrepancy between $\boldsymbol{s}_i$ and the actual, corresponding behavior $\boldsymbol{t}_i$ by looking at the single surviving bit. Of course, this is impossible because, for example, $\boldsymbol{t}_i = (0,1,0,0,X,0,1)$ gives the exact same hash value as $h(\boldsymbol{s}_i)$.

How do we design a linear hash function that shrinks $n$-dimensional vectors as much as possible while ensuring detection of at most one-bit discrepancy under the presence of unknown bits $X$? Let's focus on the simplest case where the blueprint of your CPU is simple enough so that there is at most one $X$ in each expected response $\boldsymbol{s}_i \in S'$. In this case, an optimal hashing circuit $H$ is given by Sperner's theorem.

To see this, recall that Sperner's theorem gives the size of a largest possible family $A = \{A_0,\dots,A_{n-1}\}$ of finite sets $A_i \subseteq \{0,1,\dots,m-1\}$ none of which contains any other sets in $A$, i.e., $A_i \not\subseteq A_j$ for any $i \not= j$. Such a family is called a Sperner family. The theorem says that for any Sperner family $A$, we have $$\vert A \vert = n \leq \binom{m}{\lfloor m/2 \rfloor},$$ and that the equality can be achieved by taking all distinct $\lfloor m/2 \rfloor$-subsets of $\{0,1,\dots,m-1\}$.

Now, given an $m \times n$ binary matrix $H = (h_{i,j})$, construct the family $B = \{B_0,\dots,B_{n-1}\}$ of subsets of $\{0,1,\dots,m-1\}$ by defining $i \in B_j$ if and only if $h_{i,j} = 1$. It is straightforward to see that, with this set representation of a binary matrix, the kind of linear hash function we want for detecting discrepancies under the presence of at most $1$ unknown $X$ is exactly a Sperner family. Indeed, the condition that no set covers any other corresponds to the requirement that propagated $X$'s do not mask any possible $1$-bit-wise discrepancy.

So, the condition that the linear map should compress data as much as possible corresponds to the requirement that for given $m$, the number $n$ of elements in a Sperner family should be as large as possible. Or if $n$ is given, $m$ should be as small as possible. Either way, we know the bound and how to achieve it thanks to Sperner's theorem.

Of course, if your CPU gives multiple-bit-wise discrepancies or if there are more than one unknown bit, you need more sophisticated extremal set theory. But the point is that the kind of research related to Sperner's theorem gives a solid foundation of practical problems outside of mathematics like this.

Answer 2

This may not quite answer your stated question but it may give you some sense of a larger context into which Sperner's theorem fits in.

Let's take as given that finding a (proper) coloring of a graph is an interesting combinatorial optimization problem. We know that this problem is NP-hard in general, but the interesting thing is that certain classes of graphs can be optimally colored in polynomial time. The most famous examples are perfect graphs. The special case of incomparability graphs arises frequently, and in this case, Dilworth's theorem tells us that the chromatic number of the incomparability graph of a poset $P$ is equal to the maximum size of an antichain in $P$. In some cases, the maximum size of an antichain may be easier to understand directly than the chromatic number. In particular, Sperner's theorem tells us that at least in the special case of a Boolean algebra, the obvious candidate for a maximum-size antichain is indeed optimal.

To put it another way, one way to think about Sperner-type theorems is that they tell you that for certain special graphs, the obvious bound on the chromatic number is actually tight. This is not quite an "application" in the sense of an interesting theorem that uses Sperner's theorem as a lemma, but the question of whether a seemingly optimal solution is actually optimal arises all the time in combinatorial optimization, and it is good to have some theory that helps us answer that question in commonly occurring special cases.

Answer 3

I will upgrade my comment to an answer.

Let $P$ be a ranked poset, with rank sizes $N_1,N_2,\ldots,N_k$. Suppose that we want to estimate the number $e(P)$ of linear extensions of $P$. (This is a basic problem in combinatorics/order theory, which I won't motivate otherwise, but maybe it is already too close to Sperner's Theorem for you?)

A trivial lower bound on the number of linear extensions is $\prod_{i=1}^{k} N_i! \leq e(P)$: this counts those linear extensions of the form a permutation of $N_1$ followed by a permutation of $N_2$ and so on. A trivial upper bound on $e(P) \leq \mathrm{width}(P)^{\#P}$ (where width is the maximal size of an antichain) because when I build up a linear extension element by element, the set of next available elements forms an antichain.

There is an improvement to the trivial upper bound in the case where $P$ is LYM. We say $P$ is LYM if for any antichain $A$ of $P$ we have $\sum_{a \in A} \mathrm{wt}(a) \leq 1$, where the weight $\mathrm{wt}(p)$ of an element $p \in P$ is $1/N_i$ if $p$ belongs to the $i$th rank. The LYM property is a generalization of the Sperner property. For more details see the Wikipedia page.

Theorem If $P$ is LYM then $e(P) \leq \prod_{i=1}^{k} N_i^{N_i}$.

For a beautiful, short, "probabilistic" proof of this result, see this expository article by Brightwell.

As I mentioned in the comments, this is a pretty good estimate on the number of linear extensions in the case of the Boolean lattice, but is not the best known result. The best result can be found in this paper of Brightwell and Tetali.