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 条
  • [41] A Sequential Importance Sampling Algorithm for Counting Linear Extensions
    Jensen A.
    Beichl I.
    ACM Journal of Experimental Algorithmics, 2020, 25
  • [42] On the cross-product conjecture for the number of linear extensions
    Chan, Swee Hong
    Pak, Igor
    Panova, Greta
    CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2025, 77 (02): : 535 - 562
  • [43] The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
    Franz J. Brandenburg
    Andreas Gleißner
    Andreas Hofmeier
    Journal of Combinatorial Optimization, 2013, 26 : 310 - 332
  • [44] Depth Functions for Partial Orders with a Descriptive Analysis of Machine Learning Algorithms
    Blocher, Hannah
    Schollmeyer, Georg
    Jansen, Christoph
    Nalenz, Malte
    INTERNATIONAL SYMPOSIUM ON IMPRECISE PROBABILITY: THEORIES AND APPLICATIONS, VOL 215, 2023, 215 : 59 - 71
  • [45] Aggregating disjoint partial sub-orders - an internal logistics application
    Vacher, Blandine
    Jouglet, Antoine
    Nace, Dritan
    Bouznif, Marwane
    INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE-OPERATIONS & LOGISTICS, 2023, 10 (01)
  • [46] The nearest neighbor Spearman footrule distance for bucket, interval, and partial orders
    Brandenburg, Franz J.
    Gleissner, Andreas
    Hofmeier, Andreas
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2013, 26 (02) : 310 - 332
  • [47] Detecting Concurrency Vulnerabilities Based on Partial Orders of Memory and Thread Events
    Yu, Kunpeng
    Wang, Chenxu
    Cai, Yan
    Luo, Xiapu
    Yang, Zijiang
    PROCEEDINGS OF THE 29TH ACM JOINT MEETING ON EUROPEAN SOFTWARE ENGINEERING CONFERENCE AND SYMPOSIUM ON THE FOUNDATIONS OF SOFTWARE ENGINEERING (ESEC/FSE '21), 2021, : 280 - 291
  • [48] Partial orders on conjugacy classes in the Weyl group and on unipotent conjugacy classes
    Adams, Jeffrey
    He, Xuhua
    Nie, Sian
    ADVANCES IN MATHEMATICS, 2021, 383
  • [49] A LOOP-FREE ALGORITHM FOR GENERATING THE LINEAR EXTENSIONS OF A POSET
    CANFIELD, ER
    WILLIAMSON, SG
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1995, 12 (01): : 57 - 75
  • [50] NUMBER OF LINEAR EXTENSIONS FOR A VARIANT OF UP-DOWN POSET
    Ju, Hyeong-Kwan
    Shim, Kyu-Chul
    HONAM MATHEMATICAL JOURNAL, 2021, 43 (04): : 741 - 749
12345