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 条
  • [1] Linear Extensions and Comparable Pairs in Partial Orders
    McDiarmid, Colin
    Penman, David
    Iliopoulos, Vasileios
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 2018, 35 (03): : 403 - 420
  • [2] Counting Linear Extensions of Modular Partial Orders
    Dien, Matthieu
    Peschanski, Frederic
    2023 25TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND NUMERIC ALGORITHMS FOR SCIENTIFIC COMPUTING, SYNASC 2023, 2023, : 60 - 67
  • [3] Maximal extensions of partial orders preserving antimonotonicity
    Szigeti, Jeno
    ALGEBRA UNIVERSALIS, 2011, 66 (1-2) : 143 - 150
  • [4] FREQUENCY ESTIMATES FOR LINEAR EXTENSION MAJORITY CYCLES ON PARTIAL ORDERS
    GEHRLEIN, WV
    RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1991, 25 (04): : 359 - 364
  • [5] Comparable pairs in families of sets
    Alon, Noga
    Das, Shagnik
    Glebov, Roman
    Sudakov, Benny
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 115 : 164 - 185
  • [6] Antichains and Linear Extensions
    Peter C. Fishburn
    Order, 1998, 15 : 129 - 142
  • [7] Antichains and linear extensions
    Fishburn, PC
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1998, 15 (02): : 129 - 142
  • [8] DECOMPOSITION OF PARTIAL ORDERS
    WAGNER, D
    ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1990, 6 (04): : 335 - 350
  • [9] MINING POSETS FROM LINEAR ORDERS
    Fernandez, Proceso L.
    Heath, Lenwood S.
    Ramakrishnan, Naren
    Tan, Michael
    Vergara, John Paul C.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2013, 5 (04)
  • [10] Partial orders on representations of algebras
    Forbregd, Tore A.
    Nornes, Nils M.
    Smalo, Sverre O.
    JOURNAL OF ALGEBRA, 2010, 323 (07) : 2058 - 2062
12345