On Better-Quasi-Ordering Countable Series-Parallel Orders
Author:
Stéphan Thomassé
Journal:
Trans. Amer. Math. Soc. 352 (2000), 2491-2505
MSC (1991):
Primary 05C20; Secondary 05C05, 08A65, 05C75
DOI:
https://doi.org/10.1090/S0002-9947-99-02400-9
Published electronically:
April 7, 1999
MathSciNet review:
1624214
Full-text PDF Free Access
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.
- E. Corominas, On better quasi-ordering countable trees, Discrete Math. 53 (1985), 35–53 (English, with French summary). Special volume on ordered sets and their applications (L’Arbresle, 1982). MR 786475, DOI https://doi.org/10.1016/0012-365X%2885%2990127-X
- B. Dushnik and E.W. Miller, Concerning similarity transformations of linearly ordered sets, Bull. Amer. Math. Soc., 46 (1940), 322-326.
- Maurice Pouzet and Denis Richard (eds.), Orders: description and roles, North-Holland Mathematics Studies, vol. 99, North-Holland Publishing Co., Amsterdam, 1984. Annals of Discrete Mathematics, 23. MR 779841
- T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66 (German). MR 221974, DOI https://doi.org/10.1007/BF02020961
- G. Higman, Ordering by divisibility in abstract algebras, Proc. London Math. Soc., 2 (1952), 326-336.
- P. Ille, Private communication.
- David Kelly, Comparability graphs, Graphs and order (Banff, Alta., 1984) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 147, Reidel, Dordrecht, 1985, pp. 3–40. MR 818492
- J. B. Kruskal, Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjecture, Trans. Amer. Math. Soc. 95 (1960), 210–225. MR 111704, DOI https://doi.org/10.1090/S0002-9947-1960-0111704-1
- Richard Laver, On Fraïssé’s order type conjecture, Ann. of Math. (2) 93 (1971), 89–111. MR 279005, DOI https://doi.org/10.2307/1970754
- E. C. Milner, Basic wqo- and bqo-theory, Graphs and order (Banff, Alta., 1984) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 147, Reidel, Dordrecht, 1985, pp. 487–502. MR 818505
- C. St. J. A. Nash-Williams, On better-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 64 (1968), 273–290. MR 221949, DOI https://doi.org/10.1017/s030500410004281x
- M. Pouzet, Applications of well quasi-ordering and better quasi-ordering, Graphs and order (Banff, Alta., 1984) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 147, Reidel, Dordrecht, 1985, pp. 503–519. MR 818506
- R. Rado, Partial well-ordering of sets of vectors, Mathematika, 1 (1954), 89-95.
- S. Thomassé, Thèse de doctorat, Lyon (1995).
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
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
Published electronically:
April 7, 1999
Additional Notes:
This work was supported in part by the DIMANET program, Human Capital and Mobility (HCM) Contract No. ERBCHRXCT 940429
Article copyright:
© Copyright 2000
American Mathematical Society
