A tanglegram is an ordered pair of binary trees with the same set of leaves. (Our binary trees are rooted and unordered, and have labeled leaves and unlabeled internal vertices, so the number of binary trees in which the leaves are labeled \(1\), \(2\), \(\dots\), \(n\) is \(1\cdot3\cdots(2n-3)\) for \(n>1\).) Billey, Konvalinka, and Matsen, motivated by biological interest, studied the number of unlabeled tanglegrams with \(n\) leaves (orbits of tanglegrams under the action of the symmetric group \(\mathfrak{S}_n\)). It follows from Burnside’s lemma that this number is \[\begin{equation} \sum_{\lambda\vdash n} \frac{r_\lambda^2}{z_\lambda}, \end{equation}\] where \(r_\lambda\) is the number of binary trees fixed by a permutation of cycle type \(\lambda\). There is a similar interpretation for \(\sum_{\lambda\vdash n}{r_\lambda^k}/{z_\lambda}\). (Here \(n!/z_\lambda\) is the number of permutations in the symmetric group \(\mathfrak{S}_n\) of cycle type \(\lambda\).)
Billey, Konvalinka, and Matsen found a surprisingly simple explicit formula for \(r_\lambda\): If \(\lambda\) is a binary partition (a partition in which every part is a power of 2) then \[\begin{equation} \label{e-rprod} r_\lambda=\prod_{i=2}^{l(\lambda)}\bigl(2(\lambda_i+\cdots + \lambda_{l(\lambda)}) -1\bigr), \end{equation}\] where \(l(\lambda)\) is the number of parts of \(\lambda\), and if \(\lambda\) is not a binary partition then \(r_\lambda=0\).
Amdeberhan and Konvalinka independently conjectured that if we appropriately replace 2 by an arbitrary prime in these formulas then \(\sum_{\lambda\vdash n}{r_\lambda^k}/{z_\lambda}\) is still an integer.
The key to proving the Amdeberhan-Konvalinka conjecture is the fact that the symmetric functions \(\sum_{\lambda\vdash n}{r_\lambda} p_\lambda/{z_\lambda}\) (with generalized \(r_\lambda\)), where \(p_\lambda\) is the power sum symmetric function, have integer coefficients. This is because these symmetric functions are plethystic inverses of integral symmetric functions closely related to the Lyndon symmetric functions. These symmetric functions are quite interesting, and several questions about them remain open, most notably whether they have a combinatorial interpretation and whether they are Schur-positive.
Lorentzian polynomials are multivariate polynomials with remarkable positivity properties. They appear in diverse areas such as combinatorics, representation theory, algebraic geometry, computer science and convex geometry, and are useful to establish various positivity properties.
We will give an introduction to Lorentzian polynomials and highlight the connections with combinatorics and matroid theory. We will also show how these polynomials may be used to prove Mason’s strong conjecture and to give a new proof of the Heron-Rota-Welsh conjecture in matroid theory.
The talk is based on joint work with June Huh and Jonathan Leake.
The monopole-dimer model is a signed variant of the monomer-dimer model which has determinantal structure. We extend the monopole-dimer model for planar graphs introduced by Prof. Arvind Ayyer to Cartesian products thereof and show that the partition function of this model can be expressed as a determinant of a generalised signed adjacency matrix. We then give an explicit product formula for three-dimensional grid graphs a la Kasteleyn and Temperley–Fischer, in which case the partition function turns out to be fourth power of a polynomial when all grid lengths are even. Finally, we generalise this product formula to \(d\) dimensions, again obtaining an explicit product formula.
To a symplectic Kashiwara-Nakashima (KN) tableau, a variation of a De Concini tableau, used in standard monomial theory to write standard bases, one may attach a \(\mathfrak{sl}_2\) crystal graph, called cocrystal, whose edges are defined via the local Lecouvey-Sheats symplectic jeu de taquin operators on consecutive columns. These cocrystals contain all the needed information to compute the right and left keys of a symplectic KN tableau. Similarly to type A Willis method, Santos has also given a Willis like way of computing right and left keys without the use of the symplectic jeu de taquin. Alternatively, we may utilize the Baker virtualization embedding of \(C_n\) into \(A_{2n-1}\) to embed a type \(C_n\) Demazure crystal, its opposite and atoms into \(A_{2n-1}\) ones. The right, respectively left key of a KN tableau are then computed as \(A_{2n-1}\) keys in the virtual Demazure crystal and sent back via reverse Schensted insertion to the \(C_n\) crystal as the desired right, respectively left symplectic key. As an application of our explicit symplectic right and left key maps, thanks to the isomorphism between Lakshmibai-Seshadri path crystals, by Littelmann, and Kashiwara crystals, we may use, similarly to the \(\mathfrak{gl}_n\) case, symplectic left and right key maps as a tool to test the “standardness” of a symplectic KN tableau, in the sense of standard monomial theory, on a Schubert or Richardson variety in \(\mathrm{Sp}(2n; C)/B\) where \(B\) is a Borel subroup of the symplectic group \(\mathrm{Sp}(2n; C)\). This is s joint work with J. M. Santos.
The central objects in this talk are the descent polynomials of colored permutations on multisets, referred to as colored multiset Eulerian polynomials. These polynomials generalize the colored Eulerian polynomials that appear frequently in algebraic combinatorics and are known to admit desirable distributional properties, including real-rootedness, log-concavity, unimodality and the alternatingly increasing property. In joint work with Liam Solus and Bin Han, symmetric colored multiset Eulerian polynomials are identified and used to prove sufficient conditions for a colored multiset Eulerian polynomial to be interlaced by its own reciprocal. This property implies that the polynomial obtains all of the aforementioned distributional properties as well as others, including bi-\(\gamma\)-positivity. To derive these results, multivariate generalizations of a generating function identity due to MacMahon are deduced.
Alternating sign triangles have been introduced by Ayyer, Behrend and Fischer in 2016 and it was proven that there is the same number of alternating sign triangles with n rows as there is of n×n alternating sign matrices. Later on Fischer gave a refined enumeration of alternating sign triangles with respect to a statistic ρ, having the same distribution as the unique 1 in the top row of an alternating sign matrix, by connecting alternating sign triangles to (0,n,n)- Magog trapezoids. We introduce two more statistics counting the all 0-columns on the left and right in an alternating sign triangle yielding objects we call alternating sign pentagons. We then show the equinumeracy of these alternating sign pentagons with Magog pentagons of a certain shape taking into account the statistic ρ. Furthermore we deduce a generating function of these alternating sign pentagons with respect to the statistic ρ in terms of a Pfaffian and consider the implications of our new results on some open conjectures.
We present a combinatorial proof of the Graham-Pollak formula for the determinant of the distance matrix of a tree, via sign-reversing involutions and the Lindström-Gessel-Viennot lemma. Our approach provides a cohesive and unified framework for the understanding of the existing generalizations and q-analogues of the Graham-Pollak formula, and facilitates the derivation of a natural simultaneous generalizations for them.
Combining a variant of the Farkas lemma with the Flow Decomposition Theorem we show that the regions of any deformation of a graphical arrangement may be bijectively labeled with a set of weighted digraphs containing directed cycles of negative weight only. Bounded regions correspond to strongly connected digraphs. The study of the resulting labelings allows us to add the omitted details in Stanley’s proof on the injectivity of the Stanley-Pak labeling of the regions of the extended Shi arrangement and to introduce a new labeling of the regions in the \(a\)-Catalan arrangement. We also point out that Athanasiadis-Linusson labelings may be used to directly count regions in a class of arrangements properly containing the extended Shi arrangement and the Fuss-Catalan arrangement.
We study the symmetric function that conjecturally gives the Frobenius characteristic of a diagonal coinvariant ring with one set of commuting and two sets of anti-commuting variables, of which we provide a combinatorial interpretation in terms of segmented Smirnov words. Furthermore, this function is related to the Delta conjectures, and this work is a step towards a unified formulation of the two versions, as we prove a unified Delta theorem at t=0.
For a naturally labelled poset \(P\) on \(n\) elements let \(L(P)\) be the set of linear extensions of \(P\) considered as permutations. Define \(h_P(x) = \sum_{\pi \in L(P)} x^{\mathit{des}(\pi)}\). Neggers and Stanley conjectured that \(h_P(x)\) is real rooted. This was shown to be false by Branden and Stembridge. The unimodality consequence of the Neggers-Stanley conjecture holds for graded posets by work of Reiner and Welker. In this talk we use their approach to show that for non-graded posets the coefficient sequence of \(h_P(x)\) is the h-vector of a triangulated ball of dimension \(n − |P|\). In particular, the unimodality consequence follows if this triangulation satisfies the generalized g-theorem. In addition, we present a jeu-de-jaquin type bijection between the maximal simplices of the triangulation and \(L(P)\) based on ideas by Dennis White.
We determine the maximum number of edges of a graph without containing the 2-power of a Hamilton cycle. This extends a well-known theorem of Ore in 1961 concerning the maximum number of edges of a graph without containing a Hamilton cycle. (https://doi.org/10.1016/j.disc.2022.112908)
The rook monoid \(R_n\) is a natural generalization of the symmetric group \(S_n\). As such, it is not surprising that elegant combinatorics arise in the realm of its representation theory. In 2002, for a field \(\mathbb{F}\) of characteristic zero, L. Solomon established an important Schur-Weyl duality between the general linear group \(GL_d(F)\) and the rook monoid on tensor spaces. Recently, we have defined a finite-dimensional algebra \(\mathcal{S}_{\mathbb{F}}(d, \mathbf{n})\) whose module category is equivalent to the category of homogeneous polynomial \(GL_d(F)\)-modules of degree at most n, where \(\mathbb{F}\) is an infinite field of any characteristic. This algebra, which we have christened the extended Schur algebra, is an extension of classical Schur algebras as defined in 1980 by J. A Green in a seminal monograph. Our work led us to a new Schur-Weyl duality between \(\mathcal{S}_{\mathbb{F}}(d, \mathbf{n})\) and \(R_n\) on tensor spaces which is closely related to Solomon’s result. In this talk, we give a combinatorial construction of a complete set of simple modules for \(\mathbb{F}R_n\), where \(\mathbb{F}\) is an infinite field. It is our purpose to explain how the methods outlined in Chaper 6 of Green’s monograph can be used to obtain analogues of the dual Specht modules for \(S_n\) from the Carter-Lusztig modules of \(\mathcal{S}_{\mathbb{F}}(d, \mathbf{n})\) realised on tensors. Our second aim is to show how our approach relates to tableaux of shape \(\lambda_r^n\) which occur in C. Grood’s construction of Specht modules analogues for the rook monoid.
A permutation statistic \(\operatorname{stat}\) is called shuffle compatible if, for any two permutations \(\pi\) and \(\sigma\) on disjoint sets of symbols, its distribution over all shuffles of \(\pi\) and \(\sigma\) depends only on \(\operatorname{stat}(\pi)\), \(\operatorname{stat}(\sigma)\) and the lengths of \(\pi\) and \(\sigma\). It follows from Stanley’s work on \(P\)-partitions that the descent set constitutes the prototypical example of a shuffle-compatible permutation statistic. Gessel and Zhuang formalized this notion by introducing and studying the associated shuffle algebra. In this talk, we are going to discuss a colored analogue of shuffle compatibility for colored permutation statistics and its connection with Poirier’s colored quasisymmetric functions and Hsiao–Petersen’s colored \(P\)-partitions. Additionally, we are going to present an application of colored shuffle compatibility in computing Hadamard products of ask zeta functions. This is based on joint work with Angela Carnevale and Tobias Rossmann.
For a (finite) simplicial complex \(\Delta\) of dimension \(d-1\) the \(h\)-vector \(h^\Delta = (h_0^\Delta,\ldots, h_d^\Delta)\) is an encoding of the face numbers of the simplicial complex. Athanasiadis and Tzanaki study the inequalities \[\begin{align} \frac{h_0^\Delta}{h_d^\Delta} \leq & \frac{h_1^\Delta}{h_{d-1}^\Delta} \leq \cdots \leq \frac{h_{d-1}^\Delta}{h_1^\Delta} \overset{\text{(*)}}{\leq} \frac{h_0^\Delta}{h_d^\Delta}. \end{align}\] under the assumption all terms are defined, respectively all terms except the last one \(\frac{h_0}{h_d}\) are defined. The inequalities have strong implications on symmetric decompositions of \(h\)-polynomials. In this talk, we study when a subdivision of a simplicial complex preserves the inequalities.
We characterize the commutative nilpotent subsemigroups of maximum order in the full transformation semigroup \(T_n\), using a mixture of algebraic and combinatorial techniques. Although non-commutative nilpotent subsemigroups of \(T_n\) can be much larger, the maximum-order commutative nilpotent subsemigroups turn out to be precisely the maximum-order null subsemigroups of \(T_n\) previously characterized by Cameron et al. [1]. [1] Peter J. Cameron, James East, Des FitzGerald, James D. Mitchell, Luke Pebody and Thomas Quinn-Gregson. Minimum degrees of finite rectangular bands, null semigroups, and variants of full transformation semigroups. Combinatorial Theory, 3(3), 2023.
Crystal graphs are powerful combinatorial tools for working with the plactic monoid and symmetric functions. Quasi-crystal graphs are an analogous concept for the hypoplactic monoid and quasi-symmetric functions. We explicitly describe a previously observed isomorphism of components of the quasi-crystal graph, introducing a new combinatorial structure called quasi-array. As an application, we explore the interaction of fundamental quasi-symmetric functions and Schur functions, and the arrangement of quasi-crystal components within crystal components. This is joint work with Alan Cain, António Malheiro and Fátima Rodrigues.
For any simple character of a finite group, we will define a projective variety by projecting the Segre embedding. Such varieties are described by parametric equations involving the immanant (of the corresponding simple character) of a matrix of parameters. For one-dimensional characters, the geometry of these varieties suggests the definition of a combinatorial structure, which we call \(\chi\)-matroid. A matroid is obtained by considering the alternating character of a symmetric group. We will enounce some conjectures and problems concerning the combinatorics and the geometry of immanant varieties.
The vector partition function is the counting function enumerating solutions x with non-negative integer co-ordinates to the matrix equation Ax = b. It is well known that vector partition functions are piecewise quasi-polynomials whose domains of quasi-polynomiality are chambers of the chamber complex of A. We present a result which allows one to compute the quasi-polynomials for certain chambers by computing a vector partition function for some A’ whose dimensions are smaller than A. In the simplest case (i.e for certain chambers that we call external chambers), we are able to reduce things to the classical coin exchange problem. Using this reduction, we show that in certain cases, the quasi-polynomial is given by a negative binomial coefficient. We then illustrate how the vector partition function approach is effective in studying other combinatorial objects (Littlewood-Richardson coefficients, Kronecker coefficients, and multigraphs). In particular, we present symmetry and stability results for the Littlewood-Richardson coefficients, bounds on the Kronecker coefficients, and an enumeration result for multigraphs with certain degree sequences.
We obtain a cancellation-free formula, represented in terms of Schröder trees, for the antipode in the double tensor Hopf algebra introduced by Ebrahimi-Fard and Patras. We apply the antipode formula in the context of non-commutative probability and recover cumulant-moment formulas as well as a new expression for Anshelevich’s free Wick polynomials in terms of Schröder trees.