|
On Better-Quasi-Ordering Countable Series-Parallel Orders
Author(s):
Stéphan
Thomassé
Journal:
Trans. Amer. Math. Soc.
352
(2000),
2491-2505.
MSC (1991):
Primary 05C20;
Secondary 05C05, 08A65, 05C75
Posted:
April 7, 1999
Retrieve article in:
PDF
This article is available free of charge
Abstract |
References |
Similar articles |
Additional information
Abstract:
We prove that any infinite sequence of countable series-parallel orders contains an increasing (with respect to embedding) infinite subsequence. This result generalizes Laver's and Corominas' theorems concerning better-quasi-order of the classes of countable chains and trees.
References:
- [1]
- E. Corominas, On better-quasi-ordering countable trees, in Proceedings of the Conference on Ordered Sets and their Applications (L'Arbresle, July 1982), (M. Pouzet and D. Richard, eds.), Discrete Math., 53 (1984), 35-53. MR 86k:06001
- [2]
- B. Dushnik and E.W. Miller, Concerning similarity transformations of linearly ordered sets, Bull. Amer. Math. Soc., 46 (1940), 322-326. MR 1:318g
- [3]
- R. Fraïssé, L'intervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture d'une relation, in Orders, Description and Roles, (M. Pouzet and D. Richard, eds.), Annals of Discrete Math., 23 North-Holland, (1984), 313-341. MR 85k:06001
- [4]
- T. Gallai, Transitiv Orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18 (1967), 25-66. MR 36:5026
- [5]
- G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc., 2 (1952), 326-336. MR 14:238e
- [6]
- P. Ille, Private communication.
- [7]
- D. Kelly, Comparability graphs, in Graphs and Orders, (I. Rival ed.), D. Reidel Publishing Company, (1985), 3-40. MR 87g:05190
- [8]
- J. B. Kruskal, Well-quasi-ordering, the tree theorem and Vázsonyi's conjecture, Trans. Amer. Math. Soc., 95 (1960), 210-225. MR 22:2566
- [9]
- R. Laver, On Fraïssé's order type conjecture, Ann. of Math., 93 (1971), 89-111. MR 43:4731
- [10]
- E.C. Milner, Basic wqo and bqo theory, in Graphs and Orders, (I. Rival ed.), D. Reidel Publishing Company, (1985), 487-502. MR 87h:04004
- [11]
- C.St.J.A. Nash-Williams, On better-quasi-ordering transfinite sequences, Proc. Camb. Phil. Soc., 64 (1968), 273-290. MR 36:5001
- [12]
- M. Pouzet, Applications of well-quasi-ordering and better-quasi-ordering, in Graphs and Orders, (I. Rival ed.), D. Reidel Publishing Company, (1985), 503-519. MR 87g:06014
- [13]
- R. Rado, Partial well-ordering of sets of vectors, Mathematika, 1 (1954), 89-95. MR 16:576b
- [14]
- S. Thomassé, Thèse de doctorat, Lyon (1995).
Similar Articles:
Retrieve articles in Transactions of the American Mathematical Society
with MSC
(1991):
05C20,
05C05, 08A65, 05C75
Retrieve articles in all Journals with MSC
(1991):
05C20,
05C05, 08A65, 05C75
Additional Information:
Stéphan
Thomassé
Affiliation:
Laboratoire LMD, UFR de Mathématiques, Université Claude Bernard 43, Boulevard du 11 novembre 1918, 69622 Villeurbanne Cedex, France
Email:
thomasse@jonas.univ-lyon1.fr
DOI:
10.1090/S0002-9947-99-02400-9
PII:
S 0002-9947(99)02400-9
Keywords:
Better-quasi-order,
interval,
series-parallel graphs,
series-parallel orders,
structured trees,
well-quasi-order
Received by editor(s):
October 4, 1995
Received by editor(s) in revised form:
January 6, 1998
Posted:
April 7, 1999
Additional Notes:
This work was supported in part by the DIMANET program, Human Capital and Mobility (HCM) Contract No. ERBCHRXCT 940429
Copyright of article:
Copyright
2000,
American Mathematical Society
|
Comments: webmaster@ams.org