Namespaces
Variants
Actions

Difference between revisions of "Sperner property"

From Encyclopedia of Mathematics
Jump to: navigation, search
(fix tex)
(refs)
 
(3 intermediate revisions by one other user not shown)
Line 1: Line 1:
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
+
{{TEX|done}}
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 
was used.
 
If the TeX and formula formatting is correct and if all png images have been replaced by TeX code, please remove this message and the {{TEX|semi-auto}} category.
 
  
Out of 67 formulas, 65 were replaced by TEX code.-->
+
Let $P$ be a finite [[Partially ordered set|partially ordered set]] (abbreviated: poset) which possesses a rank function $r$, ''i.e.'' a function $r : P \rightarrow \mathbf{N}$ such that $r ( p ) = 0$ for some minimal element $p$ of $P$ and $r ( q ) = r ( p ) + 1$ whenever $q$ [[Covering element|covers]] $p$, i.e. $p < q$ and there is no element between $p$ and $q$. Let $N _ { k } : = \{ p \in P : r ( p ) = k \}$ be its $k$th level and let $r ( P ) : = \operatorname { max } \{ r ( p ) : p \in P \}$ be the rank of $P$.
 
 
{{TEX|done}}
 
Let $P$ be a finite [[Partially ordered set|partially ordered set]] (abbreviated: poset) which possesses a rank function $r$, i.e. a function $r : P \rightarrow \mathbf{N}$ such that $r ( p ) = 0$ for some minimal element $p$ of $P$ and $r ( q ) = r ( p ) + 1$ whenever $q$ covers $p$, i.e. $p &lt; q$ and there is no element between $p$ and $q$. Let $N _ { k } : = \{ p \in P : r ( p ) = k \}$ be its $k$th level and let $r ( P ) : = \operatorname { max } \{ r ( p ) : p \in P \}$ be the rank of $P$.
 
  
An [[anti-chain]] or Sperner family in $P$ is a subset of pairwise incomparable elements of $P$. Obviously, each level is an anti-chain. The [[width of a partially ordered set]] $P$ (Dilworth number or Sperner number) is the maximum size $d ( P )$ of an anti-chain of $P$. The poset $P$ is said to have the Sperner property if $d ( P ) = \operatorname { max } _ { k } | N _ { k } |$. E. Sperner proved in 1928 the Sperner property for Boolean lattices (cf. also [[Sperner theorem|Sperner theorem]]).
+
An [[anti-chain]] or Sperner family in $P$ is a subset of pairwise incomparable elements of $P$. Obviously, each level is an anti-chain. The [[width of a partially ordered set]] $P$ (Dilworth number or Sperner number) is the maximum size $d ( P )$ of an anti-chain of $P$. The poset $P$ is said to have the Sperner property if $d ( P ) = \operatorname { max } _ { k } | N _ { k } |$. E. Sperner proved in 1928 the Sperner property for Boolean lattices (cf. also [[Sperner theorem]]).
  
 
More generally, a $k$-family, $ k  = 1 , \ldots , r ( P )$, is a subset of $P$ containing no chain of $k + 1$ elements in $P$, and $P$ has the strong Sperner property if for each $k$ the largest size of a $k$-family in $P$ equals the largest size of a union of $k$ levels. There exist several classes of posets having the strong Sperner property:
 
More generally, a $k$-family, $ k  = 1 , \ldots , r ( P )$, is a subset of $P$ containing no chain of $k + 1$ elements in $P$, and $P$ has the strong Sperner property if for each $k$ the largest size of a $k$-family in $P$ equals the largest size of a union of $k$ levels. There exist several classes of posets having the strong Sperner property:
  
LYM posets, i.e. posets $P$ satisfying the LYM inequality (cf. also [[Sperner theorem|Sperner theorem]])
+
''LYM posets'', i.e. posets $P$ satisfying the [[LYM inequality]]  
  
 
\begin{equation*} \sum _ { k = 0 } ^ { r ( P ) } \frac { | \mathcal{F} \cap N _ { k } | } { | N _ { k } | } \leq 1 \end{equation*}
 
\begin{equation*} \sum _ { k = 0 } ^ { r ( P ) } \frac { | \mathcal{F} \cap N _ { k } | } { | N _ { k } | } \leq 1 \end{equation*}
Line 21: Line 15:
 
\begin{equation*} \frac { | \nabla ( {\cal A} ) | } { | N _ { k + 1} | } \geq \frac { | {\cal A} | } { | N _ { k } | } \end{equation*}
 
\begin{equation*} \frac { | \nabla ( {\cal A} ) | } { | N _ { k + 1} | } \geq \frac { | {\cal A} | } { | N _ { k } | } \end{equation*}
  
for all $A \subseteq N _ { k }$, $k = 0 , \ldots , r ( P ) - 1$, where $\nabla ( \mathcal{A} ) : = \{ q \in N _ { k  + 1} : q &gt; p \ \text { for some } p \in \mathcal{A} \}$. This equivalent property is called the normalized matching property of $P$.
+
for all $A \subseteq N _ { k }$, $k = 0 , \ldots , r ( P ) - 1$, where $\nabla ( \mathcal{A} ) : = \{ q \in N _ { k  + 1} : q > p \ \text { for some } p \in \mathcal{A} \}$. This equivalent property is called the ''normalized matching property'' of $P$.
  
Symmetric chain orders, i.e. ranked posets $P$ which can be decomposed into chains of the form $( p _ { 0 } &lt; \ldots &lt; p _ { h } )$ where $r ( p _ { i } ) = r ( p _ { 0 } ) + i$, $i = 0 , \ldots , h$, and $r ( p _ { 0 } ) + r ( p _ { h } ) = r ( P )$.
+
''Symmetric chain orders'', i.e. ranked posets $P$ which can be decomposed into chains of the form $( p _ { 0 } < \cdots < p _ { h } )$ where $r ( p _ { i } ) = r ( p _ { 0 } ) + i$, $i = 0 , \ldots , h$, and $r ( p _ { 0 } ) + r ( p _ { h } ) = r ( P )$.
  
Peck posets, i.e. ranked posets $P$ such that $| N _ { k } | = | N _ { r \langle P \rangle -k } |$ for all $k$ and there is a linear operator $\tilde { \nabla }$ on the vector space having the basis $\{  \tilde{p} : p \in P \}$ with the following properties:
+
''Peck posets'', i.e. ranked posets $P$ such that $| N _ { k } | = | N _ { r(P)-k} |$ for all $k$ and there is a linear operator $\tilde { \nabla }$ on the vector space having the basis $\{  \tilde{p} : p \in P \}$ with the following properties:
$$
+
* $\widetilde{\nabla}(\tilde p) = \sum_{q:\,q\,\text{covers}\,p} c(p,q)\,\tilde q$ with some numbers $c ( p , q )$,
\widetilde{\nabla}(\tilde p) = \sum_{q:\,q\,\text{covers}\,p} c(p,q)\,\tilde q
+
* the subspace generated by $\{ \tilde { p } : p \in N _ { i } \}$ is mapped via $\widetilde { \nabla } ^ { j - i }$ to a subspace of dimension $\min\{|N_i|,|N_j|\}$ for all $0 \leq i < j \leq r ( P )$.
$$
 
with some numbers $c ( p , q )$,
 
  
the subspace generated by $\{ \tilde { p } : p \in N _ { i } \}$ is mapped via $\widetilde { \nabla } ^ { j - i }$ to a subspace of dimension $\min\{|N_i|,|N_j|\}$ for all $0 \leq i < j \leq r ( P )$. If $P$ and $Q$ are posets from one class, then also the direct product $P \times Q$ (ordered componentwise) belongs to that class, where in the case of LYM posets an additional condition must be supposed: $| N _ { k } | ^ { 2 } \geq | N _ { k  - 1} | | N _ { k  + 1}|$ for all $k$ (so-called logarithmic concavity). Moreover, quotient theorems have been proved for LYM posets with weight functions and Peck posets.
+
If $P$ and $Q$ are posets from one class, then also the direct product $P \times Q$ (ordered componentwise) belongs to that class, where in the case of LYM posets an additional condition must be supposed: $| N _ { k } | ^ { 2 } \geq | N _ { k  - 1} | | N _ { k  + 1}|$ for all $k$ (so-called logarithmic concavity). Moreover, quotient theorems have been proved for LYM posets with weight functions and Peck posets.
  
 
Every LYM poset with the symmetry and unimodality property $| N _ { 0 } | = | N _ { r(P) } | \leq | N _ { 1 } | = | N _ {  r ( P ) - 1} | \leq \dots$ is a symmetric chain order and every symmetric chain order is a Peck poset.
 
Every LYM poset with the symmetry and unimodality property $| N _ { 0 } | = | N _ { r(P) } | \leq | N _ { 1 } | = | N _ {  r ( P ) - 1} | \leq \dots$ is a symmetric chain order and every symmetric chain order is a Peck poset.
Line 37: Line 29:
 
Standard examples of posets belonging to all these three classes are the lattice of subsets of a finite set, ordered by inclusion (the Boolean lattice), the lattice of divisors of a natural number, ordered by divisibility, the lattice of all subspaces of an $n$-dimensional vector space over a finite field, ordered by inclusion. The poset of faces of an $n$-dimensional cube, ordered by inclusion, belongs only to the class of LYM posets. The lattice of partitions of a finite set, ordered by refinement, even does not have the Sperner property if $n$ is sufficiently large.
 
Standard examples of posets belonging to all these three classes are the lattice of subsets of a finite set, ordered by inclusion (the Boolean lattice), the lattice of divisors of a natural number, ordered by divisibility, the lattice of all subspaces of an $n$-dimensional vector space over a finite field, ordered by inclusion. The poset of faces of an $n$-dimensional cube, ordered by inclusion, belongs only to the class of LYM posets. The lattice of partitions of a finite set, ordered by refinement, even does not have the Sperner property if $n$ is sufficiently large.
  
Details can be found in [[#References|[a1]]].
+
Details can be found in {{Cite|a1}}.
  
 
====References====
 
====References====
<table>
+
* {{Ref|a1}} K. Engel, Sperner Theory, Encyclopedia of Mathematics and its Applications '''65''', Cambridge (1997) {{ISBN|0-521-45206-6}} {{ZBL|0868.05001}}
<tr><td valign="top">[a1]</td> <td valign="top"> K. Engel, Sperner Theory, Encyclopedia of Mathematics and its Applications '''65''', Cambridge (1997) ISBN 0-521-45206-6  {{ZBL|0868.05001}}</td></tr>
 
</table>
 

Latest revision as of 07:51, 19 March 2023


Let $P$ be a finite partially ordered set (abbreviated: poset) which possesses a rank function $r$, i.e. a function $r : P \rightarrow \mathbf{N}$ such that $r ( p ) = 0$ for some minimal element $p$ of $P$ and $r ( q ) = r ( p ) + 1$ whenever $q$ covers $p$, i.e. $p < q$ and there is no element between $p$ and $q$. Let $N _ { k } : = \{ p \in P : r ( p ) = k \}$ be its $k$th level and let $r ( P ) : = \operatorname { max } \{ r ( p ) : p \in P \}$ be the rank of $P$.

An anti-chain or Sperner family in $P$ is a subset of pairwise incomparable elements of $P$. Obviously, each level is an anti-chain. The width of a partially ordered set $P$ (Dilworth number or Sperner number) is the maximum size $d ( P )$ of an anti-chain of $P$. The poset $P$ is said to have the Sperner property if $d ( P ) = \operatorname { max } _ { k } | N _ { k } |$. E. Sperner proved in 1928 the Sperner property for Boolean lattices (cf. also Sperner theorem).

More generally, a $k$-family, $ k = 1 , \ldots , r ( P )$, is a subset of $P$ containing no chain of $k + 1$ elements in $P$, and $P$ has the strong Sperner property if for each $k$ the largest size of a $k$-family in $P$ equals the largest size of a union of $k$ levels. There exist several classes of posets having the strong Sperner property:

LYM posets, i.e. posets $P$ satisfying the LYM inequality

\begin{equation*} \sum _ { k = 0 } ^ { r ( P ) } \frac { | \mathcal{F} \cap N _ { k } | } { | N _ { k } | } \leq 1 \end{equation*}

for every anti-chain $\mathcal{F}$ in $P$ or, equivalently,

\begin{equation*} \frac { | \nabla ( {\cal A} ) | } { | N _ { k + 1} | } \geq \frac { | {\cal A} | } { | N _ { k } | } \end{equation*}

for all $A \subseteq N _ { k }$, $k = 0 , \ldots , r ( P ) - 1$, where $\nabla ( \mathcal{A} ) : = \{ q \in N _ { k + 1} : q > p \ \text { for some } p \in \mathcal{A} \}$. This equivalent property is called the normalized matching property of $P$.

Symmetric chain orders, i.e. ranked posets $P$ which can be decomposed into chains of the form $( p _ { 0 } < \cdots < p _ { h } )$ where $r ( p _ { i } ) = r ( p _ { 0 } ) + i$, $i = 0 , \ldots , h$, and $r ( p _ { 0 } ) + r ( p _ { h } ) = r ( P )$.

Peck posets, i.e. ranked posets $P$ such that $| N _ { k } | = | N _ { r(P)-k} |$ for all $k$ and there is a linear operator $\tilde { \nabla }$ on the vector space having the basis $\{ \tilde{p} : p \in P \}$ with the following properties:

  • $\widetilde{\nabla}(\tilde p) = \sum_{q:\,q\,\text{covers}\,p} c(p,q)\,\tilde q$ with some numbers $c ( p , q )$,
  • the subspace generated by $\{ \tilde { p } : p \in N _ { i } \}$ is mapped via $\widetilde { \nabla } ^ { j - i }$ to a subspace of dimension $\min\{|N_i|,|N_j|\}$ for all $0 \leq i < j \leq r ( P )$.

If $P$ and $Q$ are posets from one class, then also the direct product $P \times Q$ (ordered componentwise) belongs to that class, where in the case of LYM posets an additional condition must be supposed: $| N _ { k } | ^ { 2 } \geq | N _ { k - 1} | | N _ { k + 1}|$ for all $k$ (so-called logarithmic concavity). Moreover, quotient theorems have been proved for LYM posets with weight functions and Peck posets.

Every LYM poset with the symmetry and unimodality property $| N _ { 0 } | = | N _ { r(P) } | \leq | N _ { 1 } | = | N _ { r ( P ) - 1} | \leq \dots$ is a symmetric chain order and every symmetric chain order is a Peck poset.

Standard examples of posets belonging to all these three classes are the lattice of subsets of a finite set, ordered by inclusion (the Boolean lattice), the lattice of divisors of a natural number, ordered by divisibility, the lattice of all subspaces of an $n$-dimensional vector space over a finite field, ordered by inclusion. The poset of faces of an $n$-dimensional cube, ordered by inclusion, belongs only to the class of LYM posets. The lattice of partitions of a finite set, ordered by refinement, even does not have the Sperner property if $n$ is sufficiently large.

Details can be found in [a1].

References

  • [a1] K. Engel, Sperner Theory, Encyclopedia of Mathematics and its Applications 65, Cambridge (1997) ISBN 0-521-45206-6 Zbl 0868.05001
How to Cite This Entry:
Sperner property. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Sperner_property&oldid=51607
This article was adapted from an original article by K. Engel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article