Chain Dominated Orders | Order Skip to main content
Springer Nature Link
Log in

Chain Dominated Orders

  • Published:
Order Aims and scope Submit manuscript

Abstract

We study finite partial orders which have a chain such that every element of the order either belongs to this chain or has all its covers in this chain. We show that such orders are exactly the orders being both interval orders and truncated lattices. We prove that their jump number is polynomially tractable and that their dimension is unbounded. We also show that every order admits a visibility model having such an order as host.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Birkhoff, G.: Lattice theory. American Mathematical Society Colloquium Publications Volume XXV (1967)

  2. Bogart, K.P., Rabinovich, I., Trotter, W.T.: A bound on the dimension of interval orders. J. Combin. Theory, Ser. A 21(3), 319–328 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  3. Chein, M., Martin, P.: Sur le nombre de sauts d'une forêt. C. R. Acad. Sci. Paris, Sér. A 275, 159–161 (1972)

    MATH  MathSciNet  Google Scholar 

  4. Even, S., Kariv, O.: An \(\mathcal{O}(n^{2.5})\) algorithm for maximum matching in general graphs. In: 16th Annual Symposium on Foundations of Computer Science (Berkeley, California), pp. 100–112 (1975)

  5. Freese, R., Ježek, J., Nation, J.B.: Free lattices. Math. Surveys Monogr. 42 (1995)

  6. Fishburn, P.C.: Intransitive indifference with unequal indifference intervals. J. Math. Psych. 7, 144–149 (1970)

    Article  MATH  MathSciNet  Google Scholar 

  7. Fishburn, P.C.: Interval Orders and Interval Graphs: A Study of Partially Ordered Sets. Wiley, Interscience Publication New York (1985)

  8. Gabow, H.N.: A linear time recognition algorithm for interval dags. Inform. Process. Lett. 12, 20–22 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  9. Guenver, G.-B., Rampon, J.-X.: Split orders. Discrete Math. 276(1–3), 249–267 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  10. Hiraguchi, T.: On the dimension of orders. Sci. Rep. Kanazawa Univ. 4(1), 1–20 (1955)

    MathSciNet  Google Scholar 

  11. Kratsch, D., Rampon, J.-X.: Tree-visibility orders. Discrete Math. 190, 163–175 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  12. Kuntzmann, J., Verdillon, A.: Recherche d'un ordre minimal compatible avec un ordre partiel donné. Séminaire Institut de Math. Appl. de Grenoble (non publié) (1971)

  13. Mitas, J.: Tackling the jump number of interval orders. Order 8(2), 115–132 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  14. Mirkin, B.G.: Description of some relations on the set of real-line intervals. J. Math. Psych. 9, 243–252 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  15. Müller, H., Rampon, J.-X.: Partial orders and their convex subsets. Discrete Math. 165–166, 507–517 (1997)

    Article  Google Scholar 

  16. Müller, H., Rampon, J.-X.: Partial orders on weak orders convex subsets. Order 17(2), 103–123 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  17. Papadimitriou, C.H., Yannakakis, M.: Scheduling interval ordered tasks. SIAM J. Comput. 8, 405–409 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  18. Pulleyblank, W.R.: On minimizing setups in precedence constrained scheduling. Report 81105-OR, University of Bonn (1981)

  19. Schröder, B.S.W.: Ordered Sets. An Introduction. Birkhäuser, Boston, Inc., Massachusetts (2003)

    MATH  Google Scholar 

  20. Trotter, W.T.: Combinatorics and Partially Ordered Sets: Dimension Theory. The John Hopkins University Press, Baltimore, Maryland (1992)

    Google Scholar 

  21. Wiener, N.: A contribution to the theory of relative position. Proc. Camb. Philos. Soc. 17, 441–449 (1914)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. FST de l’Université de Nantes, 2, rue de la Houssinière, BP 92208, F-44322, Nantes Cedex 3, France

    Glen-Brug Guenver & Jean-Xavier Rampon

  2. Université d’Orléans, L.I.F.O., Bat IIIA, Rue Léonard de Vinci, B.P. 6759, F-45067, Orléans Cedex 2, France

    Jimmy Leblet

Authors
  1. Glen-Brug Guenver
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jimmy Leblet
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jean-Xavier Rampon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jean-Xavier Rampon.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Guenver, GB., Leblet, J. & Rampon, JX. Chain Dominated Orders. Order 23, 109–127 (2006). https://doi.org/10.1007/s11083-006-9035-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11083-006-9035-z

Key words

Search

Navigation