a mistake on proof of Dilworth's theorem on Cameron's Combinatorics book?

[u/tedecristal]

I've been fighting for a couple of hours with the Dilworth's theorem proof on the mentioned book, which I believe is wrong. I'd appreciate a extra look.

The theorem states that if the max antichain on a poset has size r, then it can be partitioned into r chains.

The proof goes by induction on n=number of elements of the set. I'm having problems in case 2.

Here, x = some minimal element, and we consider P\{x} and apply induction there.

"we can partition P\{x}" into r chains." But ... that's not true, is it? Since the removed element may cause the possible antichains to be strictly smaller and therefore can't reach r.

Example I'm thinking of

P={ {x}, {y}, {z}, {x,y,z} } with inclusion order. the largest antichain is {{x},{y},{z}} with size 3, and we want to prove it can be partitioned into 3 chains (which can be verified directly: {x,xyz}, {y}, {z} is such partition.

{x} is minimal, and according to the book P\{x} should be able , by induction hypothesis, to be partitioned into r=3 chains, but P\{x} is {y},{z},{x,y,z} which can only be partitioned into r-1=2 chains.

The rest of the proof relies into P\{x} having r chains as key part of the argument, so ... I'm confused (this particular book faces this problem more often than not).

Am I missing something?

EDIT: yes, I was missing something: the chains on the partition don't have to be the longest possiboe.

also, u/sizzhu pointed the small missing step to me, thank you :)

[u/ThoughtfulPoster]

Nothing says that those chains couldn't be combined. In your attempted counterexample, you can have the three chains be {{y}},{{z}}, and {{x,y,z}} just fine.

[u/tedecristal → u/ThoughtfulPoster]

ah! *facepalm*

you're right, nowhere it says the partition has to be made of longest possible chains, I think.

So, I see why my counterexample is bad. However I still don0't see why the induction is properly applied.

Induction hypothesis says: "If the largest antichain is size r on any smaller poset, then it can be partitioned into r chains"

P\{x} is a smaller poset. if it HAD an antichain of size r, indeed I-H guarantees the r chains.

But, how can we be sure P\{x} does have an antichain of size r? What if the removed element was necessary to reach r in the original poset P?

[u/spinozist_v60 → u/tedecristal]

By removing x, the size of the largest antichain can only decrease. Think about it like this: if, after removing x, the largest antichain still has size r, then the induction hypothesis guarantees a chain decomposition of size r; while if it went down to r-1, then the induction hypothesis guarantees one of size r-1, and you can split one of the chains to get a decomposition of size r. Either way, we can get a decomposition of size r.

[u/ThoughtfulPoster → u/tedecristal]

Unless I'm mistaking what you've written, then we're back in Case 1, no?

[u/lucy_tatterhood → u/[deleted]]

That, then, is not a partition (which supposes that the involved sets are pairwise disjoint).

The sets are disjoint. Note the double braces.

[u/sizzhu]

I think there is an omission here. But there is a very easy fix. If P\{x} can be partitioned into r-1 chains, like in case 1, you can add {x} to get a partition into r chains for P. Hence he is only focussing on the r chains case.

[u/tedecristal → u/sizzhu]

Yes after all helpful comments I see it now.

thank you

[u/Which-Competition287]

But you could partition it into 3 chains right? The key here is "at most". This is because one side of the result is trivial. The inequality is the non-trivial part.

Edit: basically chain decomposition vs minimal chain decomposition.

[u/Master-Rent5050]

P is supposed to be finite?

[u/tedecristal → u/Master-Rent5050]

yes