Talk:Dilworth's theorem

History

Look at this.Kope (talk) 15:26, 8 March 2009 (UTC)

Locally finite posets?

Does anyone know if Dilworth's Theorem holds for locally finite posets? I'm having a hard time digging up a reference one way or another. (The Peles counterexample is not locally finite.) Vince Vatter (talk) 18:25, 6 June 2009 (UTC)

Examples?

Seriously, someone went through all the trouble of posting this without posting a single example? Ridiculous. —Preceding unsigned comment added by 66.49.227.118 (talk) 18:13, 25 January 2011 (UTC)

There are three examples in the article already: the one in the figure, the one involving Boolean lattices, and the one involving divisibility. They are not in a section with a big heading "EXAMPLES" but that doesn't make them non-examples. On the other hand, maybe they could use to be spelled out in more detail. —David Eppstein (talk) 18:57, 25 January 2011 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 2 external links on Dilworth's theorem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20070714201213/http://planetmath.org/encyclopedia/DualOfDilworthsTheorem.html to http://planetmath.org/encyclopedia/DualOfDilworthsTheorem.html
• Added archive https://web.archive.org/web/20110720134637/http://www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/10.pdf to http://www.classes.cs.uchicago.edu/archive/2005/spring/37200-1/notes/10.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 06:14, 13 December 2016 (UTC)

Chain decompositions

I've noticed "chain decomposition" redirects here, is there any good reason it does not have its own page? I don't the concept is so well defined here. LudwikSzymonJaniuk (talk) 12:40, 22 February 2019 (UTC)

@LudwikSzymonJaniuk: Maybe you mean Heavy path decomposition? wumbolo ^^^ 14:23, 22 February 2019 (UTC)

That's related, but not the same. In the context of this theorem, a chain decomposition would be a partition of a partial order into total orders. The theorem states how many total orders you need. I'm not sure, is there much to say about chain decompositions beyond that? —David Eppstein (talk) 17:21, 22 February 2019 (UTC)

I just came here trying to understand what the definition of chain decomposition is, and I didn't find it. LudwikSzymonJaniuk (talk) 20:33, 25 February 2019 (UTC)

The definition is actually right there in the first sentence of the article. It's just not stated that it's the definition of that term. —David Eppstein (talk) 21:40, 25 February 2019 (UTC)

Proof using König's theorem

The article says "Let A be the set of elements of S that do not correspond to any vertex in C; then A has at least n - m elements". So how does it prove that the size of the biggest antichain and of the smallest partition into chains is equal? To me there only seems to be a lower bound on the antichain size. Llama carl (talk) 17:44, 16 March 2019 (UTC)

The matching upper bound is very very easy. So proving the lower bound is the main part. —David Eppstein (talk) 17:47, 16 March 2019 (UTC)

Wordyness of Statement of Theorem

The current statement of the theorem is excessively wordy and bogged down with definitions such as antichain that have their own separate page. I propose that we change the first section to be:

"Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician Robert P. Dilworth (1950).

Dilworth's theorem states that, in any finite partially ordered set, the largest antichain has the same size as the minimum number of chains needed to cover the partially ordered set.

A version of the theorem for infinite partially ordered sets states that, when there exists a decomposition into finitely many chains, or when there exists a finite upper bound on the size of an antichain, the sizes of the largest antichain and of the smallest chain decomposition are again equal. Where a chain decomposition is a partition of the elements of the order into disjoint chains."

This is more inline with other pages dedicated to theorems for ex: Vizing's theorem. The definition of things like antichain and chain decomposition should be on their/have own pages. WhimsicalRuben (talk) 20:12, 14 August 2024 (UTC)

Per WP:TECHNICAL, I think we should gloss the technical terms used here at least one level down. The definition of things like antichain do have their own pages, but if we assume that readers already know those terms or will follow links to figure them out, we limit our readership to, basically, the people who already know the statement of the theorem. We should aim for a broader audience. If you're looking for a brief statement before all of the definitions of terms, we have one: the theorem "characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains." —David Eppstein (talk) 22:21, 14 August 2024 (UTC)

I agree that the current statement is too wordy and takes too long to get to the actual statement of the theorem. And I like having the statement in its own paragraph, as in your edit.

I might even go one step further, and have the statement of the theorem be the first sentence. The sentence describing it as characterizing the width of posets can then come afterwards. But that's just a stylistic preference. I think your edit is good.

Regarding description sentence vs statement of theorem sentence order, I can find examples of both:

• An article that leads with the description, then has the statement of the theorem as the second sentence: Pythagorean Theorem.
• An article that leads with the statement of the theorem: Hairy ball theorem.

2601:18D:4500:80:54A4:5946:E4D8:9C7E (talk) 16:22, 19 August 2024 (UTC)