Fact-checked by Grok 2 weeks ago

Dilworth's theorem

Dilworth's theorem is a foundational result in order theory, established by mathematician Robert P. Dilworth in 1950, which states that in any finite partially ordered set, the cardinality of the largest antichain equals the minimum number of disjoint chains needed to partition the set.^[1] A partially ordered set (poset) consists of a set equipped with a binary relation that is reflexive, antisymmetric, and transitive, modeling hierarchical structures in mathematics and computer science. In this context, a chain is a subset where every pair of elements is comparable (i.e., one precedes the other), forming a total order, while an antichain is a subset of pairwise incomparable elements, representing a maximal level of "parallel" or non-hierarchical items. The theorem establishes a precise duality between these concepts, quantifying the "width" of the poset (maximum antichain size) as the minimum chain cover size, and its proof relies on constructing a bipartite graph and applying the König-Egerváry theorem on matchings.^[1]^[2] Dilworth's theorem holds significant importance in combinatorics and related fields, enabling min-max characterizations that simplify proofs of extremal results. One notable application is in sequence analysis: for any sequence of n^2 + 1 distinct real numbers, the theorem implies the existence of a monotone subsequence of length at least n+1, providing a combinatorial proof of the Erdős–Szekeres theorem.^[3] It also connects to bipartite matching problems, where posets model graphs satisfying Hall's marriage condition, yielding perfect matchings via chain decompositions.^[3] In extremal set theory, the theorem underpins inequalities like the LYM inequality for antichains in the Boolean lattice, influencing results on intersecting families and Sperner's theorem.^[2]

Introduction and Statement

Historical Background

Robert Palmer Dilworth (1914–1993) was an American mathematician whose work significantly advanced the fields of algebra and order theory. Born in Hemet, California, he earned his B.S. in 1936 and Ph.D. in 1939 from the California Institute of Technology (Caltech), where his doctoral research under Morgan Ward focused on lattice theory. Following his time as an instructor at Yale University from 1940 to 1943, Dilworth returned to Caltech in 1943 as an assistant professor. He served in World War II from July 1944 to spring 1945 with the U.S. Air Force's analysis unit while on leave from Caltech, rising to full professor in 1950 and retiring as professor emeritus in 1982. Throughout his career, he made foundational contributions to lattice and poset structures, including theorems on complemented lattices and modular varieties.^[4] Dilworth's theorem emerged from his research on partially ordered sets (posets) and was first published in 1950 in the Annals of Mathematics. In the paper "A Decomposition Theorem for Partially Ordered Sets," Dilworth proved that in any finite poset, the minimum number of chains required to cover the poset equals the size of the largest antichain. This result provided a precise tool for decomposing posets, with applications to matching theory and lattice embeddings. The proof addressed finite posets directly, using inductive arguments on the size of maximal antichains.^[5] The theorem built on earlier developments in lattice theory during the 1930s and 1940s, particularly the foundational work of Garrett Birkhoff, who established lattice theory as a rigorous discipline through his 1940 monograph Lattice Theory and studies on distributive lattices and order ideals. Dilworth's motivation stemmed from efforts to generalize results like Hall's marriage theorem and Menger's theorem on disjoint paths, while resolving open questions on poset decompositions tied to antichain cardinalities, as explored in prior work by Dushnik and Miller on poset dimensions. His theorem thus marked a key advancement in mid-20th-century combinatorics, linking chain partitions directly to antichain sizes.^[4]^[5]

Formal Statement

A partially ordered set, or poset, is a set P together with a binary relation \leq on P that is reflexive, antisymmetric, and transitive.^[6] In a poset P, a chain is a subset C \subseteq P in which every pair of elements is comparable under \leq (i.e., for all a, b \in C, either a \leq b or b \leq a), making C totally ordered.^[7] An antichain is a subset A \subseteq P in which no two distinct elements are comparable (i.e., for all distinct a, b \in A, neither a \leq b nor b \leq a).^[8] Dilworth's theorem asserts that for any finite poset P, the size of a maximum antichain in P equals the minimum number of chains whose union covers P (a chain partition of P).^[9] The width of P, denoted \mathrm{width}(P), is defined as the cardinality of a maximum antichain in P; the minimum size of a chain partition is often denoted \chi(P).^[10] Thus, the theorem can be expressed as

\mathrm{width}(P) = \min \{ k \mid P \text{ can be partitioned into } k \text{ chains} \}.

For example, consider the poset of all subsets of \{1,2\}, ordered by inclusion: \emptyset, \{1\}, \{2\}, \{1,2\}. The set \{\{1\}, \{2\}\} forms an antichain of size 2, which is maximum, so \mathrm{width}(P) = 2. This poset can be partitioned into 2 chains, such as \emptyset \subset \{1\} and \{2\} \subset \{1,2\}, confirming the theorem.

Key Concepts

Partial Orders, Chains, and Antichains

A partial order on a set P is a binary relation \leq that is reflexive, antisymmetric, and transitive. Reflexivity means that for every x \in P, x \leq x. Antisymmetry requires that if x \leq y and y \leq x, then x = y. Transitivity states that if x \leq y and y \leq z, then x \leq z.^[11]^[12] A set equipped with such a relation is called a partially ordered set, or poset. In a poset, not all pairs of elements need to be comparable; two elements x and y are incomparable, denoted x \parallel y, if neither x \leq y nor y \leq x. A chain in a poset is a subset where every pair of distinct elements is comparable, making it totally ordered under the induced relation. For example, the set \{1, 2, 3\} with the usual order $1 < 2 < 3 forms a chain.^[11]^[12] An antichain is a subset of a poset in which no two distinct elements are comparable. For instance, in a poset with elements a and b where a \parallel b, the set \{a, b\} is an antichain.^[11]^[12] A classic example of a poset is the Boolean lattice B_n, consisting of all subsets of an n-element set ordered by inclusion \subseteq. In B_3, for the ground set \{1,2,3\}, the singletons \{\{1\}, \{2\}, \{3\}\} form an antichain, while \emptyset \subset \{1\} \subset \{1,2\} \subset \{1,2,3\} is a chain.^[13] Posets are often visualized using Hasse diagrams, which depict elements as points with line segments connecting pairs related by the cover relation, omitting transitive edges for clarity.^[14] The cover relation in a poset holds between x and y (written x \prec y) if x < y and there exists no z such that x < z < y. This relation captures the immediate successors in the order.^[11]^[14] These notions of chains and antichains play a key role in defining the width of a poset as the cardinality of its largest antichain.^[11]

Poset Width and Chain Partitions

The width of a partially ordered set (poset) P, denoted \mathrm{width}(P), is the maximum cardinality of an antichain in P.^[9] This measure captures the "broadest" level of incomparability within the poset, reflecting how many elements can coexist without any ordering relations among them. A chain partition of a poset P is a collection of pairwise disjoint chains whose union equals P, thereby covering every element exactly once.^[9] The minimum chain partition number, often denoted \chi(P), is the smallest size of such a partition, i.e., the minimal number of chains required to decompose P in this manner.^[9] These partitions provide a way to "linearize" the poset into totally ordered components, with the minimum number indicating the inherent complexity of the partial order. One prominent application of these concepts arises in the Boolean lattice B_n, the poset of all subsets of an n-element set ordered by inclusion. Sperner's theorem establishes that the width of B_n is the cardinality of the largest rank (level), given by the middle binomial coefficient \binom{n}{\lfloor n/2 \rfloor}.^[2] This result highlights how the theorem identifies the subsets of size \lfloor n/2 \rfloor (or \lceil n/2 \rceil for even n) as forming the maximal antichain, underscoring the symmetric structure of the lattice. Consider a simple poset consisting of three elements a, b, and c with no comparabilities, forming a total antichain. Here, the width is 3, as \{a, b, c\} is the largest antichain. Any chain partition must consist of at least three singleton chains (e.g., \{a\}, \{b\}, \{c\}), since no two elements can be combined into a longer chain.^[9] This example illustrates the intuitive lower bound: the size of the largest antichain necessitates at least that many chains in any partition, as each chain can intersect an antichain in at most one element. These notions naturally suggest investigating whether the width of a poset always equals its minimum chain partition number, a question central to understanding the balance between incomparability and decomposability in partial orders.^[9]

Proofs

Inductive Proof

A standard inductive proof of Dilworth's theorem proceeds by mathematical induction on the number of elements in the finite poset P. The theorem states that the size of the maximum antichain equals the minimum number of chains in a chain partition. The direction that the maximum antichain size is at most the minimum chain partition size follows easily without induction: in any chain partition into k chains, an antichain can intersect each chain in at most one element, so its size is at most k. For the converse, assume P is nonempty and let k be the size of a maximum antichain in P. Proceed by induction on |P|. The base case |P| = 1 is trivial, as the singleton is both a chain and an antichain of size 1. For the inductive step, let t be a maximal element of P, and let P' = P \setminus \{t\}. By the inductive hypothesis, P' has a chain partition into r chains C_1, \dots, C_r, where r is the width (maximum antichain size) of P', so r \leq k. Let A_0 be a maximum antichain in P' of size r. Choose the partition such that the maximal elements s_i of each C_i form an antichain A = \{s_1, \dots, s_r\} of size r (possible by selecting appropriate tops). If there exists i such that t \geq s_i, then form the chain K = \{t\} \cup \{u \in C_i \mid u \leq s_i\} (appending t to the initial segment of C_i up to s_i). The remaining poset P \setminus K can be partitioned into r-1 chains (the other C_j minus nothing, and the tail of C_i above s_i if any, but since s_i maximal in C_i, it's just the other chains). Thus, P is partitioned into r chains. Since r \leq k, and if r < k, this would imply width of P at most r < k, contradiction unless r = k. If t \not\geq s_i for all i, then t is incomparable to all s_i. Since A is an antichain of size r, and t incomparable to them, A \cup \{t\} is an antichain of size r+1. But r+1 > k would contradict k being maximum, so this case implies r = k-1, and we partition P into the r chains plus the singleton \{t\}, totaling k chains. In both cases, P has a chain partition into k chains, completing the induction.^[11]

Proof Using Kőnig's Theorem

One alternative proof of Dilworth's theorem reduces the problem to Kőnig's theorem in bipartite graphs, which asserts that in any bipartite graph, the cardinality of a maximum matching equals the cardinality of a minimum vertex cover.^[15] Given a finite poset (P, \preceq), construct the bipartite graph G = (X \cup Y, E) where X = \{ x^- \mid x \in P \}, Y = \{ x^+ \mid x \in P \}, and there is an edge x^- y^+ \in E if and only if x \prec y (that is, x \preceq y and x \neq y).^[16] A matching M in G selects a set of edges with no shared vertices, corresponding to pairwise disjoint comparable pairs in P. To relate this to chain partitions, form a directed graph D on vertex set P by including an arc x \to y for each edge x^- y^+ \in M. The out-degree and in-degree of each vertex in D are at most 1, so D consists of disjoint directed paths and isolated vertices; each path (including singletons) is a chain in P since consecutive elements are comparable by the edge condition. Starting from |P| isolated vertices (trivial chains), each arc in M connects two components into one, reducing the total number of chains by 1. Thus, M yields a chain partition of P into exactly |P| - |M| chains. Taking a maximum matching of size \nu(G), the minimum chain partition size c(P) satisfies c(P) \leq |P| - \nu(G).^[15] Now consider a vertex cover R \subseteq X \cup Y of G, which intersects every edge in E. Define A = \{ x \in P \mid x^- \notin R \text{ and } x^+ \notin R \}. The set A forms an antichain in P: if x, y \in A with x \prec y, then the edge x^- y^+ has neither endpoint in R, contradicting that R covers all edges. Each vertex in R belongs to exactly one pair \{ z^-, z^+ \} for some z \in P, so R can exclude both representatives of at most |P| - |R| elements. Hence, |A| \geq |P| - |R|. For a minimum vertex cover of size \tau(G), the maximum antichain size (width) w(P) satisfies w(P) \geq |P| - \tau(G).^[16] By Kőnig's theorem, \nu(G) = \tau(G), so c(P) \leq |P| - \nu(G) = |P| - \tau(G) \leq w(P). The reverse inequality w(P) \leq c(P) holds because any antichain intersects each chain in a partition in at most one element, requiring at least w(P) chains to cover P. Therefore, w(P) = c(P).^[15]

Extensions and Duals

Extension to Infinite Posets

While Dilworth's theorem establishes equality between the size of the largest antichain and the minimum number of chains needed to cover a finite poset, this equality does not hold in general for infinite posets. However, the one-sided inequality—that the cardinality of the largest antichain is at most the minimum number of chains in any chain partition—remains true for arbitrary posets. This follows from the observation that each chain can intersect any antichain in at most one element, so an antichain of size \kappa requires at least \kappa chains to cover it. A key counterexample illustrating the failure of equality was constructed by Perles in 1963. For any infinite cardinal \kappa, Perles defined a poset P of cardinality \kappa consisting of a triangular array of elements \{p_{\zeta,\xi} : \zeta \leq \xi < \kappa\}, where p_{\zeta,\xi} < p_{\zeta',\xi'} only if the indices satisfy specific inclusion conditions that prevent long chains, and elements with \zeta < \zeta' and \xi > \xi' are incomparable. This poset has no infinite antichain (hence finite width, as all antichains are bounded in size), but it cannot be covered by fewer than \kappa chains, since any chain can contain at most one element from each "diagonal" level, forcing a large number of chains. Extensions of Dilworth's theorem to infinite posets often impose additional conditions to recover equality. For instance, if the poset is countable and has finite width w, then it can be partitioned into exactly w chains; this follows from a compactness argument using König's infinity lemma on the comparability graph or by iteratively extending partial partitions. More generally, for posets with no infinite antichains (finite width), equality holds unless the poset embeds a "Perles configuration," a structure isomorphic to the triangular array above; Abraham (1987) characterized such counterexamples precisely as those containing a \kappa^+-Perles type subposet for some infinite \kappa. Under the axiom of choice, further generalizations exist for posets of arbitrary width, but equality may still fail without restrictions like well-quasi-ordering (no infinite descending chains or antichains). For example, the poset of all finite subsets of a countably infinite set, ordered by inclusion, has infinite width (e.g., the infinite antichain of all singletons) and requires infinitely many chains for a cover, but the exact cardinal equality depends on the specific partition and does not contradict the one-sided inequality. These results highlight that while the finite case is robust, infinite posets require careful structural assumptions for the full theorem to apply.

Dual Theorem: Mirsky's Theorem

In order theory, the dual (or opposite) poset of a partially ordered set P = (X, \leq_P) is the poset P^\op = (X, \leq_{P^\op}) where x \leq_{P^\op} y if and only if y \leq_P x, reversing the order relation while preserving the structure of comparability.^[17] Mirsky's theorem, stated by Leon Mirsky in 1971, asserts that in any finite poset P, the height of P, denoted \mathrm{height}(P) and defined as the cardinality of a maximum-sized chain in P, equals the minimum number of antichains into which P can be partitioned.^[18] A proof of Mirsky's theorem follows immediately from Dilworth's theorem applied to the dual poset P^\op: the chains of P correspond precisely to the antichains of P^\op, and the antichains of P correspond to the chains of P^\op, so the minimum number of antichains partitioning P equals the width of P^\op, which by Dilworth's theorem equals the maximum size of an antichain in P^\op, i.e., the maximum size of a chain in P (the height of P).^[18] An alternative direct proof proceeds by induction on the height h = \mathrm{height}(P): if h = 1, then P is itself an antichain; otherwise, let M be the (nonempty) antichain of maximal elements of P, so \mathrm{height}(P \setminus M) < h, and by the inductive hypothesis P \setminus M partitions into h-1 antichains, yielding a partition of P into h antichains.^[18] For example, consider a total order on n elements, which forms a chain of size n; here \mathrm{height}(P) = n, and the minimum antichain partition consists of n singleton antichains.^[18] Mirsky's theorem is the natural dual to Dilworth's theorem under poset order reversal, interchanging the roles of chains and antichains as well as height and width.^[18] The theorem extends to infinite posets of finite height, where the inductive proof shows that any such poset partitions into \mathrm{height}(P) many antichains; the reverse inequality (minimum antichain partition number at least \mathrm{height}(P)) always holds, but equality fails in general for infinite posets without additional assumptions like finiteness, as there exist locally finite posets with no infinite chains yet requiring more than countably many antichains for a cover.^[18]^[19]

Applications

Comparability Graphs and Perfection

A comparability graph of a partially ordered set (poset) P is the undirected graph G with vertex set identical to that of P, and an edge between two vertices if and only if the corresponding elements are comparable in P.^[20] Equivalently, a graph is a comparability graph if its edges admit a transitive orientation, meaning an asymmetric orientation where if there are directed edges u \to v and v \to w, then there is also a directed edge u \to w; this orientation corresponds to the transitive closure of the poset relation.^[21] Comparability graphs form an important class in graph theory due to their structural properties and algorithmic tractability. A central result is that every comparability graph is perfect: for every induced subgraph H of a comparability graph G, the chromatic number \chi(H) equals the clique number \omega(H), where \chi(H) is the minimum number of colors needed to color the vertices of H such that no adjacent vertices share the same color, and \omega(H) is the size of the largest clique in H.^[22] This perfection follows from Dilworth's theorem and its dual, Mirsky's theorem, applied to the underlying poset. To see this, consider the comparability graph G of a poset P. A clique in G is a set of vertices where every pair is adjacent, corresponding to a chain in P (a totally ordered subset). Thus, \omega(G) equals the size of the maximum chain in P. A proper coloring of G partitions the vertices into independent sets, where each independent set has no edges, meaning the corresponding elements form an antichain in P (a set of pairwise incomparable elements). Therefore, \chi(G) equals the minimum number of antichains needed to cover P. By Mirsky's theorem, this minimum antichain cover equals the maximum chain size, so \chi(G) = \omega(G).^[9] The argument extends to induced subgraphs, as they correspond to induced subposets where the equality holds similarly.^[23] Dilworth's theorem provides a complementary perspective via the complement graph \overline{G}, where edges connect incomparable elements. In \overline{G}, a clique corresponds to an antichain in P, so \omega(\overline{G}) is the size of the maximum antichain. A proper coloring of \overline{G} partitions into independent sets of \overline{G}, which are cliques in G and thus chains in P, so \chi(\overline{G}) is the minimum number of chains covering P. By Dilworth's theorem, this equals the maximum antichain size, yielding \chi(\overline{G}) = \omega(\overline{G}).^[9] Since the perfection of \overline{G} (a cocomparability graph) implies that of G via the perfect graph theorem, this reinforces the result.^[22] A notable subclass consists of interval graphs, which are the comparability graphs of interval orders (posets where incomparability is defined by non-overlapping intervals on a line). As comparability graphs, interval graphs inherit perfection, allowing efficient coloring algorithms where the chromatic number equals the maximum clique size (the maximum number of overlapping intervals at any point).^[24] The connection between Dilworth's theorem and the perfection of comparability graphs emerged in the 1950s and 1960s, building on Dilworth's 1950 decomposition result and subsequent work linking poset structure to graph orientations.^[9]

Width in Special Partial Orders

Dilworth's theorem finds direct application in determining the width of the Boolean lattice B_n, the power set of an n-element set ordered by inclusion. Here, the width equals the size of the largest antichain, which consists of all subsets of size \lfloor n/2 \rfloor. Sperner's theorem establishes this as \binom{n}{\lfloor n/2 \rfloor}, and since the Boolean lattice is a distributive lattice, it satisfies the Sperner property, making the largest rank an antichain of maximum size. This result follows as a corollary of Dilworth's theorem combined with the LYM inequality, confirming that no larger antichain exists across multiple ranks.^[25] In product orders, such as the poset \times formed by the direct product of two finite chains of sizes m and n (with m \leq n), Dilworth's theorem yields the width as \min(m, n). This poset has the Sperner property, so the width is the size of the largest rank under the rank function given by the sum of coordinates minus 2. The ranks are the sets of elements with fixed sum k, and the maximum rank size occurs at the middle sums, equaling m. For instance, in

{{grok:render&&&type=render_inline_citation&&&citation_id=2&&&citation_type=wikipedia}} \times {{grok:render&&&type=render_inline_citation&&&citation_id=3&&&citation_type=wikipedia}}

, the ranks have sizes 1, 2, 2, 1, confirming width 2. More generally, for products of multiple chains k_1 \times \cdots \times k_r with k_1 \geq \cdots \geq k_r \geq 2, the width is the maximum rank size, determined by multinomial coefficients adjusted for the chain lengths.^[26] For tree posets, defined by the ancestry order in a rooted tree (where x < y if x is a proper ancestor of y), the width equals the number of leaves. The leaves form an antichain, as no leaf is an ancestor of another. By Dilworth's theorem, the minimum chain partition has size equal to the number of leaves, since each chain can include at most one leaf and the poset can be partitioned into paths from the root to each leaf, adjusted for disjointness by assigning branches separately after branching points. This holds because subtrees below any level have at least as many leaves as elements in that level, ensuring no larger antichain exists. In forests (disjoint unions of trees), the width is the total number of leaves across components. In the partition lattice \Pi_n, consisting of all partitions of an n-element set ordered by refinement (where \pi \leq \sigma if every block of \pi is contained in some block of \sigma), the width is the size of the largest antichain. The ranks are indexed by the number of blocks, with sizes given by the Stirling numbers of the second kind. Although the poset lacks the full Sperner property, the largest antichain exceeds the largest single rank by a factor of n^{1/35} asymptotically.^[27] Algorithmically, Dilworth's theorem enables polynomial-time computation of the width via bipartite matching, leveraging the proof using Kőnig's theorem. Construct a bipartite graph with vertex sets U and V, both copies of the poset elements, and edges from u \in U to v \in V if u < v in the poset. The size of the maximum matching \nu in this graph satisfies that the minimum chain cover number (and thus width) is |P| - \nu. This matching can be computed in O(|P|^{2.5}) time using Hopcroft-Karp, making width computation feasible for moderate-sized posets.^[28] A concrete example arises in the divisor lattice D(n) of a positive integer n, the poset of divisors of n ordered by divisibility. As a distributive lattice, it is isomorphic to the product of chains corresponding to the prime factorization n = p_1^{a_1} \cdots p_k^{a_k}, so its width is the largest rank size in this product poset, given by the maximum coefficient in the generating function \prod_{i=1}^k (1 + x + \cdots + x^{a_i}). This maximum occurs at the middle rank (exponent sum \approx \Omega(n)/2, where \Omega(n) counts prime factors with multiplicity), corresponding to divisors of size around \sqrt{n}. For instance, if n = 60 = 2^2 \times 3 \times 5, the chains are of lengths 3, 2, 2, and the width is 4, achieved by divisors like 4, 6, 10, 15 (all around \sqrt{60} \approx 7.75).^[26]

References

[1]
http://www.jstor.org/stable/1969503
[2]
Dilworth's theorem and extremal set theory (Chapter 6)
Theorem 6.1.Let P be a partially ordered finite set. The minimum number m of disjoint chains which together contain all elements of P is equal to the maximum ...Missing: applications | Show results with:applications
[3]
[PDF] Class 14 Dilworth's theorem and extremal set theory
Two applications of Dilworth's Theorem. (i) Let a1,a2,...,an2+1 be a sequence of real numbers. A sub-sequence i1 < i2 < ··· ik is said to be monotone ...
[4]
Robert Dilworth (1914 - 1993) - Biography - MacTutor
He received his B.S. degree in 1936 and remained at Caltech to undertake postgraduate work for his doctorate. At Caltech, Dilworth's doctoral studies were ...
[5]
https://www.jstor.org/stable/1969503
[6]
Partially Ordered Set -- from Wolfram MathWorld
A partially ordered set (or poset) is a set taken together with a partial order on it. Formally, a partially ordered set is defined as an ordered pair.
[7]
Chain -- from Wolfram MathWorld
Let be a finite partially ordered set. A chain in is a set of pairwise comparable elements (i.e., a totally ordered subset). The partial order length of is the ...
[8]
Antichain -- from Wolfram MathWorld
Let P be a finite partially ordered set, then an antichain in P is a set of pairwise incomparable elements. Antichains are also called Sperner systems in ...
[9]
[PDF] A Decomposition Theorem for Partially Ordered Sets - UCSD Math
If every set of k+1 elements in a partially ordered set is dependent, and at least one set of k is independent, then the set is a sum of k disjoint chains.Missing: antichains | Show results with:antichains
[10]
Dilworth's Lemma -- from Wolfram MathWorld
Dilworth's Lemma: The partial order width of a set P is equal to the minimum number of chains needed to cover P.
[11]
[PDF] Chains and Antichains
A is an antichain. Proof. Let Ai be an antichain of size k that contains si . ... Dilworth's theorem. µ1 = λ′. 1 (= ℓ(λ), the length or number of parts of λ) ...Missing: motivation | Show results with:motivation
[12]
[PDF] PARTIALLY ORDERED SETS
A chain in P corresponds to a monotone increasing subsequence. So, suppose that there are no monotone increasing sequences of length n + 1.
[13]
[PDF] Posets: Math 454 Lecture 17 (7/26/2017)
Jul 26, 2017 · We define the Boolean lattice to be the poset. Bn = (2[n],⊆). Example 9. If n is a number, the set D of divisors of n can be made into a poset.
[14]
[PDF] Partially Ordered Sets
Sep 29, 2008 · Posets can be represented geometrically by diagramms. The cover relation <c is defined by a <c b iff a<b and there is no c such that a<c<b ...
[15]
[PDF] 1 Lecture 6 Partially Ordered Sets (posets) — Ch.14
Feb 26, 2004 · Bipartite Matching Dilworth's theorem is actually equivalent to König's theorem for bipartite graphs. Let us start by stating König's theorem ...
[16]
[PDF] MATH 314 Dilworth's Theorem Feb 22
We proved two fundamental theorems about matchings in bipartite graphs: Theorem 1 (K˝onig's Theorem). If G is a bipartite graph, then α′(G) = β(G).
[17]
[PDF] combinatorial aspects of partially ordered sets
1.8. Antichains and Order Ideals. Definition 1.8. 1. A set A is an antichain (or Sperner family or clutter) of a poset P if A ⊆ P and any pair of elements of A ...<|control11|><|separator|>
[18]
https://www.jstor.org/stable/2316481
[19]
Obstacles to Extending Mirsky's Theorem | Order
Authors and Affiliations. Department of Mathematics, University of Connecticut ... Cite this article. Schmerl, J.H. Obstacles to Extending Mirsky's Theorem.
[20]
[PDF] 12 – Cover Graphs and Comparability Graphs - William T. Trotter
Nov 14, 2017 · Definition A graph G is a comparability graph when there is a poset P on the same ground set so that G is the comparability graph of P. Page ...
[21]
[PDF] Lecture 3: Comparability Graphs - CSE, IIT Delhi
This lecture develops the concepts of comparability and co-comparability graphs. Then, we define perfect graphs and their properties. 3.1 Comparability Graph.
[22]
[PDF] Lecture 7 1 Perfect Graph - MIT Mathematics
Feb 27, 2014 · The proof follows from Dilworth's theorem on posets. It was highly believed that the complement of any perfect graph G is perfect till finally ...
[23]
[PDF] Lecture 10: April 20, 2005 Perfect Graphs
Apr 20, 2005 · If G is the comparability graph of a poset P = (S, ≤) then the chromatic number of G is the minimum number of colors to color S such that the ...
[24]
[PDF] Comparability and Interval Graphs - Cornell eCommons
We give fast parallel algorithms for recognizing and representing comparabilit v graphs. the graphs that can be transitivel v oriented. and inter val graphs.
[25]
The width of downsets - ScienceDirect.com
Our main results are a Dilworth-type decomposition theorem for downsets, and a new proof of a result of Engel and Leck that determines the largest possible ...
[26]
Maximum antichains in the product of chains | Order
≥k n ≥2. Let M = k 1 − ∑ i = 2 n ( k i − 1 ) . P is known to have the Sperner property, which means that its maximum ranks are maximum antichains.Missing: largest two
[27]
Large antichains in the partition lattice - Canfield - Wiley Online Library
We show that the ratio of the size of the largest antichain to the size of the largest rank exceeds n1/35 for all n sufficiently large. References. 1 V. B. ...
[28]
[PDF] 22 – Solving the Dilworth Problem - William T. Trotter
Nov 14, 2017 · Theorem A poset of height h can be partitioned into h antichains. Proof As illustrated in the figure, we recursively strip off the minimal ...Missing: conjecture | Show results with:conjecture