maths.free › Combinatorics & Graph Theory › Partially Ordered Sets › Dilworth's Chain Covering Theorem and its Dual

Dilworth's Chain Covering Theorem and its Dual

In this section, we prove the following theorem of R.P. Dilworth, which is truly one of the classic results of combinatorial mathematics.

Dilworth's Chain Covering Theorem and its Dual

In this section, we prove the following theorem of R.P. Dilworth, which is truly one of the classic results of combinatorial mathematics.

Before proceeding with the proof of Dilworth's theorem later in this section, we pause to discuss the dual version for partitions into antichains, as it is even easier to prove.

Theorem: Dual of Dilworth's Theorem

If \(\PXP\) is a poset and \(\height(P)=h\), then there exists a partition \(X=A_1\cup A_2\cup\dots\cup A_h\), where \(A_i\) is an antichain for \(i=1,2,\dots,h\). Furthermore, there is no partition using fewer antichains.

Proof

For each \(x\in X\), let \(\height(x)\) be the largest integer \(t\) for which there exists a chain \[\begin{aligned}\end{aligned}\] with \(x=x_t\). Evidently, \(\height(x)\le h\) for all \(x\in X\). Then for each \(i=1,2,\dots,h\), let \(A_i=\{x\in X:\height(x)=i\}\). It is easy to see that each \(A_i\) is an antichain, as if \(x,y\in A_i\) are such that \(x\lt y\), then there is a chain \(x_1\lt x_2\lt \cdots\lt x_i=x \lt x_{i+i}=y\), so \(\height(y)\ge i+1\). Since \(\height(P)=h\), there is a maximum chain \(C=\{x_1,x_2,\dots,x_h\}\). If it were possible to partition \(\bfP\) into \(t\lt h\) antichains, then by the Pigeon Hole Principle, one of the antichains would contain two points from \(C\), but this is not possible.

When \(\PXP\) is a poset, a point \(x\in X\) with \(\height(x)=1\) is called a minimal point of \(\bfP\). We denote the set of all minimal points of a poset \(\PXP\) by \(\min(X,P)\).Since we use the notation \(\bfP= (X,P)\) for a poset, the set of minimal elements can be denoted by \(\min(\bfP)\) or \(\min(X,P)\). This convention will be used for all set valued and integer valued functions of posets.

The argument given for the proof of yields an efficient algorithm, one that is defined recursively. Set \(\bfP_0= \bfP\). If \(\bfP_i\) has been defined and \(\bfP_i\neq \emptyset\), let \(A_i=\min(\bfP_i)\) and then let \(\bfP_{i+1}\) denote the subposet remaining when \(A_i\) is removed from \(\bfP_i\).

In , we illustrate the antichain partition provided by this algorithm for the \(17\) point poset from . The darkened points form a chain of size\(5\).

Maximal antichains and maximum antichains are defined analogously.

Condensed: the full section is in Keller & Trotter, Applied Combinatorics.

இப்போது நீங்கள் கணிப்பொறி இதற்கு தீர்வு கூற முடியாது, ஆனால் இதன் துண்டுகள் கணிக்கக்கூடியவை. கீழே உள்ள ஒன்றை முயற்சி செய்யவும் அல்லது உங்கள் சொந்தத்தை உள்ளிடவும்.

பயிற்சி (1)

ஒவ்வொரு கேள்வியும் முதலில் காகிதத்தில் முயற்சி செய்யவும். சரிபார்க்க பதிலைக் காட்டவும்; சரிபார்த்தவைகளை ஒவ்வொரு படிக்கும் தீர்ப்பாளர்களில் திறக்கலாம்.

Consider implementing an algorithm from on the poset of . First, verify that you agree with the labeling of the points with their heights, which assigns the points to antichains. Explain why this poset is a good illustration of why finding the chain of five points is best done by starting with a point labeled \(5\) and working down instead of starting with a point labeled \(1\) and working up.

உங்களின் வேலையை தொடரவும்

இலவச கணக்கு ஒவ்வொரு பாடத்திலும் குறிப்புகளை சேர்க்கும், நீங்கள் முடித்ததை பதிவு செய்கிறது, உங்கள் தீர்த்த பிரச்சனைகள் ஒரு இடத்தில், மற்றும் ஒரு ஆசிரியரை நீங்கள் இந்த பக்கத்தை பற்றி கேட்கலாம். கணிதமே அனைவருக்கும் திறந்துள்ளது, நுழைந்தாலும் இல்லையென்றாலும்.

பதிவு செய் உள்நுழை

இங்கே பயன்படுத்தப்பட்ட குறியீடுகள்

முழுமையான வரையறை, ஒரு படத்தை, மற்றும் ஒவ்வொரு எழுத்தும் என்ன அர்த்தம் என்று எந்த சின்னத்தையும் அழுத்து.

கேள்விகள்

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

இந்தப் பக்கத்தின் பகுதிகள் பின்வருமாறு மாற்றப்பட்டுள்ளன Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). இங்கு மீண்டும் மீண்டும் விளக்கப்பட்டுள்ளது; தவறுகளே நம்முடையவை.

மேலும் Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion, exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs