On Better-Quasi-Ordering Countable Series-Parallel Orders
HTML articles powered by AMS MathViewer
- by Stéphan Thomassé PDF
- Trans. Amer. Math. Soc. 352 (2000), 2491-2505 Request permission
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
- 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 10.1016/0012-365X(85)90127-X
- T. Venkatarayudu, The $7$-$15$ problem, Proc. Indian Acad. Sci., Sect. A. 9 (1939), 531. MR 0000001, DOI 10.1090/gsm/058
- 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 10.1007/BF02020961
- P. Hebroni, Sur les inverses des éléments dérivables dans un anneau abstrait, C. R. Acad. Sci. Paris 209 (1939), 285–287 (French). MR 14
- 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 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 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 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
- Tadasi Nakayama, On Frobeniusean algebras. I, Ann. of Math. (2) 40 (1939), 611–633. MR 16, DOI 10.2307/1968946
- S. Thomassé, Thèse de doctorat, Lyon (1995).
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
- 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
- © Copyright 2000 American Mathematical Society
- 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
- MathSciNet review: 1624214