Talk:Antichain

Correction

[...]the non-existence of an antichain A of size n+1 in S is a necessary and sufficient condition for S to be the union of n total orders. That doesn't sound quite right. Surely, if S has no antichain of size n+1, then it doesn't have one of size n+2 either, and by this equivalence it would then be the union of n and n+1 total orders at the same time; in fact we could continue this reasoning to conclude that S is the union of n, n+1, n+2, ... total orders. Presumably the equivalence holds only for the minimal such n? --Eriatarka 13:29, 15 January 2006 (UTC)

Some combinatorics articles, some mathematical logic articles, and some algebra articles probably ought to link to this page. Michael Hardy 00:16, 25 Oct 2003 (UTC)

Agreed. Don't think Dilworth's theorem is here? Or Sperner's lemma?

Charles Matthews 09:50, 25 Oct 2003 (UTC)

I think the definition of join and meet are both broken, and should be defined as follows:

$A\vee B=\{x\in A\cup B\mid \not \exists y\in A\cup B{\mbox{ s.t. }}x<y\}.$

$A\wedge B=\{x\in L_{A}\cap L_{B}\mid \not \exists y\in L_{A}\cap L_{B}{\mbox{ s.t. }}x<y\}.$

--Iwehrman (talk) 10:38, 13 August 2009 (UTC)

Height and width are not properly defined

Width is defined as the cardinality of a maximum antichain, but such antichain need not exist. As an example (for height), we could take the disjoint union of all sets $\{1,\ldots ,n\}$ for positive integers $n$ (with the standard ordering on all the components and no new relations). In this poset there are chains of every positive length, but there is no maximum chain. So we should either say that height/width are not always defined, or we should define them in terms of suprema.

--Leen Droogendijk (talk) 10:13, 11 September 2017 (UTC)

The 'Height and width' section seems incorrect (beside the above comment)

It states: 1 A maximal antichain is an antichain that is not a proper subset of any other antichain. 2 A maximum antichain is an antichain that has cardinality at least as large as every other antichain. 3 The width of a partially ordered set is the cardinality of a maximum antichain. 4 Any antichain can intersect any chain in at most one element...

Statements 1 and 4 are fine.

Statement 2 is not. (beyond the above comment, that I would solve by having infinite width) First it is not correctly stated 'at least as large as every other antichain'. I take it to mean: 'All maximum antichains have the same cardinality'. But this is not correct. Consider the power set $P$ of a finite set $E$ with the inclusion order. The set {$E$} is an maximal antichain; its cardinal is 1. If $E$ contains an element $e$, the set {$E$\{$e$},{$e$}} is also a maximal antichain, its cardinal is 2. I feel that the confusion comes from the fact that $E$ and $E$\{$e$}∪{$e$} have indeed the same cardinality. But this is related to a particular kind of order and does not apply to order-theory as a whole.

Statement 3 is consequently not well-defined. It should be: 'The partial order width of $P$ is the maximum cardinal number of an antichain in $P$' as stated in the Wolfram page linked at the end of this one.

-- Jérôme Euzenat 194.199.22.76 (talk) 17:06, 13 February 2018 (UTC)

References

Perhaps you are getting confused by the fact that the word "maximal" in 1 and the word "maximum" in 2 look so similar? They are not the same word and they have different meanings. In your example, your 1-element and 2-element antichains are maximal, but (unless E has only two elements) neither is maximum. —David Eppstein (talk) 17:57, 13 February 2018 (UTC)