×

Linear extensions and comparable pairs in partial orders. (English) Zbl 1412.06003

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\)
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}\).
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)}\).

MSC:

06A07 Combinatorics of partially ordered sets
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Björner, A.; Wachs, ML, q-Hook length formulas for forests, J. Comb. Theory A, 52, 165-187, (1989) · Zbl 0697.06002 · doi:10.1016/0097-3165(89)90028-9
[2] Boucheron, S., Lugosi, G., Massart, P.: Concentration inequalities: A nonasymptotic theory of independence. Oxford University Press, Oxford (2013) · Zbl 1337.60003 · doi:10.1093/acprof:oso/9780199535255.001.0001
[3] Brightwell, GR, Random k-dimensional orders: Width and number of linear extensions, Order, 9, 333-342, (1992) · Zbl 0781.06003 · doi:10.1007/BF00420352
[4] Brightwell, G.R.: Models of random partial orders. In: Walker, K. (ed.) Surveys in Combinatorics, London Mathematical Society Lecture Note Series 187, pp. 53-84. Cambridge University Press (1993) · Zbl 0792.05127
[5] Brightwell, GR, Linear extensions of random orders, Discret. Math., 125, 87-96, (1994) · Zbl 0793.06001 · doi:10.1016/0012-365X(94)90147-3
[6] Brightwell, GR; Prömel, HJ; Steger, A., The average number of linear extensions of a partial order, J. Comb. Theory A, 73, 193-206, (1996) · Zbl 0842.05004 · doi:10.1016/S0097-3165(96)80001-X
[7] Brightwell, GR; Tetali, P., The number of linear extensions of the boolean lattice, Order, 20, 333-345, (2003) · Zbl 1061.06001 · doi:10.1023/B:ORDE.0000034596.50352.f7
[8] Cardinal, J.; Fiorini, S.; Joret, G.; Jungers, RM; Munro, JI, Sorting under partial information (without the ellipsoid algorithm), Combinatorica, 33, 655-697, (2013) · Zbl 1315.06002 · doi:10.1007/s00493-013-2821-5
[9] Chvátal, V., On certain polytopes associated with graphs, J. Comb. Theory B, 18, 138-154, (1975) · Zbl 0277.05139 · doi:10.1016/0095-8956(75)90041-6
[10] Csiszár, I.; Körner, J.; Lovász, L.; Marton, K.; Simonyi, G., Entropy splitting for antiblocking corners and perfect graphs, Combinatorica, 10, 27-40, (1990) · Zbl 0734.05061 · doi:10.1007/BF02122693
[11] Dilworth, RP, A decomposition theorem for partially ordered sets, Ann. Math., 51, 161-166, (1950) · Zbl 0038.02003 · doi:10.2307/1969503
[12] Edelman, P.; Hibi, T.; Stanley, RP, A recurrence for linear extensions, Order, 6, 15-18, (1989) · Zbl 0692.06001 · doi:10.1007/BF00341632
[13] Fishburn, PC, Interval graphs and interval orders, Discret. Math., 55, 135-149, (1985) · Zbl 0568.05047 · doi:10.1016/0012-365X(85)90042-1
[14] Fishburn, PC; Trotter, WT, Linear extensions of semiorders: A maximization problem, Discret. Math., 103, 25-40, (1992) · Zbl 0758.06002 · doi:10.1016/0012-365X(92)90036-F
[15] Fredman, M., How good is the information theory bound in sorting?, Theor. Comput. Sci., 1, 355-361, (1976) · Zbl 0327.68056 · doi:10.1016/0304-3975(76)90078-5
[16] Georgiou, N., The random binary growth model, Random Struct. Algor., 27, 520-552, (2005) · Zbl 1083.60009 · doi:10.1002/rsa.20083
[17] Justicz, J.; Scheinerman, E.; Winkler, P., Random intervals, Amer. Math. Monthly, 97, 881-889, (1990) · Zbl 0743.05048 · doi:10.1080/00029890.1990.11995679
[18] Kahn, J.; Kim, JH, Entropy and Sorting, J. Comput. Syst. Sci., 51, 390-399, (1995) · Zbl 1294.68069 · doi:10.1006/jcss.1995.1077
[19] Kleitman, DJ; Rothschild, BL, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205, 205-220, (1975) · Zbl 0302.05007 · doi:10.1090/S0002-9947-1975-0369090-9
[20] Knuth, D.E.: The art of computer programming, volume 3: sorting and searching, 2nd edn. Addison-Wesley, Boston (1998)
[21] McDiarmid, C.: On the method of bounded differences. In: Siemons, J. (ed.) Surveys in Combinatorics, London Mathematical Society Lecture Note Series 141, pp. 148-188. Cambridge University Press (1989) · Zbl 0712.05012
[22] Ramírez-Alfonsín, J.L., Reed, B.A.: Perfect Graphs. Wiley, New Jersey (2001) · Zbl 0972.00015
[23] Sha, J.; Kleitman, DJ, The number of linear extensions of subset ordering, Discret. Math., 63, 271-279, (1987) · Zbl 0647.05003 · doi:10.1016/0012-365X(87)90016-1
[24] Simonyi, G.: Perfect graphs and graph entropy. An updated survey. In: Ramírez-Alfonsín, J.L., Reed, B. A. (eds.) Perfect Graphs, pp. 293-328. Wiley (2001) · Zbl 0990.05054
[25] Stachowiak, G., A relation between the comparability graph and the number of linear extensions, Order, 6, 241-244, (1989) · Zbl 0696.06001 · doi:10.1007/BF00563525
[26] Stanley, RP, Two poset polytopes, Discrete Comput. Geom., 1, 9-23, (1986) · Zbl 0595.52008 · doi:10.1007/BF02187680
[27] Stanley, R.P.: Enumerative combinatorics, volume 1, 2nd edn. Cambridge University Press, Cambridge (2011) · doi:10.1017/CBO9781139058520
[28] Trotter, W.T.: Combinatorics and partially ordered sets: dimension theory. Johns Hopkins University Press, Baltimore (1992) · Zbl 0764.05001
[29] Trotter, WT; Wang, R., Planar posets, dimension, breadth and the number of minimal elements, Order, 33, 333-346, (2016) · Zbl 1359.06003 · doi:10.1007/s11083-015-9369-5
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.