Talk:Well partial order
From Wikipedia, the free encyclopedia
Shouldn't this concept be defined by saying every nonempty subset of a well-partially-ordered set has minimal elements? Michael Hardy 00:09, 23 Feb 2004 (UTC)
No. WPO also includes no infinite antichains; an infinite antichain has (infinitely many) minimal elements. Also, that graph minors are a WPO is equivalent to Robertson-Seymour: in one direction, the set of graphs not in the downward-closed set is upward-closed, the minimal elements are an antichain, and so the set of minimal forbidden graphs is finite (all of this up to isomorphism). In the other direction, it's trivial to show that there is no infinite descending chain, and if there is an infinite antichain (the other way the WPO definition can fail), then the graphs that do not lie above this antichain are a downward-closed set with an infinite set of forbidden minors, contradicting R-S. I'm reverting the comment about R-S. Populus 19:35, 2 Jun 2004 (UTC)
A question about nomenclature: is the name Well Partial Order standard? In set theory, they define a well founded partial order, as a partially ordered set, such that every non-empty subset has a minimal element (see for instance [K. Kunen, Set theory]); therefore, there is space for confusion. Moreover, I have seen the term "Noetherian Order" used instead of WPO (in the PhD thesis of M. Schmeling). --Manta 17:12, 30 Mar 2005 (UTC)
[edit] Merge with Well-quasi-ordering?
I suggested the merge. The main concept behing wqo and wpo are the same even though the technicalities may differ slightly. We need a single article in an encyclopedia and the job of helping you find out where is the article is better left to indexes, links, redirects, disambiguation pages, etc. Wikipedia is not a dictionary.
The resulting article can list other variants like better-quasi-orderings etc. Btw, comparing the variants is more natural inside a single article.
PhS 10:39, 5 September 2005 (UTC)
I think we need to merge and call the result well-quasi-ordering. It's the standard name given to a well-developed section of combinatorics. I cite the following as references:
1. Kruskal, J. The Theory of well-quasi-ordering: a frequently discovered concept. J. Combinatoriral Theory 13 (1972), 297-305
2. Nash-Williams, C. St J.A. On well quasi-ordering infinite trees. Proc. Cambridge Philos. Soc. 61 (1965), 697-720
3. Laver, L. Well-quasi-orderings and sets of finite sequences. Proc. Cambridge Philos. Soc. 79 (1976), 1-10
4. Robertson, N; Seymour, P.D. Graph Minors. XIX. Well-quasi-ordering on a surface. J. Combinatorial Theory, Series B 90 (2004) 325-385
I merged the two articles today. PhS 13:29, 25 February 2006 (UTC)
