Poset entropy versus number of linear extensions: the width-2 case.

DOI10.1007/S11083-015-9346-ZMaRDI QIDQ5965137zbMATH OpenOpenAlexFDO

Authors Samuel Fiorini, Selim Rexhep

Publication date 2 March 2016

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.5024

zbMATH Keywords

algorithmsentropyfinite partially ordered setsincomparability graphslinear extensionssortingsorting under partial information

Mathematics Subject Classification ID

Applications of graph theory (05C90) Combinatorics of partially ordered sets (06A07) Searching and sorting (68P10) Nonnumerical algorithms (68W05) Measures of information, entropy (94A17)

Abstract: Kahn and Kim (J. Comput. Sci., 1995) have shown that for a finite poset $P$, the entropy of the incomparability graph of $P$ (normalized by multiplying by the order of $P$) and the base-$2$ logarithm of the number of linear extensions of $P$ are within constant factors from each other. The tight constant for the upper bound was recently shown to be $2$ by Cardinal, Fiorini, Joret, Jungers and Munro (STOC 2010, Combinatorica). Here, we refine this last result in case $P$ has width $2$: we show that the constant can be replaced by $2-varepsilon$ if one also takes into account the number of connected components of size $2$ in the incomparability graph of $P$. Our result leads to a better upper bound for the number of comparisons in algorithms for the problem of sorting under partial information.

Recommendations

• Entropy and sorting.
• Balancing poset extensions
• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets

Cites work

• An efficient algorithm for partial order production
• Computing the number of mergings with constraints
• Entropy and sorting.
• Entropy splitting for antiblocking corners and perfect graphs
• Graphs that Split Entropies
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 780788 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• On certain polytopes associated with graphs

Cited in

(5)

• Improving the \(\frac{1}{3}\)-\(\frac{2}{3}\) conjecture for width two posets
• scientific article; zbMATH DE number 6315775 (Why is no real title available?)
• scientific article; zbMATH DE number 6400769 (Why is no real title available?)
• Extensions of the Kahn-Saks inequality for posets of width two
• Entropy and sorting.

This page was built for publication: Poset entropy versus number of linear extensions: the width-2 case.

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