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.
- [1] 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, https://doi.org/10.1016/0012-365X(85)90127-X
- [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] 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
- [4] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967), 25–66 (German). MR 221974, https://doi.org/10.1007/BF02020961
- [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] 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
- [8] J. B. Kruskal, Well-quasi-ordering, the Tree Theorem, and Vazsonyi’s conjecture, Trans. Amer. Math. Soc. 95 (1960), 210–225. MR 111704, https://doi.org/10.1090/S0002-9947-1960-0111704-1
- [9] Richard Laver, On Fraïssé’s order type conjecture, Ann. of Math. (2) 93 (1971), 89–111. MR 279005, https://doi.org/10.2307/1970754
- [10] 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
- [11] C. St. J. A. Nash-Williams, On better-quasi-ordering transfinite sequences, Proc. Cambridge Philos. Soc. 64 (1968), 273–290. MR 221949, https://doi.org/10.1017/s030500410004281x
- [12] 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
- [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).
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:
https://doi.org/10.1090/S0002-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
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
