Chains, Antichains, Sperner and Dilworth

About this page

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 23 results · all verified · 1 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 22 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

1 · Prerequisites

Combinatorics

Real Analysis

Set Theory

2 · Logical flowchart

3 · Items

Definition

At most k cyclic intervals of length k in a cyclic order are pairwise intersecting when the ground-set size is at least 2k

Theorem

Erdős-Ko-Rado theorem: for 1≤ k and n≥ 2k, an intersecting family of k-subsets of an n-set has size at most C(n-1, k-1), and a star attains the bound

Lemma

A maximal pairwise disjoint subfamily either supplies a sunflower or gives a small transversal for the whole uniform family

Theorem

Birkhoff representation theorem: every finite distributive lattice is isomorphic to the lattice of order ideals of its join-irreducible poset

False statement

False: every maximal antichain in a finite poset has maximum cardinality

False statement

False: the Erdős-Ko-Rado bound holds without the hypothesis n≥ 2k

Sources

Chains, Antichains, Sperner and Dilworth

3 · Items

Antichains, chain covers, and antichain covers of a poset

Height and width of a nonempty finite poset

Graded poset, rank function, and rank levels

The Boolean lattice of subsets of a finite set and its rank levels

Lattices, distributive lattices, and order ideals

Join-irreducible elements of a nonempty finite lattice

The lower and upper shadows of a uniform set family

Intersecting uniform families of finite sets

Sunflowers, petals, and their common core

Mirsky's theorem: the minimum number of antichains covering a finite poset equals its height

A maximal antichain splits a finite poset into its down-set and up-set with the antichain as their intersection

The down-set and up-set chain covers from a suitable maximum antichain splice to a width-sized chain cover

Dilworth's theorem: the minimum number of chains covering a finite poset equals its width

The Erdős-Szekeres monotone subsequence theorem follows by applying Mirsky's theorem to the index-value poset

The Boolean lattice on an n-element set has n! maximal chains, and exactly k!(n-k)! contain a fixed k-set

Lubell-Yamamoto-Meshalkin inequality for antichains in a Boolean lattice

Local LYM inequality comparing a uniform family with its upper shadow

The binomial coefficients are symmetric and increase to the middle level before decreasing

Sperner's theorem and its equality cases: a largest antichain is a complete middle level

A symmetric chain decomposition of one Boolean lattice lifts to the next Boolean lattice

Every finite Boolean lattice has a symmetric chain decomposition

A symmetric chain decomposition gives a second proof of Sperner's bound

At most k cyclic intervals of length k in a cyclic order are pairwise intersecting when the ground-set size is at least 2k

Erdős-Ko-Rado theorem: for 1≤ k and n≥ 2k, an intersecting family of k-subsets of an n-set has size at most C(n-1, k-1), and a star attains the bound

A maximal pairwise disjoint subfamily either supplies a sunflower or gives a small transversal for the whole uniform family

Erdős-Rado sunflower lemma: more than k!(r-1)ᵏ distinct k-sets contain an r-petal sunflower

A finite lattice has a bottom and a top, and every element is the join of the join-irreducible elements below it

Every join-irreducible element of a distributive lattice is join-prime

The order ideals of a finite poset form a distributive lattice under union and intersection

Birkhoff representation theorem: every finite distributive lattice is isomorphic to the lattice of order ideals of its join-irreducible poset

False: every maximal antichain in a finite poset has maximum cardinality

False: the Erdős-Ko-Rado bound holds without the hypothesis n≥ 2k