Weak orders admitting a perpendicular linear order
type: Item
instance of: scholarly article
title: Weak orders admitting a perpendicular linear order
zbMATH Open document ID: 1115.06002
author: Maurice Pouzet
author: Imed Zaguia
published in: Discrete Mathematics
publication date: 2007-02-02T00:00:00Z
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''.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 5121352
zbMATH Keywords: Ordered set
zbMATH Keywords: Weak order
zbMATH Keywords: Autonomous set
zbMATH Keywords: Order-preserving map
zbMATH Keywords: Endomorphism
zbMATH Keywords: Maximal clone
zbMATH Keywords: Perpendicular orders
MaRDI profile type: Publication
full work available at URL: j.disc.2006.05.038
OpenAlex ID: W2048143630
cites work: Betweenness, orders and interval graphs
cites work: Q3691784
cites work: Relational systems with trivial endomorphisms and polymorphisms
cites work: The number of orthogonal permutations
cites work: Unary polynomials in algebras. I
cites work: Perpendicular orders
cites work: Prime two-dimensional orders and perpendicular total orders
DOI: 10.1016/J.DISC.2006.05.038
description: scientific article; zbMATH DE number 5121352