Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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

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 [Enhancements On Off] (What's this?)

  • [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: 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

American Mathematical Society