On linear extensions of ordered sets with a symmetry
type: Item
instance of: scholarly article
title: On linear extensions of ordered sets with a symmetry
zbMATH Open document ID: 0607.06001
DOI: 10.1016/0012-365X(87)90005-7
author: Bernhard Ganter
author: Gerhart Häfner
author: Werner Poguntke
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: A linear extension of a finite ordered set \((P,<)\) is an order-preserving bijection \(\lambda\) : \(P\to \{1,2,...,| P| \}\). For any pair x, y of distinct elements in P, \(p(x<y)\) denotes the fraction of linear extensions such that \(\lambda (x)<\lambda (y)\). The authors prove the following theorem: Let \((P,<)\) be a finite cycle-free ordered set, and let \(\alpha\) be a non-trivial automorphism of \((P,<)\). Then \(p(x<\alpha (x))=1/2\) for any \(x\in P\) with \(\alpha\) (x)\(\neq x\). The motivation for this comes from sorting problems.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 3981228
zbMATH Keywords: covering graph
zbMATH Keywords: finite ordered set
zbMATH Keywords: linear extensions
zbMATH Keywords: automorphism
zbMATH Keywords: sorting
reviewed by: Bohumil František Šmarda
MaRDI profile type: Publication
cites work: On the family of linear extensions of a partial order
cites work: On linear extension majority graphs of partial orders
cites work: Q3952141
cites work: Balancing poset extensions
cites work: The Information-Theoretic Bound is Good for Merging
cites work: A fixed point theorem for finite partially orderes sets
cites work: Q3686039
full work available at URL: 0012-365x(87)90005-7
OpenAlex ID: W2090600710
Recommended article: Q4891475
Recommended article: Q3344241
Recommended article: Linear extensions and order polynomials of finite partially ordered sets
Recommended article: On a class of partially ordered sets and their linear invariants
Recommended article: On extensions, linear extensions, upsets and downsets of ordered sets
Recommended article: Linear extensions and comparable pairs in partial orders
Recommended article: On extensions of constructive linear orders
Recommended article: On the Linearity of Order-isomorphisms
Recommended article: On linear extensions of finite posets
Recommended article: Russian Text Ignored
description: scientific article; zbMATH DE number 3981228