Math 2.0

Order, lattices, ordered algebraic structures Definition

Sperner property

Builds on Graded posetAntichainWidth of a poset

Definition

Let PP be a finite graded poset with rank function ρ\rho, and for each integer i≥0i \ge 0 let Pi={x∈P:ρ(x)=i}P_i = \set{x \in P : \rho(x) = i} be the ii-th rank level. The poset PP has the Sperner property when every antichain A⊆PA \subseteq P satisfies ∣A∣≤max⁡i∣Pi∣\abs{A} \le \max_i \abs{P_i}.

Remarks

Since each PiP_i is an antichain, the condition says that the width of PP equals max⁡i∣Pi∣\max_i \abs{P_i}.

Example: the lattice of subsets of {1,…,n}\set{1, \ldots, n}, ranked by size, has the Sperner property. Check: by Sperner's theorem, an antichain has at most (n⌊n/2⌋)\binom{n}{\floor{n/2}} members, which is the size of the middle level.

Non-example: let PP have elements a1,a2,ba_1, a_2, b of rank 00 and c,d1,d2c, d_1, d_2 of rank 11, with the relations a1<ca_1 < c, a2<ca_2 < c, b<d1b < d_1, b<d2b < d_2 and no others. Each level has 33 elements, but {a1,a2,d1,d2}\set{a_1, a_2, d_1, d_2} is an antichain with 44 elements.

A poset is strongly Sperner when, for every kk, the largest union of kk antichains is no larger than the largest union of kk rank levels.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Antichain concept
  2. Graded poset concept
  3. Width of a poset concept
  4. Sperner property definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Sperner_property_of_a_partially_ordered_set
About this page
TagBZ5GXNN7HC
URIm2://BZ5GXNN7HC
Kinddefinition
WritingW0 stub
MSC06A07, 05D05
DefinesSperner property
UsesGraded poset, Antichain, Width of a poset

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.