Counting Linear Extensions of Posets with Determinants of Hook Lengths
Authors: 
Alexander Garver, Stefan Grosser, Jacob P. Matherne, Alejandro MoralesAuthors Info & Claims
Pages 205 - 233
Abstract
We introduce a class of posets, which includes both ribbon posets (skew shapes) and $d$-complete posets, such that their number of linear extensions is given by a determinant of a matrix whose entries are products of hook lengths. We also give $q$-analogues of this determinantal formula in terms of the major index and inversion statistics. As applications, we give families of tree posets whose numbers of linear extensions are given by generalizations of Euler numbers, we draw relations to Naruse and Okada's positive formulas for the number of linear extensions of skew $d$-complete posets, and we give polynomiality results analogous to those of descent polynomials by Diaz-López, Harris, Insko, Omar, and Sagan.
References
[1]
A. C. Aitken, The monomial expansion of determinantal symmetric functions, Proc. Roy. Soc. Edinburgh Sect. A, 61 (1943), pp. 300--310.
[2]
M. D. Atkinson, On computing the number of linear extensions of a tree, Order, 7 (1990), pp. 23--25.
[3]
A. Björner and M. L. Wachs, q-hook length formulas for forests, J. Combin. Theory Ser. A, 52 (1989), p. 165--187, https://doi.org/10.1016/0097-3165(89)90028-9.
[4]
A. Björner and M. L. Wachs, Permutation statistics and linear extensions of posets, J. Combin. Theory Ser. A, 58 (1991), pp. 85--114, https://doi.org/10.1016/0097-3165(91)90075-R.
[5]
G. Brightwell and P. Winkler, Counting linear extensions, Order, 8 (1991), pp. 225--242, https://doi.org/10.1007/BF00383444.
[6]
A. Diaz-Lopez, P. E. Harris, E. Insko, M. Omar, and B. E. Sagan, Descent polynomials, Discrete Math., 342 (2019), pp. 1674--1686.
[7]
S. Dittmer and I. Pak, Counting Linear Extensions of Restricted Posets, https://arxiv.org/abs/1802.06312, 2018.
[8]
T. Dwyer and S. Elizalde, Wilf equivalence relations for consecutive patterns, Adv. in Appl. Math., 99 (2018), pp. 134--157, https://doi.org/10.1016/j.aam.2018.04.007.
[9]
H. O. Foulkes, Enumeration of permutations with prescribed up-down and inversion sequences, Discrete Math., 15 (1976), pp. 235--252, https://doi.org/10.1016/0012-365X(76)90028-5.
[10]
J. S. Frame, G. de. B. Robinson, and R. M. Thrall, The hook graphs of the symmetric group, Canad. J. Math., 6 (1954), pp. 316--324.
[11]
A. Garver, K. Igusa, J. Matherne, and J. Ostroff, Combinatorics of exceptional sequences in type A, Electron. J. Combin., 26 (2019), pp. 1--20.
[12]
I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A, 64 (1993), pp. 189--215.
[13]
S. Grosser, Determinant Formulas for Counting Linear Extensions of Tree Posets, Undergraduate honors thesis, UMass, Amherst, 2018, https://people.math.umass.edu/~ahmorales/mentoring/thesis_Grosser.pdf.
[14]
P. Jiradilok and T. McConville, Roots of Descent Polynomials and an Algebraic Inequality on Hook Lengths, https://arxiv.org/abs/1910.14631, 2019.
[15]
J. S. Kim and M. Yoo, Hook length property of $d$-complete posets via $q$-integrals, J. Combin. Theory Ser. A, 162 (2019), pp. 167--221, https://doi.org/10.1016/j.jcta.2018.11.003.
[16]
D. E. Knuth, The Art of Computer Programming Volume 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1998.
[17]
P. A. MacMahon, Combinatory Analysis Volumes I, II Bound in One Volume, Dover Phoenix Editions, Dover, Mineola, NY, 2004.
[18]
R. H. Möhring, Computationally tractable classes of ordered sets, in Algorithms and Order, Springer, New York, 1989, pp. 105--193.
[19]
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), pp. 350--405, https://doi.org/10.1016/j.jcta.2017.09.002.
[20]
H. Naruse and S. Okada, Skew hook formula for $d$-complete posets via equivariant $k$-theory, Algebr. Combin., 2 (2019), pp. 541--571, https://doi.org/10.5802/alco.54.
[21]
G. Park, Naruse hook formula for linear extensions of mobile posets, in preparation.
[22]
R. A. Proctor, Dynkin diagram classification of $\lambda$-minuscule Bruhat lattices and of $d$-complete posets, J. Algebraic Combin., 9 (1999), pp. 61--94, https://doi.org/10.1023/A:1018615115006.
[23]
R. A. Proctor, Minuscule elements of Weyl groups, the numbers game, and $d$-complete posets, J. Algebra, 213 (1999), pp. 272--303, https://doi.org/10.1006/jabr.1998.7648.
[24]
R. A. Proctor, $d$-complete posets generalize Young diagrams for the hook product formula: Partial presentation of proof, RIMS Kôkyûroku, 1913 (2014), pp. 120--140.
[25]
R. A. Proctor and L. M. Scoppetta, $d$-complete posets: Local structural axioms, properties, and equivalent definitions, Order, 36 (2019), pp. 399--422, https://doi.org/10.1007/s11083-018-9473-4.
[26]
N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, https://oeis.org.
[27]
R. P. Stanley, Theory and application of plane partitions. Part 2, Stud. Appl. Math., 50 (1971), pp. 259--279.
[28]
R. P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combin. Theory Ser. A, 20 (1976), pp. 336--356, https://doi.org/10.1016/0097-3165(76)90028-5.
[29]
R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, Cambridge, UK, 1999.
[30]
R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, Cambridge, UK, 2012.
[31]
R. M. Thrall, A combinatorial problem, Michigan Math. J., 1 (1952), pp. 81--88, http://projecteuclid.org/euclid.mmj/1028989731.
Recommendations
An antipode formula for the natural Hopf algebra of a set operad
A symmetric set operad is a monoid in the category of combinatorial species with respect to the operation of substitution. From a symmetric set operad, we give here a simple construction of a commutative and non-co-commutative Hopf algebra, that we call ...
The sorting index and permutation codes
In the combinatorial study of the coefficients of a bivariate polynomial that generalizes both the length and the reflection length generating functions for finite Coxeter groups, Petersen introduced a new Mahonian statistic sor, called the sorting ...
Hook Formulas for Skew Shapes II. Combinatorial Proofs and Enumerative Applications
The Naruse hook-length formula is a recent general formula for the number of standard Young tableaux of skew shapes, given as a positive sum over excited diagrams of products of hook-lengths. In [A. H. Morales, I. Pak, and G. Panova, Hook Formulas for Skew ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
DOI:10.1137/sjdmec.35.1
Issue’s Table of Contents© 2021, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 01 January 2021
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in