Linear Extensions and Comparable Pairs in Partial Orders

被引：0
|
作者：
Colin McDiarmid
David Penman
Vasileios Iliopoulos
机构：
[1] University of Oxford,Department of Statistics
[2] University of Essex,Department of Mathematical Sciences
来源：
Order | 2018年 / 35卷
关键词：
Partial orders; Linear extensions; Comparable pairs; Concentration inequalities;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study the number of linear extensions of a partial order with a given proportion of comparable pairs of elements, and estimate the maximum and minimum possible numbers. We also consider a random interval partial order on n elements, which has close to a third of the pairs comparable with high probability: we show that the number of linear extensions is n! 2−Θ(n) with high probability.
引用
收藏
页码：403 / 420
页数：17
相关论文
共 50 条
  • [21] Random Partial Orders Defined by Angular Domains
    Paul Balister
    Balázs Patkós
    Order, 2011, 28 : 341 - 355
  • [22] Counting Linear Extensions: Parameterizations by Treewidth
    Eiben, E.
    Ganian, R.
    Kangas, K.
    Ordyniak, S.
    ALGORITHMICA, 2019, 81 (04) : 1657 - 1683
  • [23] Random Partial Orders Defined by Angular Domains
    Balister, Paul
    Patkos, Balazs
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2011, 28 (02): : 341 - 355
  • [24] External cofinalities and the antichain condition in partial orders
    Gorelic, I
    ANNALS OF PURE AND APPLIED LOGIC, 2006, 140 (1-3) : 104 - 109
  • [25] MAJORIZATION AND SCHUR CONVEXITY WITH RESPECT TO PARTIAL ORDERS
    HWANG, FK
    ROTHBLUM, UG
    MATHEMATICS OF OPERATIONS RESEARCH, 1993, 18 (04) : 928 - 944
  • [26] Using TPA to count linear extensions
    Banks, Jacqueline
    Garrabrant, Scott M.
    Huber, Mark L.
    Perizzolo, Anne
    JOURNAL OF DISCRETE ALGORITHMS, 2018, 51 : 1 - 11
  • [27] Counting Linear Extensions: Parameterizations by Treewidth
    E. Eiben
    R. Ganian
    K. Kangas
    S. Ordyniak
    Algorithmica, 2019, 81 : 1657 - 1683
  • [28] Combinatorial Markov chains on linear extensions
    Arvind Ayyer
    Steven Klee
    Anne Schilling
    Journal of Algebraic Combinatorics, 2014, 39 : 853 - 881
  • [29] Combinatorial Markov chains on linear extensions
    Ayyer, Arvind
    Klee, Steven
    Schilling, Anne
    JOURNAL OF ALGEBRAIC COMBINATORICS, 2014, 39 (04) : 853 - 881
  • [30] The k-track assignment problem on partial orders
    Barcia, P
    Cerdeira, JO
    JOURNAL OF SCHEDULING, 2005, 8 (02) : 135 - 143
12345