Linear extensions and comparable pairs in partial orders
type: Item
instance of: scholarly article
title: Linear extensions and comparable pairs in partial orders
zbMATH Open document ID: 1412.06003
author: Vasileios Iliopoulos
author: Colin McDiarmid
author: David B. Penman
published in: Order
publication date: 2018-10-09T00:00:00Z
full work available at URL: https://arxiv.org/abs/1603.02901
review text: For a poset $Q$, let $Q_{\perp}$ be the comparability graph of $Q$ and let $e(Q)$ be the number of linear extensions of $Q$. It is known that if $Q_{\perp}\cong Q_{\perp}'$, then $e(Q)=e(Q')$. The paper focuses on the following question: given $\delta\in (0,1)$, what are the maximum and minimum values of $e(Q)$ for posets $Q$ whose comparability graph has $\delta Q_{\perp}$ can have $\binom{n}{2}$ edges, so $\delta$ \par To express the main result, the authors introduce the following notation. Given $n$ and $\delta\in (0,1)$, let \[ f^+(n,\delta) = \max_{|Q|=n}\left\{e(Q) \mid \text{comp}(Q)\geq \delta\binom{n}{2}\right\} \] and \[ f^-(n,\delta) = \min_{|Q|=n} \left\{e(Q) \mid \text{comp}(Q)\leq \delta\binom{n}{2}\right\}, \] where $\text{comp}(Q)$ denotes the number of edges in $Q_{\perp}$. \par The principal result says, roughly, that for each fixed $\delta\in(0,1)$ it is the case that $f^+(n,\delta)=n!2^{-\Theta(n)}$ and $f^-(n,\delta)=2^{\Theta(n)}$.
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 6949472
zbMATH Keywords: partial orders
zbMATH Keywords: linear extensions
zbMATH Keywords: comparable pairs
zbMATH Keywords: concentration inequalities
reviewed by: Keith A. Kearnes
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W3099342983
arXiv ID: 1603.02901
cites work: q-hook length formulas for forests
cites work: Concentration inequalities. A nonasymptotic theory of independence
cites work: Random \(k\)-dimensional orders: Width and number of linear extensions
cites work: Q3142411
cites work: Linear extensions of random orders
cites work: The average number of linear extensions of a partial order
cites work: The number of linear extensions of the Boolean lattice
cites work: Sorting under partial information (without the ellipsoid algorithm)
cites work: On certain polytopes associated with graphs
cites work: Entropy splitting for antiblocking corners and perfect graphs
cites work: A decomposition theorem for partially ordered sets
cites work: A recurrence for linear extensions
cites work: Interval graphs and interval orders
cites work: Linear extensions of semiorders: A maximization problem
cites work: How good is the information theory bound in sorting?
cites work: The random binary growth model
cites work: Random Intervals
cites work: Entropy and sorting.
cites work: Asymptotic Enumeration of Partial Orders on a Finite Set
cites work: Q4349924
cites work: Q3496342
cites work: Q4484907
cites work: The number of linear extensions of subset ordering
cites work: Perfect graphs and graph entropy: An updated survey
cites work: A relation between the comparability graph and the number of linear extensions
cites work: Two poset polytopes
cites work: Q4004146
cites work: Planar posets, dimension, breadth and the number of minimal elements
DOI: 10.1007/S11083-017-9439-Y
description: scientific article