SpringerLink
Log in

A Proof of the Alternate Thomassé Conjecture for Countable N-Free Posets

  • Published:
Order Aims and scope Submit manuscript

Abstract

An N-free poset is a poset whose comparability graph does not embed an induced path with four vertices. We use the well-quasi-order property of the class of countable N-free posets and some labelled ordered trees to show that a countable N-free poset has one or infinitely many siblings, up to isomorphism. This, partially proves a conjecture stated by Thomassé for this class.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Data Availability Statement

Data sharing not applicable to this article as no data sets were generated or analysed during this study.

References

  1. Abdi, D.: Siblings of direct sums of chains (2022). https://arxiv.org/abs/2209.03477

  2. Abdi, D., Laflamme, C., Tateno, A., Woodrow, R.: An example of Tateno disproving conjectures of Bonato-Tardif, Thomassé, and Tyomkyn (2022). https://arxiv.org/abs/2205.14679

  3. Bonato, A., Bruhn, H., Diestel, R., Sprüssel, Ph.: Twins of rayless graphs. J. Combinatorial Theory Ser. B 101, 60–65 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  4. Boudabbous, Y., Delhommé, C.: Prechains and self-duality. Discrete Math. 312, 1743–1765 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  5. Braunfeld, S., Laskowski, M.C.: Counting siblings in universal theories (2021). ar**v:1910.11230

  6. Bonato, A., Tardif, C.: Mutually embeddable graphs and the tree alternative conjecture. J. Combin. Theory Ser. B 96, 874–880 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Courcelle, B., Delhommé, Ch.: The modular decomposition of countable graphs. Definitions and construction in monadic second-order logic, Theoretical Computer Science 394, 1–38 (2008)

    MATH  Google Scholar 

  8. Habib, M., Jegou, R.: \(N\)-free posets as generalisations of series-parallel posets. Discret. Appl. Math. 12, 279–291 (1985)

    Article  MATH  Google Scholar 

  9. Hahn, G., Pouzet, M., Woodrow, R.: Siblings of countable cographs (2020). ar**v:2004.12457

  10. Jung, H.A.: On a class of posets and the corresponding comparability graphs. Journal of Combinatorial Theory, Series B 24, 125–133 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  11. Kelly, D.: Comparability graphs, Graphs and Orders. In: Rival, I. (ed.), pp. 3–40. D. Reidel Publishing Company (1985)

  12. Laver, R.: On Fraïssé’s order type conjecture. Ann. Math. 93, 89–111 (1971). MR 43:4731

  13. Laflamme, C., Pouzet, M., Sauer, N.: Invariant subsets of scattered trees and the tree alternative property of Bonato and Tardif. Abh. Math. Semin. Univ. Hambg. 87, 369–408 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  14. Laflamme, C., Pouzet, M., Sauer, N., Woodrow, R.: Siblings of an \(\aleph _0\)-categorical relational structure. Contrib. Discrete Math. 16(2), 90–127 (2021)

    MathSciNet  MATH  Google Scholar 

  15. Laflamme, C., Pouzet, M., Sauer, N., Zaguia, I.: Pairs of orthogonal countable ordinals. Discrete Math. 335, 35–44 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  16. Laflamme, C., Pouzet, M., Woodrow, R.: Equimorphy- the case of chains. Arch. Math. Logic 56(7–8), 811–829 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  17. Tateno, A.: Mutually embeddable trees and a counterexample to the Tree Alternative Conjecture, unpublished manuscript, 32 pages, (2008)

  18. Thomassé, S.: Conjectures on countable relations, circulating manuscript, 17p. (2000)

  19. Thomassé, S.: On better-quasi-ordering countable series-parallel orders. Trans. Amer. Math. Soc. 352(6), 2491–2505 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  20. Tyomkyn, M.: A proof of the rooted tree alternative conjecture. Discret. Math. 309, 5963–5967 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Tyomkyn, M.: Personal communication (2020)

Download references

Acknowledgements

I would like to thank my PhD supervisors Professor Robert Woodrow and Professor Claude Laflamme for suggesting this problem and for their help and advice.

Funding

No funding was received for conducting this study.

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada

    Davoud Abdi

Authors
  1. Davoud Abdi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Davoud Abdi.

Ethics declarations

Conflicts of interest/Competing interests

The author has no conflicts of interest to declare that are relevant to the content of this article.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This paper is a project as part of author’s thesis under supervision of Dr. Claude Laflamme and Dr. Robert Woodrow at the Department of Mathematics and Statistics, University of Calgary, Calgary, AB, Canada (2017-2022).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Abdi, D. A Proof of the Alternate Thomassé Conjecture for Countable N-Free Posets. Order (2023). https://doi.org/10.1007/s11083-023-09650-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11083-023-09650-w

Keywords

Search

Navigation