The symmetric group, ordered by refinement of cycles, is strongly Sperner

Harper, Lawrence; Kim, Gene

doi:10.1090/proc/15183

The symmetric group, ordered by refinement of cycles, is strongly Sperner
HTML articles powered by AMS MathViewer

by Lawrence H. Harper and Gene B. Kim PDF

Proc. Amer. Math. Soc. 149 (2021), 2753-2761 Request permission

Abstract:

Given a poset $(P,\leq )$, an antichain is a subset of pairwise incomparable elements of $P$. Let $(P,w)$ be a graded, weighted poset. If the maximum weight of an antichain of $P$ is equal to the weight of the largest rank of $P$, then $P$ is said to be Sperner. In 1967, Rota conjectured that the poset of partitions, ordered by refinement of blocks, is Sperner; this conjecture was later disproved by Canfield. In this paper, we consider a generalization of Rota’s conjecture and show that $S_n$, partially ordered by refinement of cycles, is strongly Sperner.

References

Drew Armstrong, Generalized noncrossing partitions and combinatorics of Coxeter groups, Mem. Amer. Math. Soc. 202 (2009), no. 949, x+159. MR 2561274, DOI 10.1090/S0065-9266-09-00565-1
E. Rodney Canfield, On a problem of Rota, Adv. in Math. 29 (1978), no. 1, 1–10. MR 480066, DOI 10.1016/0001-8708(78)90002-6
E. Rodney Canfield, The size of the largest antichain in the partition lattice, J. Combin. Theory Ser. A 83 (1998), no. 2, 188–201. MR 1636972, DOI 10.1006/jcta.1998.2871
E. R. Canfield and L. H. Harper, Large antichains in the partition lattice, Random Structures Algorithms 6 (1995), no. 1, 89–104. MR 1368837, DOI 10.1002/rsa.3240060109
Konrad Engel, Sperner theory, Encyclopedia of Mathematics and its Applications, vol. 65, Cambridge University Press, Cambridge, 1997. MR 1429390, DOI 10.1017/CBO9780511574719
P. Erdös, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. 51 (1945), 898–902. MR 14608, DOI 10.1090/S0002-9904-1945-08454-7
L. R. Ford Jr. and D. R. Fulkerson, Flows in networks, Princeton University Press, Princeton, N.J., 1962. MR 0159700
Christian Gaetz and Yibo Gao, A combinatorial $\mathfrak {sl}_2$-action and the Sperner property for the weak order, Proc. Amer. Math. Soc. 148 (2020), no. 1, 1–7. MR 4042823, DOI 10.1090/proc/14655
C. Gaetz and Y. Gao, On the Sperner property for the absolute order on complex reflection groups, preprint (2019) arXiv:1903.02033, 12 pp.
R. L. Graham and L. H. Harper, Some results on matching in bipartite graphs, SIAM J. Appl. Math. 17 (1969), 1017–1022. MR 266792, DOI 10.1137/0117090
L. H. Harper, Stirling behavior is asymptotically normal, Ann. Math. Statist. 38 (1967), 410–414. MR 211432, DOI 10.1214/aoms/1177698956
L. H. Harper, The global theory of flows in networks, Adv. in Appl. Math. 1 (1980), no. 2, 158–181. MR 603128, DOI 10.1016/0196-8858(80)90009-3
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
L. H. Harper, G. B. Kim, and N. Livesay, The absolute orders on the Coxeter groups $A_n$ and $B_n$ are Sperner, preprint (2019) arXiv:1902.08334, 6 pp.
Samuel Karlin, Total positivity. Vol. I, Stanford University Press, Stanford, Calif., 1968. MR 0230102
Robert A. Proctor, Representations of ${\mathfrak {s}}{\mathfrak {l}}(2,\,\textbf {C})$ on posets and the Sperner property, SIAM J. Algebraic Discrete Methods 3 (1982), no. 2, 275–280. MR 655567, DOI 10.1137/0603026
G. C. Rota, Research problem: A generalization of Sperner’s problem, J. Combinatorial Theory, 2 (1967), 104.
Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), no. 1, 544–548 (German). MR 1544925, DOI 10.1007/BF01171114
Richard P. Stanley, Weyl groups, the hard Lefschetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168–184. MR 578321, DOI 10.1137/0601021