Weak orders admitting a perpendicular linear order

DOI10.1016/J.DISC.2006.05.038MaRDI QIDQ861798zbMATH OpenOpenAlexFDO

Authors Maurice Pouzet, Imed Zaguia

Publication date 2 February 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.05.038

zbMATH Keywords

Autonomous setEndomorphismMaximal cloneOrder-preserving mapOrdered setPerpendicular ordersWeak order

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07)

Review text

The authors characterize the finite weak orders admitting a perpendicular linear order and give two basic results. First, every linear order having at least four elements has a perpendicular linear order and, second, if \(q(n)\) denotes the number of linear orders perpendicular to the natural order on \([1, \ldots, n]\), then \(\lim_{n \rightarrow \infty} \frac{q(n)}{n!} = e^{-2} = 0,1353\ldots\). The main result of this paper, Theorem 3, gives necessary and sufficient conditions for a weak order \(P\) to admit a perpendicular linear order \(L\). Essentially Theorem 3 says that such a linear order exists if and only if the levels of \(P\) are not ``too big.

Recommendations

• Perpendicular orders
• Prime two-dimensional orders and perpendicular total orders
• Orthogonal countable linear orders
• Countable linear orders with disjoint infinite intervals are mutually orthogonal
• The order on the rationals has an orthogonal order with the same order type

Cites work

• Betweenness, orders and interval graphs
• scientific article; zbMATH DE number 3914376 (Why is no real title available?)
• Perpendicular orders
• Prime two-dimensional orders and perpendicular total orders
• Relational systems with trivial endomorphisms and polymorphisms
• The number of orthogonal permutations
• Unary polynomials in algebras. I
• Weak orders admitting a perpendicular linear order

Cited in

(8)

• Prime two-dimensional orders and perpendicular total orders
• Perpendicular orders
• Orthogonal countable linear orders
• Geometric representations of weak orders
• The number of weak orders. A comment
• The order on the rationals has an orthogonal order with the same order type
• Weak orders admitting a perpendicular linear order
• Order extensions and the fixed point property

This page was built for publication: Weak orders admitting a perpendicular linear order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q861798)