The number of symmetric chain decompositions

Tomon, István

doi:10.1090/proc/17142

The number of symmetric chain decompositions
HTML articles powered by AMS MathViewer

by István Tomon;

Proc. Amer. Math. Soc. 153 (2025), 1511-1518

DOI: https://doi.org/10.1090/proc/17142

Published electronically: February 18, 2025

HTML | PDF | Request permission

Abstract:

We prove that the number of symmetric chain decompositions of the Boolean lattice $2^{[n]}$ is \begin{equation*} \left (\frac {n}{2e}+o(n)\right )^{2^n}. \end{equation*} Furthermore, the number of symmetric chain decompositions of the hypergrid $[t]^n$ is \begin{equation*} n^{(1-o_n(1))\cdot t^n}. \end{equation*}

References

Ian Anderson, Combinatorics of finite sets, Dover Publications, Inc., Mineola, NY, 2002. Corrected reprint of the 1989 edition. MR 1902962
József Balogh, Andrew Treglown, and Adam Zsolt Wagner, Applications of graph containers in the Boolean lattice, Random Structures Algorithms 49 (2016), no. 4, 845–872. MR 3570990, DOI 10.1002/rsa.20666
L. M. Brégman, Some properties of nonnegative matrices and their permanents, Soviet Math. Dokl. 14 (1973), 945–949.
Karl Däubel, Sven Jäger, Torsten Mütze, and Manfred Scheucher, On orthogonal symmetric chain decompositions, Electron. J. Combin. 26 (2019), no. 3, Paper No. 3.64, 32. MR 4017317, DOI 10.37236/8531
N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde (2) 23 (1951), 191–193. MR 43115
G. P. Egorychev, Proof of the van der Waerden conjecture for permanents, Sibirsk. Mat. Zh. 22 (1981), no. 6, 65–71, 225 (Russian). MR 638007
V. Falgas-Ravry, E. Räty, and I. Tomon, Dedekind’s problem in the hypergrid, Preprint, arXiv:2310.12946, 2023.
D. I. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29 (1981), no. 6, 931–938, 957 (Russian). MR 625097
Curtis Greene and Daniel J. Kleitman, Strong versions of Sperner’s theorem, J. Combinatorial Theory Ser. A 20 (1976), no. 1, 80–88. MR 389608, DOI 10.1016/0097-3165(76)90079-0
Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille, Gray codes and symmetric chains, J. Combin. Theory Ser. B 153 (2022), 31–60. MR 4342529, DOI 10.1016/j.jctb.2021.10.008
Jerrold R. Griggs, Sufficient conditions for a symmetric chain order, SIAM J. Appl. Math. 32 (1977), no. 4, 807–809. MR 441751, DOI 10.1137/0132068
Jerrold Griggs, Charles E. Killian, and Carla D. Savage, Venn diagrams and symmetric chain decompositions in the Boolean lattice, Electron. J. Combin. 11 (2004), no. 1, Research Paper 2, 30. MR 2034416, DOI 10.37236/1755
L. H. Harper, The morphology of partially ordered sets, J. Combinatorial Theory Ser. A 17 (1974), 44–58. MR 366762, DOI 10.1016/0097-3165(74)90027-2
Gy. Katona, On a conjecture of Erdős and a stronger form of Sperner’s theorem, Studia Sci. Math. Hungar. 1 (1966), 59–63. MR 205864
Daniel J. Kleitman, On a lemma of Littlewood and Offord on the distribution of certain sums, Math. Z. 90 (1965), 251–259. MR 184865, DOI 10.1007/BF01158565
D. J. Kleitman, On an extremal property of antichains in partial orders, Combinatorics (eds. M. Hall and J. H. van Lint), Math. Centre Tracts 55 (1974), 77–90. Mathematics Centre, Amsterdam.
Alexander Schrijver, Counting $1$-factors in regular bipartite graphs, J. Combin. Theory Ser. B 72 (1998), no. 1, 122–135. MR 1604705, DOI 10.1006/jctb.1997.1798
James Shearer and Daniel J. Kleitman, Probabilities of independent choices being ordered, Stud. Appl. Math. 60 (1979), no. 3, 271–276. MR 532807, DOI 10.1002/sapm1979603271
Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), no. 1, 544–548 (German). MR 1544925, DOI 10.1007/BF01171114
Hunter Spink, Orthogonal symmetric chain decompositions of hypercubes, SIAM J. Discrete Math. 33 (2019), no. 2, 910–932. MR 3952674, DOI 10.1137/18M1187179
István Tomon, Decompositions of the Boolean lattice into rank-symmetric chains, Electron. J. Combin. 23 (2016), no. 2, Paper 2.53, 17. MR 3522137, DOI 10.37236/5328