×

Sorting probability for large Young diagrams. (English) Zbl 1482.05338

Summary: For a finite poset \(P=(X,\prec)\), let \(\mathcal{L}_P\) denote the set of linear extensions of \(P\). The sorting probability \(\delta(P)\) is defined as \[ \delta(P) \, := \, \min_{x,y\in X} \, \big|P \, [L(x)\leq L(y)] -P \, [L(y)\leq L(x)] \big|\,, \] where \(L \in \mathcal{L}_P\) is a uniform linear extension of \(P\). We give asymptotic upper bounds on sorting probabilities for posets associated with large Young diagrams and large skew Young diagrams, with bounded number of rows.

MSC:

05E10 Combinatorial aspects of representation theory
05A16 Asymptotic enumeration
06A07 Combinatorics of partially ordered sets
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Conjecture 1.1, we do not resolve the conjecture in any new cases. As mentioned in the introduction, for all skew Young diagrams the conjecture was already established in [OS18]. In fact, when compared with the Kahn-Saks Conjecture 1.6, our results are counterintuitive since we obtain the conclusion of the conjecture in a strong form, while the width of our posets remains bounded. Clearly, much of the subject remains misunderstood and open to further exploration.
[2] When λ = (m d ) is a rectangle, one can estimate δ (P λ ) without the NHLF, since f (λ /µ) can be computed by the hook-length formula (2.7). This greatly simplifies the calculations, and is an approach
[3] M. Aigner, A note on merging, Order 2 (1985), 257-264. · Zbl 0582.06003
[4] Y. Baryshnikov and D. Romik, Enumeration formulas for Young tableaux in a diagonal strip, Israel J. Math. 178 (2010), 157-186. 5 · Zbl 1206.05011
[5] G. R. Brightwell, Semiorders and the 1 3 -2 3 conjecture, Order 5 (1989), 369-380. 4, 6 · Zbl 0681.06001
[6] G. R. Brightwell, Models of random partial orders, in Surveys in combinatorics, Cambridge Univ. Press, Cambridge, UK, 1993, 53-83. 5 · Zbl 0792.05127
[7] G. R. Brightwell, Balanced pairs in partial orders, Discrete Math. 201 (1999), 25-52. 4 · Zbl 0940.06002
[8] G. R. Brightwell, S. Felsner and W. T. Trotter, Balancing pairs and the cross product conjecture, Order 12 (1995), 327-349. 2, 4, 6 · Zbl 0839.06002
[9] G. R. Brightwell and P. Winkler, Counting linear extensions, Order 8 (1991), 225-242. 5 DISCRETE ANALYSIS, 2021:24, 57pp. · Zbl 0759.06001 · doi:10.19086/da
[10] G. R. Brightwell and C. Wright, The 1 3 -2 3 conjecture for 5-thin posets, SIAM J. Discrete Math. 5 (1992), 467-474. · Zbl 0777.06001
[11] J. Cardinal, S. Fiorini, G. Joret, R. M. Jungers and J. I. Munro, Sorting under partial information (without the ellipsoid algorithm), Combinatorica 33 (2013), 655-697. 4 · Zbl 1315.06002
[12] [CPP21] S. H. Chan, I. Pak and G. Panova, Sorting probability of Catalan posets, Advances Applied Math. 129 (2021), Paper No. 102221, 13 pp. 6, 50, 53 · Zbl 1478.60020
[13] E. Chen, A family of partially ordered sets with small balance constant, Electron. J. Combin. 25 (2018), Paper 4.43, 13 pp. 4 · Zbl 1507.06002
[14] H. Cohn, R. Kenyon and J. Propp, A variational principle for domino tilings, Jour. AMS 14 (2001), 297-346. 5 · Zbl 1037.82016
[15] [DP18] S. Dittmer and I. Pak, Counting linear extensions of restricted posets, preprint (2018), 33 pp.; arXiv:1802.06312. 5
[16] W. Feit, The degree formula for the skew-representations of the symmetric group, Proc. AMS 4 (1953), 740-744. · Zbl 0052.02302
[17] J. S. Frame, G. de B. Robinson and R. M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954), 316-324. 9 · Zbl 0055.25404
[18] M. L. Fredman, How good is the information theory bound in sorting?, Theoret. Comput. Sci. 1 (1975), 355-361. 4 · Zbl 0327.68056
[19] C. Gaetz and Y. Gao, Balance constants for Coxeter groups, preprint (2020), 27 pp.; arXiv:2005.09719. 53
[20] B. Ganter, G. Häfner and W. Poguntke, On linear extensions of ordered sets with a symmetry, Discrete Math. 63 (1987), 153-156. 4 · Zbl 0607.06001
[21] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Stat. Assoc. 58 (1963), 13-30. 11 · Zbl 0127.10602
[22] J. Janson, Poset limits and exchangeable random posets, Combinatorica 31 (2011), 529-563. · Zbl 1265.06002
[23] [KL91] J. Kahn and N. Linial, Balancing extensions via Brunn-Minkowski, Combinatorica 11 (1991), 363-368. 4, 6 · Zbl 0735.06004
[24] J. Kahn and J. H. Kim, Entropy and sorting, J. Comput. Syst. Sci. 51 (1995), 390-399. 4 · Zbl 1294.68069
[25] J. Kahn and M. Saks, Balancing poset extensions, Order 1 (1984), 113-126. 4, 5, 6 · Zbl 0561.06004
[26] S. S. Kislitsyn, A finite partially ordered set and its corresponding set of permutations, Math. Notes 4 (1968), 798-801. 4 · Zbl 0229.05016
[27] D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. AMS 205 (1975), 205-220. 5 · Zbl 0302.05007
[28] J. Komlós, A strange pigeonhole principle, Order 7 (1990), 107-113. 5, 6 · Zbl 0743.05070
[29] M. Konvalinka, A bijective proof of the hook-length formula for skew shapes, Europ. J. Combin. 88 (2020), 103104, 14 pp. 5 · Zbl 1442.05022
[30] A. D. Korshunov, On linear extensions of partially ordered sets (in Russian), Trudy Inst. Mat. (Novosibirsk) 27 (1994), 34-42, 179. 5 · Zbl 0859.06007
[31] N. Linial, The information-theoretic bound is good for merging, SIAM J. Comput. 13 (1984), 795-801. 4, 6, 7 · Zbl 0548.68065
[32] I. G. Macdonald, Schur functions: theme and variations, in Sém. Lothar. Combin., Strasbourg, 1992, 5-39. 5, 9 · Zbl 0889.05073
[33] I. G. Macdonald, Symmetric functions and Hall polynomials (Second ed.), Oxford U. Press, New York, 1995, 475 pp. 8 · Zbl 0824.05059
[34] A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes I. q-analogues and bijections, J. Combin. Theory, Ser. A 154 (2018), 350-405. 4, 5, 9, 10, 52 · Zbl 1373.05026
[35] A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes II. Combinatorial proofs and enumerative applications, SIAM J. Discrete Math. 31 (2017), 1953-1989. 5, 9 · Zbl 1370.05007
[36] A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes III. Multivariate and product formulas, Algebraic Combin. 2 (2019), 815-861. 5 · Zbl 1425.05158
[37] A. H. Morales, I. Pak and G. Panova, Asymptotics of the number of standard Young tableaux of skew shape, European J. Combin. 70 (2018), 26-49. 4, 5, 10 · Zbl 1384.05175
[38] A. H. Morales, I. Pak and M. Tassy, Asymptotics for the number of standard tableaux of skew shape and for weighted lozenge tilings, Combinatorics, Probability and Computing, to appear, 25 pp.; arXiv:1805.00992. 5, 7
[39] A. H. Morales and D. G. Zhu, On the Okounkov-Olshanski formula for standard tableaux of skew shapes, preprint (2020), 37 pp.; arXiv:2007.05006. 52
[40] A. Okounkov and G. Olshanski, Shifted Schur functions, St. Petersburg Math. J. 9 (1998), 239-300. 5, 52 · Zbl 0894.05053
[41] E. J. Olson and B. E. Sagan, On the 1 3 -2 3 conjecture, Order 35 (2018), 581-596. 5, 6, 11, 52 · Zbl 1528.06007
[42] I. Pak, Skew shape asymptotics, a case-based introduction, Sém. Lothar. Combin. 84, Art. B84a (2021), 26 ipp. 5 · Zbl 1491.05194
[43] J. Pitman, Combinatorial stochastic processes, Springer, Berlin, 2006, 256 pp. 6 DISCRETE ANALYSIS, 2021:24, 57pp. · Zbl 1103.60004 · doi:10.19086/da
[44] B. Pittel and D. Romik, Limit shapes for random square Young tableaux, Adv. Appl. Math. 38 (2007), 164-209. 5, 6 · Zbl 1122.60009
[45] B. E. Sagan, The symmetric group (Second ed.), Springer, New York, 2001, 238 pp. 8, 9 · Zbl 0964.05070
[46] A. Sah, Improving the 1 3 -2 3 conjecture for width two posets, Combinatorica 41 (2021), 99-126. 2, 4 · Zbl 1474.06006
[47] M. Saks, Balancing linear extensions of ordered sets, Order 2 (1985), 327-330. 5, 6
[48] R. P. Stanley, Enumerative Combinatorics, vol. 1 (second ed.) and vol. 2, Cambridge Univ. Press, 2012 and 1999. 5, 8, 9, 51, 52 · Zbl 0928.05001
[49] R. P. Stanley, On the enumeration of skew Young tableaux, Adv. Appl. Math. 30 (2003), 283-294. 5 · Zbl 1027.05109
[50] W. Sun, Dimer model, bead and standard Young tableaux: finite cases and limit shapes, preprint (2018), 67 pp.; arXiv:1804.03414. 6, 7
[51] W. T. Trotter, Partially ordered sets, in Handbook of combinatorics, Vol. 1, Elsevier, Amster-dam, 1995, 433-480. 8 · Zbl 0841.06001
[52] W. T. Trotter, W. G. Gehrlein and P. C. Fishburn, Balance theorems for height-2 posets, Order 9 (1992), 43-53. 4 · Zbl 0769.06004
[53] A. M. Vershik and S. V. Kerov, The asymptotic character theory of the symmetric group, Funct. Anal. Appl. 15 (1981), 246-255. 5 · Zbl 0507.20006
[54] I. Zaguia, The 1 3 -2 3 conjecture for N-free ordered sets, Electron. J. Combin. 19 (2012), no. 2, Paper 29, 5 pp. 4, 6 · Zbl 1288.06005
[55] I. Zaguia, The 1 3 -2 3 conjecture for ordered sets whose cover graph is a forest, Order 36 (2019), · Zbl 1443.06004
[56] Swee Hong Chan University of California Los Angeles Los Angeles, USA sweehong [at] math [dot] ucla [dot] edu https://www.math.ucla
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.