0

I'm currently learning something about Sperner's Lemma and then the LYM Inequality. In trying to prove the LYM Inequality, the proof uses the concept of a shadow but I can't seem to get a proper grip of what it actually means. I've tried 'drawing it out' using Hasse diagrams but really have no clue whether I'm right or not.

For reference, this is the definition that I'm working with:

Let $F\subset X^{(r)}$ be a set system. The shadow $\delta F$ of $F$ is $\delta F=\{A\in X^{(r-1)}:\exists B\in F s.t. A\subset B\}$.

Various examples of how this definition works will certainly be helpful. Thanks.

Haikal Yeo
  • 2,224

1 Answers1

1

I do not know, if this is a common construction, but I can try to explain how it 'works'. By its very definition the shadow of a system $\mathcal F \subseteq X^{(r)}$ is just all the $r-1$-subsets of the elements of $F$, that is $$ \partial \def\F{\mathcal F}\F = \bigcup_{A \in \mathcal F} A^{(r-1)} $$ to write the definiton in another form (this sometimes helps). If you want to picture the shadow in the Hasse diagram of $\mathcal P(X)$ then note that $\mathcal F$ consists of some points in the $r$-th layer. The $r-1$-subsets of these sets are those sets in the $(r-1)$-layer which are linked to one of the $\F$-sets, that is lay directly under one of them.

To finally give an example, let us consider $\F = \bigl\{\{1,2,3\}, \{2,4,6\}, \{1,2,4\}, \{3,4,7\}\bigr\} \subseteq \mathbb N^{(3)}$. To compute the shadow we have to take the $2$-subsets of each, we have

  • $\def\a{1}\def\b{2}\def\c{3}\{\a,\b,\c\}$ has the $2$-subsets $\{\a,\b\}$, $\{\a,\c\}$, and $\{\b,\c\}$
  • $\def\a{2}\def\b{4}\def\c{6}\{\a,\b,\c\}$ has the $2$-subsets $\{\a,\b\}$, $\{\a,\c\}$, and $\{\b,\c\}$
  • $\def\a{1}\def\b{2}\def\c{4}\{\a,\b,\c\}$ has the $2$-subsets $\{\a,\b\}$, $\{\a,\c\}$, and $\{\b,\c\}$
  • $\def\a{3}\def\b{4}\def\c{7}\{\a,\b,\c\}$ has the $2$-subsets $\{\a,\b\}$, $\{\a,\c\}$, and $\{\b,\c\}$

So the shadow is $$ \partial\F = \bigl\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{2,6\}, \{3,4\},\{3,7\}, \{4,6\}, \{4,7\} \bigr\} $$

martini
  • 84,101