Proceedings FPSAC 2016

Below are all papers as they will appear in the FPSAC 2016 proceedings. Papers are sorted in lexicographic order of their first author.

Show all abstracts Hide all abstracts Montrer tous les résumés Cacher tous les résumés

Fully packed loop configurations: polynomiality and nested arches
by Florian Aigner
This extended abstract proves that the number of fully packed loop configurations whose link pattern consists of two noncrossing matchings separated by \(m\) nested arches is a polynomial in \(m\). This was conjectured by Zuber (2004) and for large values of \(m\) proved by Caselli et al. (2004).
Dans cet article nous prouvons que le nombre de configurations de boucles compactes dont le motif de liaison consiste en deux couplages non-croisés séparés par \(m\) arcs emboîtés est un polynôme en \(m\). Ce résultat avait été conjecturé par Zuber (2004) et prouvé pour les grandes valeurs de \(m\) par Caselli et al. (2004).
Normal Supercharacter Theory
by Farid Aliniaeifard
There are three main constructions of supercharacter theories for a group \(G\). The first, defined by Diaconis and Isaacs, comes from the action of a group \(A\) via automorphisms on our given group \(G\). Another general way to construct a supercharacter theory for \(G\), defined by Diaconis and Isaacs, uses the action of a group \(A\) of automorphisms of the cyclotomic field \(Q{[{\zeta}_{|G|}]}\). The third, defined by Hendrickson, is combining a supercharacter theories of a normal subgroup \(N\) of \(G\) with a supercharacter theory of \(G/N\). In this paper we construct a supercharacter theory from an arbitrary set of normal subgroups of \(G\). We show that when we consider the set of all normal subgroups of \(G\), the corresponding supercharacter theory is related to a partition of \(G\) given by certain values on the central primitive idempotents. Also, we show the supercharacter theories that we construct can not be obtained via automorphisms or a single normal subgroup.
Il y a trois constructions principales de théories des supercaractères pour un groupe \(G\). La première, définie par Diaconis et Isaacs, provient de l'action d'un groupe \(A\) par automorphismes sur un groupe donné \(G\). Une autre méthode générale pour construire la théorie des supercaractères de \(G\), définie par Diaconis et Isaacs, utilise l'action d'un groupe \(A\) d'automorphismes du corps cyclotomique \(Q{[{\zeta}_{|G|}]}\). La troisième, définie par Hendrickson, combine une théorie de supercaractères d'un sous-groupe distingué \(N\) de \(G\) avec une théorie des supercaractères de \(G/N\). Dans cet article, nous construisons une théorie des supercaractères à partir d'un ensemble arbitraire de sous-groupes distingués de \(G\). Nous montrons que lorsqu'on considère l'ensemble de tous les sous-groupes distingués de \(G\), la théorie des supercarcatères correspondante est liée à une partition de \(G\) donnée par certaines valeurs des idempotents centraux primitifs. Nous montrons aussi que les théories des supercaractères que nous construisons ne peuvent pas être obtenues par automorphismes ou par un unique sous-groupe distingué.
Dual Immaculate Quasisymmetric Functions Expand Positively into Young Quasisymmetric Schur Functions
by Edward Allen, Joshua Hallam and Sarah Mason
We describe a combinatorial formula for the coefficients when the dual immaculate quasisymmetric functions are decomposed into Young quasisymmetric Schur functions. We prove this using an analogue of Schensted insertion. We also provide a Remmel-Whitney style rule to generate these coefficients algorithmically.
Nous décrivons une formule combinatoire pour les coefficients des dual immaculate quasisymmetric functions quand ils sont décomposées en Young quasisymmetric Schur functions. Nous le prouvons en utilisant un analogue d'insertion de Schensted. Nous fournissons également une règle de style Remmel-Whitney pour générer ces coefficients algorithmiquement.
Non-representable hyperbolic matroids
by Nima Amini and Petter Brändén
The generalized Lax conjecture asserts that each hyperbolicity cone is a linear slice of the cone of positive semidefinite matrices. Hyperbolic polynomials give rise to a class of (hyperbolic) matroids which properly contains the class of matroids representable over the complex numbers. This connection was used by the first author to construct counterexamples to algebraic (stronger) versions of the generalized Lax conjecture by considering a non-representable hyperbolic matroid. The Vamos matroid and a generalization of it are to this day the only known instances of non-representable hyperbolic matroids. We prove that the Non-Pappus and Non-Desargues matroids are non-representable hyperbolic matroids by exploiting a connection, due to Jordan, between Euclidean Jordan algebras and projective geometries. We further identify a large class of hyperbolic matroids that are parametrized by uniform hypergraphs and prove that many of them are non-representable. Finally we explore consequences to algebraic versions of the generalized Lax conjecture.
La conjecture généralisée de Lax affirme que chaque cône hyperbolique est une partie linéaire du cône des matrices définies positives. Les polynômes hyperboliques engendrent une classe de matroïdes qui contient l'ensemble des matroïdes qui pensent être représenter sur les nombres complexes. Cette observation a été utilisé par le premier auteur pour construire un contre-exemple à des versions algébriques de la conjecture généralisée de Lax qui dépend d'un matroïde hyperbolique que l'on ne peut pas représenter sur les nombres complexes. Le matroïde de Vamos et une généralisation sont les seuls exemples de matroïdes que l'on connait aujourd'hui et qui ne peuvent pas être représenter sur les nombres complexes. On montre que les Non-Pappus et Non-Desarques matroïdes ne peuvent pas être représenté non plus en utilisant un lien, attribué à Jordan, entre l'Algébre de Jordan Euclidienne et la géométrie projective. On identifie aussi une classe de matroïdes hyperboliques qui sont paramétrées par des hypergraphes dont la plupart ne sont pas représentables. Finalement, on exploite des conséquences des versions algébriques de la conjecture de Lax généralisée.
The generalized Gelfand-Graev characters of \(\mathrm{GL}_n(\mathbb{F}_q)\) (extended abstract)
by Scott Andrews
Introduced by Kawanaka in order to find the unipotent representations of finite groups of Lie type, generalized Gelfand-Graev characters have remained somewhat mysterious. Even in the case of the finite general linear groups, the combinatorics of their decompositions has not been worked out. This paper re-interprets Kawanaka's definition in type $A$ in a way that gives far more flexibility in computations. We use these alternate constructions to show how to obtain generalized Gelfand-Graev representations directly from the maximal unipotent subgroups. We also explicitly decompose the corresponding generalized Gelfand-Graev characters in terms of unipotent representations, thereby recovering the Kostka-Foulkes polynomials as multiplicities.
Introduits par Kawanaka pour trouver des représentations unipotentes de groupes finis de type Lie, les caractères généralisés de Gelfand-Graev sont restés en quelque sorte mystérieux. Même dans le cas des groupes généraux linéaires finis, la combinatoire de leurs décompositions n'a pas été étudiée. Cet article réinterprète la définition de Kawanaka en type \(A\) d'une façon qui offre bien plus de flexibilité pour les calculs. Nous utilisons ces constructions alternatives pour montrer comment obtenir les représentations de Gelfand-Graev directement depuis les sous-groupes unipotents maximaux. Nous décomposons aussi explicitement les caractères généralisés de Gelfand-Graev correspondants en termes de représentations unipotentes, et retrouvons ainsi comme multiplicités les polyn{ô}mes de Kostka-Foulkes.
The configuration space of a robotic arm in a tunnel of width 2
by Federico Ardila, Hanner Bastidas, Cesar Ceballos and John Guo
We study the motion of a robotic arm inside a rectangular tunnel of width \(2\). We prove that the configuration space \(\mathcal{S}\) of all possible positions of the robot is a \(\mathrm{CAT}(0)\) cubical complex. Before this work, very few families of robots were known to have \(\mathrm{CAT}(0)\) configuration spaces. ; this is the next example that was currently out of reach. This property allows us to move the arm optimally from one position to another. Ardila, Owen, and Sullivant gave a bijection between \(\mathrm{CAT}(0)\) cubical complexes and posets with inconsistent pairs (PIPs), and we describe the coral PIP which corresponds to \(\mathcal{S}\) under this bijection. We also compute the \(f\)-vector of \(\mathcal{S}\) and use it to verify that the Euler characteristic of \(\mathcal{S}\) equals \(1\).
Nous étudions le mouvement d'un bras robotisé à l'intérieur d'un tunnel de largeur \(2\). Nous démontrons que l'espace des configurations \(\mathcal{S}\) consistant de toutes les positions du robot est un complexe cubique CAT(0). Très peu de familles de robots satisfont cette propriété; cette famille, précédemment hors d'atteinte, était la prochaine à être étudiée. Cette propriété nous permet the bouger le bras de façon optimale d'un position à l'autre. Ardila, Owen et Sullivant ont donné une biection entre les complexes cubiques \(\mathrm{CAT}(0)\) et les ensembles partiellement ordonnés avec pair inconsistantes (PIPs) et nous décrivons les PIP coral qui correspond à \(\mathcal{S}\) sous cette bijection. Nous calculons aussi le \(f\)-vecteur de \(\mathcal{S}\) et l'utilisons pour vérifier que la caractéristique d'Euler de \(\mathcal{S}\) est égale à \(1\).
The topology of the external activity complex of a matroid
by Federico Ardila, Federico Castillo and Jose Samper
We prove that the external activity complex \(\textrm{Act}_<(M)\) of a matroid is shellable. In fact, we show that every linear extension of Las Vergnas's external/internal order \(<_{ext/int}\) on \(M\) provides a shelling of \(\textrm{Act}_<(M)\). We also show that every linear extension of Las Vergnas's internal order \(<_{int}\) on \(M\) provides a shelling of the independence complex \(IN(M)\). As a corollary, \(\textrm{Act}_<(M)\) and \(M\) have the same \(h\)-vector. We prove that, after removing its cone points, the external activity complex is contractible if \(M\) contains \(U_{3,1}\) as a minor, and a sphere otherwise.
Nous prouvons que le complexe d'activité externe \(\textrm{Act}_<(M)\) d'un matroïde est épluchable. En fait, nous montrons que toute extension linéaire de l'ordre externe/interne de Las Vergnas \(<_{ext/int}\) sur \(M\) fournit un épluchage de \(\textrm{Act}_<(M)\). Nous montrons aussi que toute extension linéaire de l'ordre interne de Las Vergnas \(<_{int}\) sur \(M\) fournit un épluchage du complexe d'indépendance \(IN(M)\). En conséquence, \(\textrm{Act}_<(M)\) et \(M\) ont le même \(h\)-vecteur. Nous prouvons que, après suppression des points cones, le complexe d'activité externe est contractible si \(M\) contient \(U_{3,1}\) comme mineur, et est une sphère sinon.
Non-ambiguous trees: new results and generalization
by Jean-Christophe Aval, Adrien Boussicault, Bérénice Delcroix-Oger, Florent Hivert and Patxi Laborde Zubieta
We present a new definition of non-ambiguous trees (NATs) as labelled binary trees. We thus get a differential equation whose solution can be described combinatorially. This yield a new formula for the number of NATs. We also obtain \(q\)-versions of our formula. And we generalize NATs to higher dimension.
Nous introduisons une nouvelle définition des arbres non ambigus (NATs) en terme d'arbres binaires étiquetés. Nous en déduisons une équation différentielle, dont les solutions peuvent être décrites de manière combinatoire. Ceci conduit à une nouvelle formule pour le nombre de NATs. Nous démontrons aussi des \(q\)-versions des formules obtenues. Enfin, nous généralisons la notion de NAT en dimension supérieure.
Continued Classification of 3D Lattice Models in the Positive Octant
by Axel Bacher, Manuel Kauers and Rika Yatchak
We continue the investigations of lattice walks in the three-dimensional lattice restricted to the positive octant. We separate models which clearly have a D-finite generating function from models for which there is no reason to expect that their generating function is D-finite, and we isolate a small set of models whose nature remains unclear and requires further investigation. For these, we give some experimental results about their asymptotic behaviour, based on the inspection of a large number of initial terms. At least for some of them, the guessed asymptotic form seems to tip the balance towards non-D-finiteness.
Nous poursuivons l'étude des chemins dans le réseau à trois dimensions restreints à l'octant positif. Nous séparons les modèles ayant clairement une série génératrice D-finie de ceux pour laquelle il n'y a pas de raison de s'attendre à une série D-finie et nous isolons un petit ensemble de modèles dont la nature reste indéterminée. Pour ceux-là, nous donnons des résultats expérimentaux sur leur comportement asymptotique basés sur l'inspection d'un grand nombre de termes initiaux. Au moins pour certains d'entre eux, la forme asymptotique devinée semble faire pencher la balance vers la non-D-finitude.
Fourientation activities and the Tutte polynomial: Extended abstract
by Spencer Backman, Samuel Hopkins and Lorenzo Traldi
A fourientation of a graph \(G\) is a choice for each edge of the graph whether to orient that edge in either direction, leave it unoriented, or biorient it. We may naturally view fourientations as a mixture of subgraphs and graph orientations where unoriented and bioriented edges play the role of absent and present subgraph edges, respectively. Building on work of Backman and Hopkins (2015), we show that given a linear order and a reference orientation of the edge set, one can define activities for fourientations of \(G\) which allow for a new \(12\) variable expansion of the Tutte polynomial \(T_G\). Our formula specializes to both an orientation activities expansion of \(T_G\) due to Las Vergnas (1984) and a generalized activities expansion of \(T_G\) due to Gordon and Traldi (1990).
Une fourientation d'un graphe \(G\) est un choix, pour chaque arête du graphe, d'orienter l'arête, ou laisser l'arête pas orienté, ou biorienter l'arête. Les fourientations sont un mélange d'orientations et de sous-graphes. Suivant Backman et Hopkins (2015), nous démontrons que, étant donné un ordre linéaire sur l'ensemble des arêtes et une orientation de référence, on peut définir des activités pour tous les fourientations de \(G\) qui donnent une nouvelle formule de \(12\) variables pour le Tutte polynôme \(T_G\). Cette formule se spécialise à la formule de l'activité d'orientation de Las Vergnas (1984) et à la formule de l'activité généralisée de Gordon et Traldi (1990).
Asymptotics of polygons in restricted geometries subject to a force
by Nicholas Beaton, Christine Soteros and Jeremy Eng
We consider self-avoiding polygons in a restricted geometry, namely an infinite \(L\times M\) tube in \(\mathbb Z^3\). These polygons are subjected to a force \(f\), parallel to the infinite axis of the tube. When \(f>0\) the force stretches the polygons, while when \(f<0\) the force is compressive. In this extended abstract we obtain and prove the asymptotic form of the free energy in the limit \(f\to-\infty\). We conjecture that the \(f\to-\infty\) asymptote is the same as the free energy of Hamiltonian polygons, which visit every vertex in a \(L\times M\times N\) box.
Nous considérons des polygones auto-évitants dans une géométrie restreinte, en particulier un tube infini dans \(\mathbb Z^3\) avec les dimensions \(L\times M\). Ces polygones sont soumis à une force \(f\), parallèle à l'axe infini du tube. Quand \(f>0\) la force tend les polygones, alors que quand \(f<0\) la force est compressive. Dans ce résumé détaillé, nous obtenons et prouvons la forme asymptotique de l'énergie libre en la limite \(f\to-\infty\). Nous conjecturons que l'asymptote \(f\to-\infty\) est la même que l'énergie libre des polygones hamiltoniennes, qui visitent chaque sommet dans un boîte \(L\times M\times N\).
Diagonally and antidiagonally symmetric alternating sign matrices of odd order
by Roger Behrend, Ilse Fischer and Matjaz Konvalinka
We study the enumeration of diagonally and antidiagonally symmetric alternating sign matrices (DAS\-ASMs) of fixed odd order by introducing a case of the six-vertex model whose configurations are in bijection with such matrices. The model involves a grid graph on a triangle, with bulk and boundary weights which satisfy the Yang-Baxter and reflection equations. We obtain a general expression for the partition function of this model as a sum of two determinantal terms, and show that at a certain point each of these terms reduces to a Schur function. We are then able to prove a conjecture of Robbins from the mid 1980's that the total number of \((2n+1)\times(2n+1)\) DASASMs is \(\prod_{i=0}^n\frac{(3i)!}{(n+i)!}\), and a conjecture of Stroganov from 2008 that the ratio between the numbers of \((2n+1)\times(2n+1)\) DASASMs with central entry \(-1\) and \(1\) is \(n/(n+1)\). Among the several product formulae for the enumeration of symmetric alternating sign matrices which were conjectured in the 1980's, that for odd-order DASASMs is the last to have been proved.
Nous étudions l'énumération de matrices à signes alternants symétriques diagonalement et antidiagonalement (abrégé DASASM) d'ordre impair fixé, en introduisant un cas du modèle à six sommets dont les configurations sont en bijection avec de telles matrices. Le modèle comporte un graphe sur un réseau triangulaire, dont les poids satisfont les équations Yang-Baxter et de réflexion. Nous obtenons une expression générale pour la fonction de partition de ce modèle comme une somme de deux termes déterminantaux, et nous montrons qu' à un certain point chacun de ces termes se réduit à une fonction de Schur. Nous sommes alors en mesure de prouver une conjecture de Robbins du milieu des années 1980 prévoyant que le nombre total de DASASMs d'ordre \((2n+1)\times(2n+1)\) est \(\prod_{i=0}^n\frac{(3i)!}{(n+i)!}\), et une conjecture de Stroganov de 2008 prévoyant que le rapport entre le nombre de \((2n+1)\times(2n+1)\) DASASMs avec coefficient central \(-1\) et \(1\) est \(n/(n+1)\). Parmi les nombreuses formules de produit pour l'énumération des matrices à signe alternant symétriques qui ont été conjecturées dans les années 1980, celle-ci est la derniére à être prouvée.
DHD-puzzles
by Sabine Beil
In this work triangular puzzles that are composed of unit triangles with labelled edges are considered. To be more precise, the labelled unit triangles that we allow are on the one hand the puzzle pieces that compute Schubert calculus and on the other hand the flipped K-theory puzzle piece. The motivation for studying such puzzles comes from the fact that they correspond to a class of oriented triangular fully packed loop configurations. The main result that is presented is an expression for the number of these puzzles with a fixed boundary in terms of Littlewood-Richardson coefficients.
Dans ce travail nous considérons des puzzles triangulaires composés de triangles unitaires avec côtés étiquetés. Plus précisément, les triangles que nous autorisons sont, d'une part ceux correspondant au calcul de Schubert, et d'autre part les retournements des pièces de puzzle de la K-théorie. La motivation pour étudier des tels puzzles provient du fait qu'ils correspondent à une classe de configurations de boucles compactes triangulaires (TFPL) orientées. Le résultat principal présenté est une expression du nombre de ces puzzles ayant une frontière fixée en fonction des coefficients de Littlewood-Richardson.
Schur polynomials and matrix positivity preservers
by Alexander Belton, Dominique Guillot, Apoorva Khare and Mihai Putinar
A classical result by Schoenberg (1942) identifies all real-valued functions that preserve positive semidefiniteness (psd) when applied entrywise to matrices of arbitrary dimension. Schoenberg's work has continued to attract significant interest, including renewed recent attention due to applications in high-dimensional statistics. However, despite a great deal of effort in the area, an effective characterization of entrywise functions preserving positivity in a fixed dimension remains elusive to date. As a first step, we characterize new classes of polynomials preserving positivity in fixed dimension. The proof of our main result is representation theoretic, and employs Schur polynomials. An alternate, variational approach also leads to several interesting consequences including (a) a hitherto unexplored Schubert cell-type stratification of the cone of psd matrices, (b) new connections between generalized Rayleigh quotients of Hadamard powers and Schur polynomials, and (c) a description of the joint kernels of Hadamard powers.
Un résultat classique de Schoenberg (1942) fournit une caractérisation des fonctions réelles préservant la positivité lorsque appliquées aux entrées des matrices semidéfinie positives de dimension arbitraire. Le travail de Schoenberg est toujours d'actualité, et a récemment reçu beaucoup d'attention suite à ses applications aux statistiques de haute dimension. Néanmoins, l'obtention d'une caractérisation utile des fonctions préservant la positivité lorsque la dimension est fixe demeure un problème ouvert. Afin d'attaquer ce problème, nous caractérisons de nouvelles classes de polynômes qui préservent la positivité en dimension finie. La preuve de notre résultat principal implique plusieurs idées provenant de la théorie de la représentation, et utilise les polynômes de Schur. Nous explorons aussi une approche variationnelle parallèle qui mène à de nombreux résultats intéressants: (a) une stratification du cône des matrices semidéfinies positives, (b) de nouvelles connexions entre les quotients de Rayleigh généralisés des puissances d'Hadamard et les polynômes de Schur, et (c) une description du noyau simultané des puissances d'Hadamard.
McKay Centralizer Algebras
by Thomas Halverson and Georgia Benkart
For a finite subgroup \(\mathsf{G}\) of the special unitary group \(\mathbf{SU}_2\), we study the centralizer algebra \(\mathsf{Z}_k(\mathsf{G}) = \mathsf{End}_\mathsf{G}(\mathsf{V}^{\otimes k})\) of \(\mathsf{G}\) acting on the \(k\)-fold tensor product of its defining representation \(\mathsf{V} = \mathbb C^2\). The McKay correspondence relates the representation theory of these groups to an associated affine Dynkin diagram, and we use this connection to study the structure and representation theory of \(\mathsf{Z}_k(\mathsf{G})\) via the combinatorics of the Dynkin diagram. When \(\mathsf{G}\) equals the binary tetrahedral, octahedral, or icosahedral group, we exhibit remarkable connections between \(\mathsf{Z}_k(\mathsf{G})\) and the Martin-Jones set partition algebras.
Pour un sous-groupe fini \(\mathsf {G} \) du groupe unitaire spéciale \(\mathsf {SU}_2 \), nous étudions la centralisateur algébre \(\mathsf{Z} _k(\mathsf{G}) = \mathsf{End}_\mathsf{G}(\mathsf{V}^{\otimes k})\) de \(\mathsf{G}\) agissant sur le produit \(k\)-fold de tenseur de sa représentation définissant \(\mathsf{V} = \mathbb{C}^ 2\). La correspondance de McKay concerne la théorie des représentations de ces groupes à une associé Dynkin diagramme, et nous utiliser cette connexion pour étudier la structure et la théorie des représentations de \(\mathsf{Z}_k(\mathsf{G})\) par l'intermédiaire de la combinatoire du diagramme de Dynkin. Quand \(\mathsf{G} \) est égale à la groupe tétraédrique binaire, octaédre binaire, ou icosaédrique binaire, nous exhibons connexions remarquables entre \(\mathsf{Z}_k(\mathsf{G})\) et les algébres de partitions de Martin-Jones.
A Hopf algebra of subword complexes (Extended abstract)
by Nantel Bergeron and Cesar Ceballos
We introduce a Hopf algebra structure of subword complexes, including both finite and infinite types. We present an explicit cancellation free formula for the antipode using acyclic orientations of certain graphs, and show that this Hopf algebra induces a natural non-trivial sub-Hopf algebra on \(c\)-clusters in the theory of cluster algebras.
Nous introduisons une structure d'algèbre de Hopf sur les complexes de sous-mots de types fini et infini. Nous présentons une formule explicite sans cancelation pour l'antipode qui utilise les orientations acycliques. Nous donnons une sous-algèbre de Hopf naturel non-trivial sur les \(C\)-clusters dans la théorie des algèbres amassées.
A type B analog of the Lie representation
by Andrew Berget
We describe a type \textrm{B} analog of the much studied Lie representation of the symmetric group. The \(n\)th Lie representation of \(S_n\) restricts to the regular representation of \(S_{n-1}\), and our generalization mimics this property. Specifically, we construct a representation of the type \textrm{B} Weyl group \(B_n\) that restricts to the regular representation of \(B_{n-1}\). We view both of these representations as coming from the internal zonotopal algebra of the Gale dual of the corresponding reflection arrangements.
Nous décrivons un type \textrm{B} analogue de la bien connue représentation Lie du group symmetrique. Le représentation Lie est un représentation de \(S_n\) qui restreint à la représentation régulière de \(S_{n-1}\), et notre géneralisation imite cette propriété. Plus précisément, nous construisons une représentation de group Weyl \(B_n\) qui restreint à la représentation régulière de \(B_{n-1}\). Ces deux représentations sont des occurrences de l'algèbre interne zonotopal de dual Gale des arrangements de réflexion respectifs.
Counting quadrant walks via Tutte's invariant method
by Olivier Bernardi, Mireille Bousquet-Mélou and Kilian Raschel
In the 1970s, Tutte developed a clever algebraic approach, based on certain « invariants », to solve a functional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past decade to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps. We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic (with one small exception). This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity comes out (almost) automatically. Then, we move to an analytic viewpoint which has already proved very powerful, leading in particular to integral expressions of the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop in this context a weaker notion of invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions of the generating function, and a proof that this series is differentially algebraic (that is, satisfies a non-linear differential equation). This analytic approach solves as well the algebraic model left unsolved in the first part.
Nous adaptons à l'énumération des chemins confinés dans le premier quadrant une méthode développée par Tutte dans les années 70 pour compter les triangulations proprement colorées. Nous prouvons ou reprouvons d'abord ainsi l'algébricité de tous les chemins du quadrant dont la série génératrice est (ou est conjecturée) algébrique ; ceci inclut le célèbre modèle de Gessel. Pour être applicable, la méthode requiert l'existence de deux fonctions rationnelles appelées invariant et fonction de découplage. Nous passons ensuite à un cadre analytique qui a déjà fourni des expressions intégrales des séries génératrices dans des cas non D-finis, et des preuves de non-D-finitude. Dans ce contexte, nous définissons une notion plus faible d'invariants. Tous les modèles du quadrant admettent alors un invariant, et, pour ceux qui ont de plus une fonction de découplage, nous obtenons une expression sans intégrale de la série génératrice, et prouvons que cette série est différentiellement algébrique (solution d'une équation différentielle polynomiale).
The Mixing Time for a Random Walk on the Symmetric Group Generated by Random Involutions
by Megan Bernstein
The involution walk is a random walk on the symmetric group generated by involutions with a number of \(2\)-cycles sampled from the binomial distribution with parameter \(p\). This is a parallelization of the lazy transposition walk on the symmetric group. The involution walk is shown in this paper to mix for \(\frac{1}{2} \leq p \leq 1\) fixed, \(n\) sufficiently large in between \(\log_{1/p}(n)\) steps and \(\log_{2/(1+p)}(n)\) steps. The paper introduces a new technique for finding eigenvalues of random walks on the symmetric group generated by many conjugacy classes using the character polynomial for the characters of the representations of the symmetric group. This is especially efficient at calculating the large eigenvalues. The smaller eigenvalues are handled by developing monotonicity relations that also give after sufficient time the likelihood order, the order from most likely to least likely state. The walk was introduced to study a conjecture about a random walk on the unitary group from the information theory of back holes.
La marche d'involution est une marche aléatoire sur le groupe symétrique générée par les involutions avec un nombre de \(2\)-cycles tiré aléatoirement en suivant une distribution binomiale de paramètre \(p\). Il s'agit d'une parallèlisation de la marche de transposition paresseuse sur le groupe symétrique. Nous montrons dans cet article que la marche d'involution mélange pour \(\frac{1}{2} \leq p \leq 1\) fixé, et \(n\) suffisamment grand entre \(\log_{1/p}(n)\) et \(\log_{2/(1+p)}(n)\) étapes. Cet article introduit une nouvelle technique pour trouver les valeurs propres de marches aléatoires sur le groupe symétrique générées par de nombreuses classes de conjugaison en utilisant les caractères des représentations du groupe symétrique. Cette méthode est particulièrement efficace pour calculer les grandes valeurs propres. Les petites valeurs propres sont traitées en développant des relations de monotonicité qui donnent aussi après suffisamment de temps l'ordre de probabilité, c'est-à-dire l'ordre de l'état le plus probable à l'état le moins probable. La marche est introduite pour étudier une conjecture concernant une marche aléatoire sur le groupe unitaire provenant de la théorie de l'information sur les trous noirs.
A bijection for nonorientable general maps
by Jeremie Bettinelli
We give a different presentation of a recent bijection due to Chapuy and Dolega for nonorientable bipartite quadrangulations and we extend it to the case of nonorientable general maps. This can be seen as a Bouttier-Di Francesco-Guitter-like generalization of the Cori-Vauquelin-Schaeffer bijection in the context of general nonorientable surfaces. In the particular case of triangulations, the encoding objects take a particularly simple form and we recover a famous asymptotic enumeration formula found by Gao.
On donne une présentation différente d'une bijection récente due à Chapuy et Dolega pour les quadrangulations biparties non-orientables et on l'étend au cas des cartes générales non-orientables. Cela peut se voir comme une généralisation à la Bouttier-Di Francesco-Guitter de la bijection de Cori-Vauquelin-Schaeffer dans le contexte des surfaces non-orientables générales. Dans le cas particulier des triangulations, les objets codant prennent une forme particulièrement simple et on retrouve la fameuse formule d'énumération asymptotique de Gao.
Minimal factorizations of a cycle: a multivariate generating function
by Philippe Biane and Matthieu Josuat-Vergès
It is known that the number of minimal factorizations of the long cycle in the symmetric group into a product of \(k\) cycles of given lengths has a very simple formula: it is \(n^{k-1}\) where \(n\) is the rank of the underlying symmetric group and \(k\) is the number of factors. In particular, this is \(n^{n-2}\) for transposition factorizations. The goal of this work is to prove a multivariate generalization of this result. As a byproduct, we get a multivariate analog of Postnikov's hook length formula for trees, and a refined enumeration of final chains of noncrossing partitions.
On sait que le nombre de factorisations minimales du long cycle dans le groupe symétrique en un produit de \(k\) cycles de longueurs données a une formule très simple: c'est \(n^{k-1}\) où \(n\) est le rang du groupe symétrique. En particulier, c'est \(n^{n-2}\) pour les factorisations en transpositions. Le but de ce travail est de prouver une généralisation multivariée de ce résultat. En conséquence, on obtient un analogue multivarié de la formule des équerres de Postnikov sur les arbres, et une énumération raffinée de chaînes finales de partitions non-croisées.
A bijective proof of Macdonald's reduced word formula
by Sara Billey, Alexander Holroyd and Benjamin Young
We describe a bijective proof of Macdonald's reduced word identity using pipe dreams and Little's bumping algorithm. The proof extends to a principal specialization of the identity due to Fomin and Stanley. Our bijective tools also allow us to address a problem posed by Fomin and Kirillov from 1997, using work of Wachs, Lenart and Serrano-Stump.
Nous donnons une preuve bijective de l'identité des mots réduits de Macdonald, en utilisant des « pipe dreams » et l'algorithme « bumping » de Little. La preuve est étendue à une spécialisation principale de l'identité due à Fomin et Stanley. La méthode bijective nous permet aussi de traiter un problème posé par Fomin et Kirillov en 1997, en utilisant les travaux de Wachs, Lenart et Serrano-Stump.
On trees, tanglegrams, and tangled chains
by Sara Billey, Matjaz Konvalinka and Frederick Matsen
Tanglegrams are a class of graphs arising in computer science and in biological research on cospeciation and coevolution. They are formed by identifying the leaves of two rooted binary trees. The embedding of the trees in the plane is irrelevant for this application. We give an explicit formula to count the number of distinct binary rooted tanglegrams with \(n\) matched leaves, along with a simple asymptotic formula and an algorithm for choosing a tanglegram uniformly at random. The enumeration formula is then extended to count the number of tangled chains of binary trees of any length. This work gives a new formula for the number of binary trees with \(n\) leaves. Several open problems and conjectures are included along with pointers to several followup articles that have already appeared.
Les tanglegrams sont une classe de graphes qui apparaissent en informatique et en biologie dans le contexte de la cospéciation et de la coévolution. Ils sont formés en identifiant les feuilles de deux arbres binaires enracinés (les deux arbres n'étant pas munis d'un plongement). Nous donnons une formule explicite pour compter le nombre de tanglegrams binaires enracinés distincts avec \(n\) feuilles appariées, ainsi qu'une formule asymptotique simple et un algorithme pour engendrer un tanglegram aléatoire de manière uniforme. La formule de dénombrement est ensuite étendue pour compter le nombre de chaînes enchevêtrées d'arbres binaires de longueur quelconque. Cette analyse donne une nouvelle formule pour le nombre d'arbres binaires (non plongés) avec \(n\) feuilles. Plusieurs problèmes ouverts et conjectures sont inclus ainsi que les références de plusieurs articles complémentaires qui ont déjà paru.
Parabolic double cosets in Coxeter groups
by Sara Billey, Matjaz Konvalinka, T. Kyle Peterson, William Slofstra and Bridget Tenner
Parabolic subgroups \(W_I\) of Coxeter systems \((W,S)\) and their ordinary and double cosets \(W / W_I\) and \(W_I \backslash W / W_J\) appear in many contexts in combinatorics and Lie theory, including the geometry and topology of generalized flag varieties and the symmetry groups of regular polytopes. The set of ordinary cosets \(w W_I\), for \(I \subseteq S\), forms the Coxeter complex of \(W\), and is well-studied. In this extended abstract, we look at a less studied object: the set of all double cosets \(W_I w W_J\) for \(I, J \subseteq S\). Each double coset can be presented by many different triples \((I,w,J)\). We describe what we call the lex-minimal presentation and prove that there exists a unique such choice for each double coset. Lex-minimal presentations can be enumerated via a finite automaton depending on the Coxeter graph for \((W,S)\). In particular, we present a formula for the number of parabolic double cosets with a fixed minimal element when \(W\) is the symmetric group \(S_n\). In that case, parabolic subgroups are also known as Young subgroups. Our formula is almost always linear time computable in \(n\), and the formula can be generalized to any Coxeter group.
Sous-groupes paraboliques \( W_I \) de systèmes de Coxeter \( (W, S) \) et de leur classes ordinaires et doubles \( W / W_I \) et \( W_I \backslash W / W_J \) apparaissent dans de nombreux contextes dans combinatoire et la théorie de Lie, dont la géométrie et la topologie de variétés de drapeaux généralisées et les groupes de symétrie de polytopes réguliers. L'ensemble de classes ordinaires \( w W_I \), pour \( I \subseteq S \), forme le complexe de Coxeter de \( W \), et est bien étudié. Dans ce résumé étendu, nous regardons un objet moins étudié: l'ensemble des tous les classes doubles \( W_I w W_J \) pour \( I, J \subseteq S \). Chaque classe double peut être présenté par de nombreux triples différents \( (I, w, J) \). Nous décrivons ce que nous appelons la présentation lex-minimal et prouvons qu'il existe un tel choix unique pour chaque double classe. L'énumération des présentations lex-minimal peut être trouvé en utilisant un automate fini selon le graphe de Coxeter pour \( (W, S) \). En particulier, nous présentons une formule pour le nombre de classes paraboliques doubles avec un élément minimal fixé dans le cas \( W \) est le groupe symétrique \( S_n \). Dans ce cas, les sous-groupes paraboliques sont également connu sous le nom des sous-groupes de Young. Notre formule est presque toujours calculable dans un temps linéaire en \( n \). La formule peut être généralisée à tout groupe de Coxeter.
Slicings of parallelogram polyominoes, or how Baxter and Schroder can be reconciled
by Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi
We provide a new succession rule (i.e. generating tree) associated with Schröder numbers, that interpolates between the known succession rules for Catalan and Baxter numbers. We define Schröder and Baxter generalizations of parallelogram polyominoes (called slicings) which grow according to these succession rules. We also exhibit Schröder subclasses of Baxter classes, namely a Schröder subset of triples of non-intersecting lattice paths, and a new Schröder subset of Baxter permutations.
Nous décrivons une nouvelle règle de réécriture (c'est-à-dire un nouvel arbre de génération) correspondant aux nombres de Schröder, qui s'intercale entre les règles de réécriture connues pour les nombres de Catalan et de Baxter. Nous définissons des généralisations des polyominos parallélogrammes comptées par les nombres de Schröder et de Baxter dont la croissance est régie par ces règles de réécriture. Nous illustrons aussi notre travail en donnant des sous-classes de Schröder dans des classes de Baxter, en particulier un sous-ensemble de triplets de chemins non-intersectant énuméré par les nombres de Schröder, et une nouvelle sous-famille de Schröder dans l'ensemble des permutations de Baxter.
A lattice point counting generalisation of the Tutte polynomial
by Amanda Cameron and Alex Fink
The Tutte polynomial for matroids is not directly applicable to polymatroids. For instance, deletion-contraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact contains the same information as the Tutte polynomial when we restrict to matroids. This polynomial is constructed using lattice point counts in the Minkowski sum of the base polytope of a polymatroid and scaled copies of the standard simplex. We also show that, in the matroid case, our polynomial has coefficients of alternating sign, with a combinatorial interpretation closely tied to the Dawson partition.
Le polynôme de Tutte pour les matroïdes n'est pas directement applicable aux polymatroïdes. Par exemple, les propriétés de suppression et de contraction ne sont pas vérifiées. Nous construisons un polynôme pour les polymatroïdes qui se comporte de la même façon que le polynôme de Tutte d'un matroïde et qui contient en fait la même information que le polynôme de Tutte lorsqu'il est restreint aux matroïdes. Ce polynôme est construit en comptant les points entiers dans la somme de Minkowski du polytope des bases d'un polymatroïde et de copies homothétiques du simplexe standard. Nous montrons aussi que dans le cas d'un matroïde, notre polynôme a des coefficients à signes alternants, avec une interprétation étroitement liée à la partition de Dawson.
Matrix product and sum rule for Macdonald polynomials
by Luigi Cantini, Jan DeGier and Michael Wheeler
We present a new, explicit sum formula for symmetric Macdonald polynomials \(P_\lambda\) and show that they can be written as a trace over a product of (infinite dimensional) matrices. These matrices satisfy the Zamolodchikov-Faddeev (ZF) algebra. We construct solutions of the ZF algebra from a rank-reduced version of the Yang-Baxter algebra. As a corollary, we find that the normalization of the stationary measure of the multi-species asymmetric exclusion process is a Macdonald polynomial with all variables set equal to one.
Nous présentons une nouvelle formule explicite pour les polynômes symétriques de Macdonald \(P_{\lambda}\), et démontrons qu'ils peuvent être écrits comme une trace d'un produit de matrices de dimension infinie. Ces matrices forment une représentation de l'algèbre de Zamolodchikov-Faddeev (ZF). Nous élaborons des solutions de l'algèbre ZF en utilisant une version de l'algèbre Yang-Baxter de rang réduit. Comme corollaire, nous constatons que la normalisation de la mesure stationnaire du processus d'exclusion asymétrique est un polynôme de Macdonald avec toutes les variables rendues égale à un.
Asymptotic laws for knot diagrams
by Harrison Chapman
We study random knotting by considering knot and link diagrams as decorated, (rooted) topological maps on spheres and sampling them with the counting measure on from sets of a fixed number of vertices \(n\). We prove that random rooted knot diagrams are highly composite and hence almost surely knotted (this is the analogue of the Frisch-Wasserman-Delbrück conjecture) and extend this to unrooted knot diagrams by showing that almost all knot diagrams are asymmetric. The model is similar to one of Dunfield, et al.
Nous étudions les noeuds aléatoires en considérant les diagrammes de noeuds comme cartes planaires décorées sur lesquelles nous mettons la mesure uniforme de l'espace des cartes de \(n\) sommets (\(n\) fixé). Nous prouvons que les diagrammes de noeuds enracinés aléatoires sont très « composés » et de fait presque sûrement noués (ceci est un équivalent de la conjecture de Frisch-Wasserman-Delbrück). Nous étendons ensuite ce résultat aux diagrammes de noeuds non enracinés en montrant que tous les diagrammes de noeuds sont asymétriques. Ce modèle est similaire à celui de Dunfield, et al.
Matrix-Ball Construction of affine Robinson-Schensted correspondence
by Michael Chmutov, Pavlo Pylyavskyy and Elena Yudovina
In his study of Kazhdan-Lusztig cells in affine type \(A\), Shi has introduced an affine analog of Robinson-Schensted correspondence. We generalize the Matrix-Ball Construction of Viennot and Fulton to give a more combinatorial realization of Shi's algorithm. As a biproduct, we also give a way to realize the affine correspondence via the usual Robinson-Schensted bumping algorithm. Next, inspired by Honeywill, we extend the algorithm to a bijection between extended affine symmetric group and triples \((P, Q, \rho)\) where \(P\) and \(Q\) are tabloids and \(\rho\) is a dominant weight. The weights \(\rho\) get a natural interpretation in terms of the Affine Matrix-Ball Construction. Finally, we prove that fibers of the inverse map possess a Weyl group symmetry, explaining the dominance condition on weights.
Dans son étude des cellules de Kazhdan-Lusztig de type \(A\) affine, Shi a introduit un analogue affine de la correspondance de Robinson-Schensted. On généralise la Construction Matrice-Ballon de Viennot et Fulton afin de donner une réalisation plus combinatoire de l'algorithme de Shi. Comme sous-produit, on montre aussi un moyen de réaliser la correspondance affine par l'algorithme familier de l'insertion de Schensted. Puis, inspiré par Honeywill, on étend l'algorithme vers une bijection entre les éléments de la groupe affine symétrique étendue et les triples \((P,\,Q,\,\rho)\) o{ù} \(P\) et \(Q\) sont des tabloids et \(\rho\) est un poids. Les poids \(\rho\) obtiennent une interprétation naturelle en vue de la Construction Affine Matrice-Ballon. Finalement, on établit que les fibres de l'application inverse possèdent une symétrie du groupe de Weyl, ce qui explique la dominance des poids.
Plane partitions and the combinatorics of some families of reduced Kronecker coefficients
by Laura Colmenarejo
We compute the generating function of some families of reduced Kronecker coefficients. We give a combinatorial interpretation for these coefficients in terms of plane partitions. This unexpected relation allows us to check that the saturation hypothesis holds for the reduced Kronecker coefficients of our families. We also compute the quasipolynomial that govern these families, specifying the degree and period. Moving to the setting of Kronecker coefficients, these results imply some observations related to the rate of growth experienced by the families of Kronecker coefficients associated to the reduced Kronecker coefficients already studied.
Nous calculons les fonctions génératrices de certaines familles de coefficients de Kronecker réduits. Nous donnons une interprétation combinatoire de ces coefficients à l'aide de partitions planes. Cette relation inattendue nous permet de vérifier que l'hypothèse de saturation est vérifiée pour les coefficients de Kronecker réduits de nos familles. Nous calculons aussi le quasi-polynôme qui gouverne ces familles en spécifiant le degré et la période. En passant au coefficient de Kronecker, ces résultats impliquent certaines observations reliées au taux de croissance des familles de coefficients de Kronecker associés aux coefficients de Kronecker réduits déjà étudiés.
The facial weak order in finite Coxeter groups
by Aram Dermenjian, Christophe Hohlweg and Vincent Pilaud
We investigate a poset structure that extends the weak order on a finite Coxeter group \(W\) to the set of all faces of the permutahedron of \(W\). We call this order the {\em facial weak order}. We first provide two alternative characterizations of this poset: a first one, geometric, that generalizes the notion of inversion sets of roots, and a second one, combinatorial, that uses comparisons of the minimal and maximal length representatives of the cosets. These characterizations are then used to show that the facial weak order is in fact a lattice, generalizing a well-known result of A. Björner for the classical weak order. Finally, we show that any lattice congruence of the classical weak order induces a lattice congruence of the facial weak order, and we give a geometric interpretation of its classes.
Nous étudions une structure de poset qui étend l'ordre faible sur un groupe de Coxeter fini \(W\) à l'ensemble de toutes les faces du permutoèdre de \(W\). Nous appellons cet ordre {\em l'ordre faible facial}. Nous montrons d'abord deux caractérisations alternatives de ce poset : une première, géométrique, qui généralise la notion d'ensemble d'inversion, et une seconde, combinatoire, qui utilise des comparaisons entre les représentants minimaux et maximaux des faces. Ces caractérisations sont ensuite utilisées pour montrer que l'ordre faible facial est en fait un treillis, généralisant ainsi un résultat bien connu de A. Björner pour l'ordre faible classique. Finalement, nous montrons que toute congruence de treillis de l'ordre faible classique induit une congruence de treillis de l'ordre faible facial, et nous donnons une interprétation géométrique de ses classes.
The number of corner polyhedra graphs
by Clément Dervieux, Dominique Poulalhon and Gilles Schaeffer
Corner polyhedra were introduced by Eppstein and Mumford (2014) as the set of simply connected 3D polyhedra such that all vertices have non negative integer coordinates, edges are parallel to the coordinate axes and all vertices but one can be seen from infinity in the direction \((1,1,1)\). These authors gave a remarkable characterization of the set of corner polyhedra graphs, that is graphs that can be skeleton of a corner polyhedron: as planar maps, they are the duals of some particular bipartite triangulations, which we call hereafter corner triangulations. In this paper we count corner polyhedral graphs by determining the generating function of the corner triangulations with respect to the number of vertices: we obtain an explicit rational expression for it in terms of the Catalan generating function. We first show that this result can be derived using Tutte's classical compositional approach. Then, in order to explain the occurrence of the Catalan series we give a direct algebraic decomposition of corner triangulations: in particular we exhibit a family of almond triangulations that admit a recursive decomposition structurally equivalent to the decomposition of binary trees. Finally we sketch a direct bijection between binary trees and almond triangulations. Our combinatorial analysis yields a simpler alternative to the algorithm of Eppstein and Mumford for endowing a corner polyhedral graph with the cycle cover structure needed to realize it as a polyhedral graph.
Eppstein et Mumford (2014) ont défini l'ensemble des polyèdres en coin comme l'ensemble des polyèdres 3D dont les sommets sont à coordonnées entières positives, les arêtes sont parallèles aux axes de coordonnées et tous les sommets sont visibles depuis l'infini dans la direction \((1,1,1)\). Ils décrivent l'ensemble des graphes de polyèdres en coin, i.e. des graphes squelettes d'un polyèdre en coin\;: vus comme cartes planaires, il s'agit des graphes duaux de certaines triangulations bicoloriées particulières, que nous appelons triangulations en coin enracinées. Dans le présent article nous comptons les graphes de polyèdres en coin en déterminant la série génératrice des triangulations en coin enracinées selon leur nombre de sommets\;: nous en obtenons une expression explicite en fonction de la série génératrice des nombres de Catalan. Ce résultat découle de la méthode de composition de Tutte mais pour expliquer l'apparition des nombres de Catalan, nous donnons aussi une décomposition algébrique des triangulations en coin\;: en particulier nous mettons en évidence une famille de triangulations en amande qui admet une décomposition structurellement équivalente à celle des arbres binaires. Pour finir nous présentons rapidement une bijection directe entre les arbres binaires et ces triangulations en amande. Notre analyse combinatoire conduit à un algorithme plus simple que celui d'Eppstein et Mumford pour munir un graphe de polyèdre en coin d'une couverture par cycles permettant de le réaliser effectivement comme polyèdre en coin.
Resonance in orbits of plane partitions
by Kevin Dilks, Oliver Pechenik and Jessica Striker
We introduce a new concept of resonance on discrete dynamical systems. Our main result is an equivariant bijection between plane partitions in a box under rowmotion and increasing tableaux under \(K\)-promotion, using a generalization of the equivariance of promotion and rowmotion [J. Striker-N. Williams '12] to higher dimensional lattices. This theorem implies new results for \(K\)-promotion and new proofs of previous results on plane partitions.
Nous introduisons le nouveau concept de résonance pour les systèmes dynamiques discrets. Notre résultat principal est une bijection équivariante entre partitions planes dans une boîte sous rowmotion et tableaux croissants sous \(K\)-promotion, en utilisant une généralisation de la équivariance de promotion et de rowmotion [J. Striker-N. Williams `12] aux treillis en dimensions supérieures. Ce théorème implique de nouveaux résultats pour \(K\)-promotion et de nouvelles preuves de résultats connus pour partitions planes.
Cumulants of Jack symmetric functions and \(b\)-conjecture (extended abstract)
by Maciej Dołęga and Valentin Féray
Goulden and Jackson (1996) introduced, using Jack symmetric functions, some multivariate generating series \(\psi(\mathbf{x}, \mathbf{y}, \mathbf{z}; t, 1+\beta)\) that might be interpreted as a continuous deformation of the rooted hypermap generating series. They made the following conjecture: coefficients of \(\psi(\mathbf{x}, \mathbf{y}, \mathbf{z}; t, 1+\beta)\) are polynomials in \(\beta\) with nonnegative integer coefficients. Moreover, \(\psi(\mathbf{x}, \mathbf{y}, \mathbf{z}; t, 1+\beta)\) can conjecturally be written as a multivariate generating series of general hypermaps, where the exponent of \(\beta\) is an integer-valued hypermap statistics that in some sense « measures the non-orientability » of the corresponding hypermap. We prove partially this conjecture, nowadays called \(b\)-conjecture, by showing that coefficients of \(\psi(\mathbf{x}, \mathbf{y}, \mathbf{z}; t, 1+ \beta)\) are polynomials in \(\beta\) with rational coefficients. Until now, it was only known that they are rational functions of \(\beta\). A key step of the proof is a strong factorization property of Jack polynomials when \(\alpha \to 0\) that may be of independent interest.
Goulden et Jackson (1996) ont introduit, en utilisant les fonctions symétriques de Jack, une série génératrice multivariée \(\psi(\mathbf{x}, \mathbf{y}, \mathbf{z}; t, 1+\beta)\) qui est une déformation continue de séries génératrices de cartes enracinées. Ils ont fait la conjecture suivante : les coefficients de \(\psi(\mathbf{x}, \mathbf{y}, \mathbf{z}; t, 1+\beta)\) sont des polynômes en \(\beta\) avec des coefficients entiers positifs. Nous prouvons partiellemnt cette conjecture, en établissant la polynomialité en \(\beta\) des coefficients de \(\psi(\mathbf{x}, \mathbf{y}, \mathbf{z}; t, 1+ \beta)\) (ces coefficients sont a priori des fonctions rationnelles en \(\beta\)). Un ingrédient clé de notre preuve, potentiellement intéressant par ailleurs, est une propriété de factorisation forte des polynômes de Jack quand \(\alpha\) tend vers \(0\).
A non-partitionable Cohen-Macaulay simplicial complex
by Art Duval, Bennet Goeckner, Caroline Klivans and Jeremy Martin
A long-standing conjecture of Stanley states that every Cohen-Macaulay simplicial complex is partitionable. We disprove the conjecture by constructing an explicit counterexample. Due to a result of Herzog, Jahan and Yassemi, our construction also disproves the conjecture that the Stanley depth of a monomial ideal is always at least its depth.
Une conjecture de longue date de Stanley affirme que chaque complexe simplicial Cohen-Macaulay est partitionnable. Nous réfutons la conjecture en construisant un contre-exemple explicite. En raison d'un résultat de Herzog, Jahan et Yassemi, nos construction réfute également la conjecture que la profondeur Stanley d'un idéal monôme est toujours supérieure ou égale à sa profondeur.
Noncrossing partitions, toggles, and homomesies
by David Einstein, Miriam Farber, Emily Gunawan, Michael Joseph, Matthew Macauley, James Propp and Simon Rubinstein-Salzedo
We introduce \(n(n-1)/2\) natural involutions (« toggles ») on the set \(S\) of noncrossing partitions \(\pi\) of size \(n\), along with certain composite operations obtained by composing these involutions. We show that for many operations \(T\) of this kind, a surprisingly large family of functions \(f\) on \(S\) (including the function that sends \(\pi\) to the number of blocks of \(\pi\)) exhibits the homomesy phenomenon: the average of \(f\) over the elements of a \(T\)-orbit is the same for all \(T\)-orbits. Our methods apply more broadly to toggle operations on independent sets of certain graphs.
On introduit \(n(n-1)/2\) involutions naturelles (« toggles ») de l'ensemble \(S\) des partitions noncroisés \(\pi\) de cardinalité \(n\), et certaines operations composites obtenu en composant ces involutions. On prouvera que pour la plupart des operations \(T\), une étonnant grande famille de fonctionnes \(f\) sur \(S\) (contenant la fonction qui envoie \(\pi\) sur les nombres de bloques de \(\pi\)) presente le phénomène de homomesie: la moyenne de \(f\) sur les éléments d'une orbite de \(T\), c'est la même pour toutes orbites de \(T\). Notre épreuve s'applique plus largement à les operations de toggle sur la collection des ensembles indépendants de certain graphes.
On intervals of the consecutive pattern poset
by Sergi Elizalde and Peter R. W. McNamara
The consecutive pattern poset is the infinite partially ordered set of all permutations where \(\sigma\le\tau\) if \(\tau\) has a subsequence of adjacent entries in the same relative order as the entries of \(\sigma\). We study the structure of the intervals in this poset from topological, poset-theoretic, and enumerative perspectives. In particular, we prove that all intervals are rank-unimodal and strongly Sperner, and we characterize disconnected and shellable intervals. We also show that most intervals are not shellable and have Möbius function equal to zero.
Le poset des motifs consécutifs est l'ensemble infini partiellement ordonné de toutes les permutations où \(\sigma\le\tau\) si \(\tau\) a une subséquence des entrées adjacentes dans le même ordre relatif que les entrées de \(\sigma\). Nous étudions la structure des intervalles dans ce poset des perspectives topologique et énumérative. En particulier, nous prouvons que tous les intervalles sont de rang unimodale et fortement Sperner, et nous caractérisons les intervalles déconnectés et enveloppables (« shellable »). Nous montrons également que la plupart des intervalles ne sont pas enveloppables et ils ont fonction de Möbius égal à zéro.
Schur-positivity via products of grid classes
by Sergi Elizalde and Yuval Roichman
Characterizing sets of permutations whose associated quasisymmetric function is symmetric and Schur-positive is a long-standing problem in algebraic combinatorics. In this paper we present a general method to construct Schur-positive sets and multisets, based on geometric grid classes and the product operation. Our approach produces many new instances of Schur-positive sets, and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.
La caractérisation des ensembles de permutations dont la fonction quasisymmetrique associée est symétrique et Schur-positive est un problème de longue date dans la combinatoire algébrique. Dans cet article, nous présentons une méthode générale pour construire des ensembles et multiensembles Schur-positifs, basée sur des {\it grid} classes géométriques et l'opération de multiplication. Notre approche produit beaucoup de nouveaux cas d'ensembles Schur-positifs, et elle fournit un cadre général qui explique l'existence de tels ensembles qui jusqu'à maintenant étaient des cas sporadiques.
Toric matrix Schubert varieties and root polytopes (extended abstract)
by Laura Escobar and Karola Meszaros
Start with a permutation matrix \(\pi\) and consider all matrices that can be obtained from \(\pi\) by taking downward row operations and rightward column operations; the closure of this set gives the matrix Schubert variety \(\overline{X_\pi}\). We characterize when the ideal defining \(\overline{X_\pi}\) is toric (with respect to a \(2n-1\)-dimensional torus) and study the associated polytope of its projectivization. We construct regular triangulations of these polytopes which we show are geometric realizations of a family of subword complexes. We also show that these complexes can be realized geometrically via regular triangulations of root polytopes. This implies that a family of \(\beta\)-Grothendieck polynomials are special cases of reduced forms in the subdivision algebra of root polytopes. We also write the volume and Ehrhart series of root polytopes in terms of \(\beta\)-Grothendieck polynomials. Subword complexes were introduced by Knutson and Miller in 2004, who showed that they are homeomorphic to balls or spheres and raised the question of their polytopal realizations.
En partant d'une matrice de permutation \(\pi\), considérons toutes les matrices qui peuvent être obtenues à partir de \(\pi\) en effectuant des opérations de ligne vers le bas et des opérations de colonne vers la droite ; l'adhérence de cet ensemble donne la variété Schubert de matrices \(\overline{X_\pi}\). Nous caractérisons la situation où l'idéal définissant \(\overline{X_\pi}\) est torique et étudions le polytope associé de sa projectivisation. Nous construisons des triangulations régulières de ces polytopes et nous montrons qu'elles sont des réalisations géométriques d'une famille de complexes de sous-mots. Nous montrons également que ces complexes peuvent être réalisés géométriquement par des triangulations régulières de polytopes de racines. Cela implique qu'une famille de polynômes \(\beta\)-Grothendieck sont des cas particuliers de formes réduites dans l'algèbre de subdivision de polytopes des racines. On peut aussi écrire le volume et la série d'Ehrhart des polytopes des racines en termes de \(\beta\)-Grothendieck polynômes. Les complexes de sous-mots ont été introduits par Knutson et Miller en 2004, qui ont soulevé la question de leurs réalisations polytopales.
From generalized Tamari intervals to non-separable planar maps (extended abstract)
by Wenjie Fang and Louis-François Préville-Ratelle
Let \(v\) be a grid path made of north and east steps. The lattice \tam{v}, based on all grid paths weakly above the grid path \(v\) sharing the same endpoints as \(v\), was introduced by Préville-Ratelle and Viennot (2014) and corresponds to the usual Tamari lattice in the case \(v=(NE)^n\). They showed that \tam{v} is isomorphic to the dual of \tam{\overleftarrow{v}}, where \(\overleftarrow{v}\) is the reverse of \(v\) with \(N\) and \(E\) exchanged. Our main contribution is a bijection from intervals in \tam{v} to non-separable planar maps. It follows that the number of intervals in \tam{v} over all \(v\) of length \(n\) is \(\frac{2 (3n+3)!}{(n+2)! (2n+3)!}\). This formula was first obtained by Tutte(1963) for non-separable planar maps.
Soit \(v\) un chemin constitué de pas Nord et Est. Le treillis \tam{v}, basé sur tous les chemins faiblement au dessus de \(v\) avec les mêmes extrémités que \(v\), a été introduit par Préville-Ratelle et Viennot (2014) et correspond au treillis de Tamari classique dans le cas \(v=(NE)^n\). Ils ont démontré que \tam{v} est isomorphe au treillis dual de \tam{\overleftarrow{v}}, où \(\overleftarrow{v}\) est \(v\) renversé avec \(N\) et \(E\) échangés. Notre contribution principale est une bijection entre les intervalles de \tam{v} et les cartes planaires non-séparables. Il s'ensuit que le nombre d'intervalles dans \tam{v} sur tous les chemins \(v\) de longueur \(n\) est donné par \( \frac{2 (3n+3)!}{(n+2)! (2n+3)!}\). Cette formule a été obtenue par Tutte(1963) pour les cartes planaires non-séparables.
Weak Separation, Pure Domains and Cluster Distance
by Miriam Farber and Pavel Galashin
Following the proof of the purity conjecture for weakly separated sets, recent years have revealed a variety of wider classes of pure domains in different settings. In this paper we show the purity for domains consisting of sets that are weakly separated from a pair of « generic » sets \(I\) and \(J\). Our proof also gives a simple formula for the rank of these domains in terms of \(I\) and \(J\). This is a new instance of the purity phenomenon which essentially differs from all previously known pure domains. We apply our result to calculate the cluster distance and to give lower bounds on the mutation distance between cluster variables in the cluster algebra structure on the coordinate ring of the Grassmannian. Using a linear projection that relates weak separation to the octahedron recurrence, we also find the exact mutation distances and cluster distances for a family of cluster variables.
Suite à la preuve de la conjecture de pureté sur les ensembles faiblement séparés, des familles variées de domaines pures sont apparues récemment dans différents contextes. Dans cet article, nous prouvons la pureté de domaines formés par les ensembles qui sont faiblement séparés d'une paire d'ensembles « génériques » \(I\) et \(J\). Notre preuve donne aussi une formule simple pour le rank de ces domaines en termes de \(I\) et \(J\). Il s'agit d'une nouvelle instance du phénomène de pureté qui diffère essentiellement de tous les domaines pures connus précédemment. Nous appliquons notre résultat pour calculer la distance d'amas et pour donner des bornes inférieures sur la distance de mutation entre les variables d'amas dans la structure d'algèbre amassée sur l'anneau de coordonnées de la Grassmannienne. En utilisant une projection linéaire qui relie la séparation faible à la récurrence de l'octaèdre, nous trouvons aussi les distances de mutation et les distances d'amas exactes pour une famille de variables d'amas.
Quasi-isomorphisms of cluster algebras and the combinatorics of webs
by Chris Fraser
We provide bijections between the cluster variables (and clusters) in two families of cluster algebras which have received considerable attention. These cluster algebras are the ones associated with certain Grassmannians of \(k\)-planes, and those associated with certain spaces of decorated \({SL}_k\)-local systems in the disk in the work of Fock and Goncharov. When \(k\) is \(3\), this bijection can be described explicitly using the combinatorics of Kuperberg's basis of non-elliptic webs. Using our bijection and symmetries of these cluster algebras, we provide evidence for conjectures of Fomin and Pylyavskyy concerning cluster variables in Grassmannians of \(3\)-planes. We also prove their conjecture that there are infinitely many indecomposable nonarborizable webs in the Grassmannian of \(3\)-planes in \(9\)-dimensional space.
Nous fournissons des bijections entre les variables amassées de deux familles d'algébres amassées qui ont reçu de l`attention considérable. Ces algébres amassées sont celles associées à certaines grassmanniennes de \( k\) -plans et celles associées à certains espaces de \({SL}_k\)-systèmes locaux décorés sur le disque au sens de Fock et Goncharov. Lorsque \(k=3\), cette bijection peut être décrite explicitement en utilisant la combinatoire de la base de Kuperberg des toiles réduites. Notre bijection, ainsi que certaines symétries de ces algébres amassées, fournit de l`évidence pour les conjectures de Fomin et Pylyavskyy concernant les variables amassées dans les grassmanniennes de dimension \(3\). Nous démontrons aussi leur conjecture qu'il existe une infinité de toiles nonarborizables indécomposables dans la grassmannienne de \( 3 \) -plans dans un espace de dimension \(9\).
Affine type A geometric crystal structure on the Grassmannian
by Gabriel Frieden
We construct a type \(A_{n-1}^{(1)}\) affine geometric crystal structure on the Grassmannian \(\text{Gr}(k,n)\). The tropicalization of this structure recovers the combinatorics of crystal operators on semistandard Young tableaux of rectangular shape (with \(n-k\) rows), including the affine crystal operator \(\widetilde{e_0}\). In particular, the promotion operation on these tableaux essentially corresponds to cyclically shifting the Plücker coordinates of the Grassmannian.
Nous munissons la grassmannienne \(\text{Gr}(k,n)\) d'une structure de cristal géométrique affine en type \(A_{n-1}^{(1)}\). La tropicalisation de cette structure recouvre la combinatoire des opérateurs de cristal sur les tableaux de Young semistandards de forme rectangulaire (avec \(n-k\) lignes), y compris l'opérateur affine \(\widetilde{e_0}\). En particulier, l'opération de promotion sur ces tableaux correspond essentiellement au décalage cyclique des coordonées plückeriennes de la grassmannienne.
Cyclic inclusion-exclusion and the kernel of P-partitions
by Valentin Féray
Following the lead of Stanley and Gessel, we consider a linear map which associates to an acyclic directed graph (or a poset) a quasi-symmetric function. The latter is naturally defined as multivariate generating series of non-decreasing functions on the graph (or of \(P\)-partitions of the poset). We describe the kernel of this linear map, using a simple combinatorial operation that we call {\em cyclic inclusion-exclusion}. Our result also holds for the natural non-commutative analog and for the commutative and non-commutative restrictions to bipartite graphs.
Dans la lignée de Stanley et Gessel, nous considérons une application linéaire qui associe à un graphe dirigé acyclique (ou à un poset) une fonction quasi-symétrique. Celle-ci est définie comme la série génératrice multi-variée des fonction croissantes sur le graphe (ou des \(P\)-partitions du poset). Nous décrivons le noyau de cette application linéaire, à l'aide d'une opération combinatoire simple, que nous appelons {\em inclusion-exclusion cyclique}. Notre résultat est aussi valable pour l'analogue non-commutatif naturel et les restrictions commutative et non-commutative aux graphes bipartis.
Refined dual stable Grothendieck polynomials and generalized Bender-Knuth involutions
by Pavel Galashin, Darij Grinberg and Gaku Liu
The dual stable Grothendieck polynomials are a deformation of the Schur functions, originating in the study of the \(K\)-theory of the Grassmannian. We generalize these polynomials by introducing a countable family of additional parameters such that the generalization still defines symmetric functions. We outline two self-contained proofs of this fact, one of which constructs a family of involutions on the set of reverse plane partitions generalizing the Bender-Knuth involutions on semistandard tableaux, whereas the other classifies the structure of reverse plane partitions with entries 1 and 2.
Les polynômes de Grothendieck stables duaux sont une déformation des fonctions de Schur provenant de l'étude de la K-théorie de la Grassmannienne. Nous généralisons ces polynômes en introduisant une famille dénombrable de paramètres additionnels de sorte que cette généralisation définisse encore des fonctions symétriques. Nous présentons deux preuves auto-suffisantes de ce fait, dont l'une construit une famille d'involutions de l'ensemble des partitions planes inversées généralisant les involutions de Bender-Knuth sur les tableaux semi-standards, tandis que l'autre classifie la structure des partitions planes avec entrées 1 et 2.
Oriented flip graphs and noncrossing tree partitions
by Alexander Garver and Thomas McConville
Given a tree embedded in a disk, we define two lattices - the oriented flip graph of noncrossing arcs and the lattice of noncrossing tree partitions. When the interior vertices of the tree have degree 3, the oriented flip graph is equivalent to the oriented exchange graph of a type A cluster algebra. Our main result is an isomorphism between the shard intersection order of the oriented flip graph and the lattice of noncrossing tree partitions. As a consequence, we deduce a simple characterization of c-matrices of type A cluster algebras.
À partir d'un arbre plongé dans un disque, nous définissions deux réseaux: le "flip graph" orienté des arcs non-croisés et le treillis des partitions non-croisées de l'arbre. Lorsque les sommets intérieurs de l'arbre ont degré 3, le "flip graph" orienté est équivalent au graphe d'échange orienté d'une algèbre amassée de type A. Notre résultat principal est un isomorphisme entre l'ordre d'intersection des tissons du "flip graph" orienté et le treillis des partitions non-croisées de l'arbre. Nous en déduisons une caractérisation simple des c-matrices des algèbres amassées de type A.
Monodromy and K-theory of Schubert curves via generalized jeu de taquin
by Maria Gillespie and Jake Levinson
We establish a combinatorial connection between the real geometry and the \(K\)-theory of complex Schubert curves \(\mathcal{S}(\lambda_\bullet)\), which are one-dimensional Schubert problems defined with respect to flags osculating the rational normal curve. In a previous paper, the second author showed that the real geometry of these curves is described by the orbits of a map \(\omega\) on skew tableaux, defined as the commutator of jeu de taquin rectification and promotion. In particular, the real locus of the Schubert curve is naturally a covering space of \(\mathbb{RP}^1\), with \(\omega\) as the monodromy operator. We provide a fast, local algorithm for computing \(\omega\) without rectifying the skew tableau, and show that certain steps in our algorithm are in bijective correspondence with Pechenik and Yong's genomic tableaux, which enumerate the \(K\)-theoretic Littlewood-Richardson coefficient associated to the Schubert curve. Using this bijection, we give purely combinatorial proofs of several numerical results involving the \(K\)-theory and real geometry of \(\mathcal{S}(\lambda_\bullet)\).
Nous établissons une connection entre la géométrie réelle et la K-théorie des courbes de Schubert \(\mathcal{S}(\lambda_\bullet)\). Ces dernières sont des problèmes de Schubert, de dimension \(1\), définies par rapport à des drapeaux tangents à la courbe rationelle normale. Le deuxième auteur a démontré auparavant que la géométrie de ces courbes est décrite par les orbites d'une transformation \(\omega\) de tableaux de Young gauches : le commutateur de la rectification (au sens du jeu de taquin de Schützenberger) et de la promotion. Les points réels de \(\mathcal{S}(\lambda_\bullet)\) forment alors un revêtement de \(\mathbb{RP}^1\) avec \(\omega\) comme opérateur de monodromie. Nous introduisons un algorithme local et rapide qui permet de calculer \(\omega\) sans devoir rectifier le tableau. Nous démontrons ensuite que certaines étapes de l'algorithme sont en bijection avec les tableaux génomiques de Pechenik-Yong, lesquels énumèrent le coefficient de Littlewood-Richardson K-théorique associé à \(\mathcal{S}(\lambda_\bullet)\). Finalement, nous démontrons de façon purement combinatoire certaines propriétés géométriques et K-théoriques de \(\mathcal{S}(\lambda_\bullet)\).
A combinatorial approach to Macdonald \(q,t\)-symmetry via the Carlitz bijection
by Maria Gillespie
We investigate the combinatorics of the symmetry relation \(\widetilde{H}_{\mu}(\mathbf{x};q,t)=\widetilde{H}_{\mu^\ast}(\mathbf{x};t,q)\) on the transformed Macdonald polynomials, from the point of view of the combinatorial formula of Haglund, Haiman, and Loehr in terms of the \(\mathrm{inv}\) and \(\mathrm{maj}\) statistics on Young diagram fillings. By generalizing the Carlitz bijection on permutations, we provide a purely combinatorial proof of the relation in the case of Hall-Littlewood polynomials (\(q=0\)) for the coefficients of the square-free monomials in the variables \(\mathbf{x}\). Our work in this case relates the Macdonald \(\mathrm{inv}\) and \(\mathrm{maj}\) statistics to the monomial basis of the modules \(R_\mu\) studied by Garsia and Procesi. We also provide a new proof for the full Macdonald relation in the case when \(\mu\) is a hook shape.
Nous investiguons la combinatoire de la relation \(\widetilde{H}_{\mu}(\mathbf{x};q,t)=\widetilde{H}_{\mu^\ast}(\mathbf{x};t,q)\) des polynômes (transformés) de Macdonald, du point de vue de la formule de Haglund, Haiman et Loehr, exprimant ces polynômes en termes d'inversions et d'indices majeurs de remplissages de diagrammes de Young. Nous généralisons la bijection de Carlitz sur les permutations, ce qui nous permet de déduire cette relation pour les polynômes de Hall-Littlewood (le cas \(q=0\)), de façon purement combinatoire, pour les monômes sans carrés dans les variables \(\mathbf{x}\). Notre approche lie les statistiques de Macdonald \(\mathrm{inv}\) et \(\mathrm{maj}\) à la base monomiale des modules \(R_\mu\) de Garsia-Procesi. Nous fournissons aussi une nouvelle démonstration de la relation (complète) de Macdonald lorsque \(\mu\) est une équerre.
The colored symmetric and exterior algebras
by Rafael González D'León
In this extended abstract we present colored generalizations of the symmetric algebra and its Koszul dual, the exterior algebra. The symmetric group \(\mathfrak{S}_n\) acts on the multilinear components of these algebras. While \(\mathfrak{S}_n\) acts trivially on the multilinear components of the colored symmetric algebra, we use poset topology techniques to describe the representation on its Koszul dual. We introduce an \(\mathfrak{S}_n\)-poset of weighted subsets that we call the weighted boolean algebra and we prove that the multilinear components of the colored exterior algebra are \(\mathfrak{S}_n\)-isomorphic to the top cohomology modules of its maximal intervals. We show that the two colored Koszul dual algebras are Koszul in the sense of Priddy et al.
Dans ce résumé détaillé, nous présentons des généralisations colorées de l'algèbre symétrique et de sa duale de Koszul, l'algèbre extérieure. Le groupe symétrique \(\mathfrak{S}_n\) agit sur les composantes multilinéaires de ces algèbres. Tandis que \(\mathfrak{S}_n\) agit trivialement sur les composantes multilinéaires de l'algèbre symétrique colorée, nous utilisons les techniques topologiques de la théorie des ensembles partiellement ordonnés pour décrire la représentation sur sa duale de Koszul. Nous introduisons un \(\mathfrak{S}_n\)-ensemble partiellement ordonné de sous-ensembles pondérés que nous appelons l'algèbre de Boole pondérée et nous montrons que les composantes multilinéaires de l'algèbre extérieure colorée sont \(\mathfrak{S}_n\)-isomorphes aux modules cohomologiques supérieurs de ses intervalles maximaux. Nous montrons que les deux algèbres colorées sont des Koszul dans le sens apporté par Priddy et al.
Rational Dyck Paths in the Non Relatively Prime Case
by Eugene Gorsky, Mikhail Mazin and Monica Vazirani
We study the relationship between rational slope Dyck paths and invariant subsets in \(\mathbb{Z}\), extending the work of the first two authors in the relatively prime case. We also find a bijection between \((dn,dm)\)-Dyck paths and \(d\)-tuples of \((n,m)\)-Dyck paths endowed with certain gluing data. These are first steps towards understanding the relationship between the rational slope Catalan combinatorics in non relatively prime case and the geometry of affine Springer fibers and representation theory.
Nous étudions les relations entre les chemins de Dyck à pente rationnelle et des sous-ensembles invariants en \(\mathbb{Z}\), étendant le travail des deux premiers auteurs dans le cas relativement premier. On trouve aussi une bijection entre les \((dn,dm)\)-chemins de Dyck et des \(d\)-tuples de \((n,m)\)-chemins de Dyck avec certaines données de collage. Ce sont les premiers pas vers la compréhension des relations entre la combinatoire Catalan de pentes rationnelles dans le cas non-relativement premier, et la géométrie des fibres affines de Springer et la théorie de la représentation.
Asymptotics of Bivariate Analytic Functions with Algebraic Singularities
by Torin Greenwood
In this paper, we use the multivariate analytic techniques of Pemantle and Wilson to find asymptotic formulae for the coefficients of a broad class of multivariate generating functions with algebraic singularities. Flajolet and Odlyzko (1990) analyzed the coefficients of a class of univariate generating functions with algebraic singularities. These results have been extended to classes of multivariate generating functions by Gao and Richmond (1992) and Hwang (1996, 1998), in both cases by immediately reducing the multivariate case to the univariate case. Pemantle and Wilson (2013) outlined new multivariate analytic techniques and used them to analyze the coefficients of rational generating functions.
Dans ce papier, on utilise des techniques analytiques multivariées dévéloppées par Pemantle et Wilson pour trouver des développements asymptotiques des coefficients d'une large classe de séries génératrices multivariées avec singularités algébriques. Flajolet et Odlyzko (1990) ont analysé les coefficients d'une classe de séries génératrices univariées avec singularités algébriques. Ces résultats ont été généralisés aux classes de séries génératrices multivariées par Gao et Richmond (1992) et Hwang (1996, 1998). Dans les deux cas, on peut immédiatement réduire le cas multivarié au cas univarié. Pemantle et Wilson (2013) ont décrit de nouvelles techniques analytiques multivariées et ils les ont utilisées pour analyser les coefficients des séries génératrices rationelles.
The Delta Conjecture
by James Haglund, Jeffrey Remmel and Andrew Wilson
We conjecture two combinatorial interpretations for the symmetric function \(\Delta_{e_k} e_n\), where \(\Delta_f\) is an eigenoperator for the modified Macdonald polynomials defined by Bergeron, Garsia, Haiman, and Tesler. Both interpretations can be seen as generalizations of the Shuffle Conjecture, a statement originally conjectured by Haglund, Haiman, Remmel, Loehr, and Ulyanov and recently proved by Carlsson and Mellit. We show how previous work of the second and third authors on Tesler matrices and ordered set partitions can be used to verify several cases of our conjectures. Furthermore, we use a reciprocity identity and LLT polynomials to prove another case. Finally, we show how our conjectures inspire 4-variable generalizations of the Catalan numbers, extending work of Garsia, Haiman, and the first author.
Nous conjecturons deux interprétations combinatoires pour la fonction symétrique \(\Delta_{e_k} e_n\), où \(\Delta_f \) est un eigenoperator pour les polynômes de Macdonald modifiés dèfinis par Bergeron, Garsia, Haiman, et Tesler. Les deux interprétations peuvent être considérés comme des généralisations de le Shuffle Conjecture, une déclaration à l'origine conjecturé par Haglund, Haiman, Remmel, Loehr, et Ulyanov et a récemment prouvé par Carlsson et Mellit. Nous montrons comment le travail préalable des deuxième et troisième auteurs sur les matrices Tesler et ensemble ordonné partitions peuvent être utilisés pour vérifier plusieurs cas de nos conjectures. En outre, nous utilisons une identité de réciprocité et LLT polynômes de prouver une autre affaire. Enfin, nous montrons comment nos conjectures inspirent généralisations 4 variables des nombres de Catalan, l'extension du travail de Garsia, Haiman, et le premier auteur.
Factorial Characters and Tokuyama's Identity for Classical Groups
by Angele Hamel and Ronald King
In this paper we introduce factorial characters for the classical groups and derive a number of central results. Classically, the factorial Schur function plays a fundamental role in traditional symmetric function theory and also in Schubert polynomial theory. Here we develop a parallel theory for the classical groups, offering combinatorial definitions of the factorial characters for the symplectic and orthogonal groups, and further establish flagged factorial Jacobi-Trudi identities and factorial Tokuyama identities, providing proofs in the symplectic case. These identities are established by manipulating determinants through the use of certain recurrence relations and by using lattice paths.
Ici nous présentons des caractères factoriels pour des groupes classiques, et nous dérivons plusieurs résultats importants. Classiquement, le fonction de Schur factoriel joue une rôle fondamentale dans la théorie traditionnelle des fonctions symétriques et aussi dans la théorie des polynômes de Schubert. Ici nous développons une théorie paralléle à celle des groupes classiques, offrons des définitions combinatoire des caractères factoriels pour des groupes symplectiques et orthogonaux, et nous établissons aussi des identités de \guillemotleft{} flagged factorial Jacobi Trudi \guillemotright{} et de \guillemotleft{} factorial Tokyama \guillemotright{}, donnant des preuves dans le cas symplectique. Ces identités sont etablies par la manipulation des déterminants en utilisant de certains récurrences, et en utliisant des chemins.
New hook-content formulas for strict partitions (extended abstract)
by Guo-Niu Han and Huan Xiong
We introduce the difference operator for functions defined on strict partitions and prove a polynomiality property for a summation involving the bar length (hook length) and content statistics. As an application, several new hook-content formulas for strict partitions are derived.
Nous introduisons l'opérateur de différence pour les fonctions définies sur les partitions strictes et démontrons qu'une somme en fonction des équerres et des contenus est un polynôme. En particulier, nous obtenons plusieurs nouvelles formules des équerres et des contenus pour les partitions strictes.
Parking functions, tree depth and factorizations of the full cycle into transpositions
by John Irving and Amarpreet Rattan
Consider the set \(\mathcal{F}_n\) of factorizations of the full cycle \((0\,1\,2\,\cdots\,n) \in \mathfrak{S}_{\{0,1,\ldots,n\}}\) into \(n\) transpositions. Write any such factorization \((a_1\,b_1)\cdots(a_n\,b_n)\) with all \(a_i < b_i\) to define its lower and upper sequences \((a_1,\ldots,a_n)\) and \((b_1,\ldots,b_n)\), respectively. Remarkably, any factorization can be uniquely recovered from its lower (or upper) sequence. In fact, Biane (2002) showed that the simple map sending a factorization to its lower sequence is a bijection from \(\mathcal{F}_n\) to the set \(\mathcal{P}_n\) of parking functions of length \(n\). Reversing this map to recover the factorization (and, hence, upper sequence) corresponding to a given lower sequence is nontrivial. In this paper we investigate several interesting properties of full cycle factorizations with respect to their upper and lower sequences. In particular, we show that area statistics on upper / lower sequences correspond with inversion / non-inversion statistics on labelled trees. Our study centres around a natural bivariate generalization of the well-studied tree inversion enumerator of Mallows and Riordan.
Considérons l'ensemble des factorisations minimales du cycle complet canonique dans le groupe symétrique sur \(n+1\) symboles. En 2002, Biane a trouvé une bijection remarquablement simple de cet ensemble à l'ensemble des fonctions parking de longueur \(n\); la bijection mappe une factorisation à la séquence composée de la plus petite élément de chaque transposition. Ainsi, il est absolument trivial à trouver l'image d'un factorisation sous cette fonction, mais inverser cette fonction nécessite beaucoup plus travail. Par ailleurs, en ce qui concerne les fonctions parking, la plus grande élément de chaque transposition semble contenir aucune information. Nous montrons, cependant, que la séquence de la plus grande élément de chaque transposition est intéressante aussi. Notamment, les statistiques d'area naturelle sur cette séquence et la fonction parking correspondent ensemble à deux statistiques naturelles sur les arbres: le nombre inversion (ce qui est bien connu) et le nombre non-inversion. Cela nous permet de présenter une fonction génératrice bivariée, qui est une généralisation naturelle de la fonction génératrice inversion univariée pour les arbres de Mallows et Riordan. Nous donnons aussi quelques résultants alliérs.
Intersections of Amoebas
by Martina Juhnke-Kubitzke and Timo de Wolff
Amoebas are projections of complex algebraic varieties in the algebraic torus under a Log-absolute value map, which have connections to various mathematical subjects. While amoebas of hypersurfaces have been intensively studied during the last years, the non-hypersurface case is barely understood so far. We investigate intersections of amoebas of \(n\) hypersurfaces in \((\mathbb{C}^*)^n\), which are genuine supersets of amoebas given by non-hypersurface varieties. Our main results are amoeba analogs of Bernstein's Theorem and Bézout's Theorem providing an upper bound for the number of connected components of such intersections. Moreover, we show that the order map for hypersurface amoebas can be generalized in a natural way to intersections of amoebas. We show that, analogous to the case of amoebas of hypersurfaces, the restriction of this generalized order map to a single connected component is still \(1\)-to-\(1\).
Les amibes sont la projection de variétés algébriques complexes par la fonction Log-module. Elles sont en liens avec de nombreuses branches des mathématiques. Alors que les amibes d'hypersurfaces ont été intensivement étudiées ces dernières années, on comprend encore très peu le cas de la codimension supérieur à \(1\). Nous nous intéressons à l'intersection de \(n\) amibes d'hypersurfaces dans (\(\mathbb{C}^*)^n\). C'est un sur-ensemble strict de l'amibe de l'intersections des \(n\) hypersurfaces. Notre résultat principal est analogue aux Théorèmes de Berstein et de Bézout donnant une borne supérieure au nombre de composantes connexes de telles intersections. De plus, nous montrons que la fonction d'ordre d'amibes d'hypersurfaces peut être généralisée de manière naturelle à l'intersection d'amibes. Nous montrons que de manière analogue au cas d'amibes d'hypersurfaces la restriction de cette fonction d'ordre généralisée à une composante connexe est également injective.
A triple product formula for plane partitions derived from biorthogonal polynomials
by Shuhei Kamioka
A new triple product formulae for plane partitions with bounded size of parts is derived from a combinatorial interpretation of biorthogonal polynomials in terms of lattice paths. Biorthogonal polynomials which generalize the little \(q\)-Laguerre polynomials are introduced to derive a new triple product formula which recovers the classical generating function in a triple product by MacMahon and generalizes the trace-type generating functions in double products by Stanley and Gansner.
Une nouvelle formule pour des partitions planes donnée dans un produit triple est obtenue d'une interprétation combinatoire des polynômes biorthogonaux en termes de chemins sur le réseau carré. Des polynômes biorthogonaux qui généralisent les petits \(q\)-polynômes de Laguerre sont introduits pour obtenir une nouvelle formule qui généralise la fonction génératrice dans un triple produit établie par McMahon et les fonctions génératrice de traces dans des produits doubles établies par Stanley et Gansner.
Defining amplituhedra and Grassmann polytopes
by Steven Karp
The {\itshape totally nonnegative Grassmannian} \( Gr_{k,n}^{\ge 0}\) is the set of \(k\)-dimensional subspaces \(V\) of \(\mathbb{R}^n\) whose nonzero Plücker coordinates all have the same sign. In their study of scattering amplitudes in \(\mathcal{N}=4\) supersymmetric Yang-Mills theory, Arkani-Hamed and Trnka (2013) considered the image (called an {\itshape amplituhedron}) of \( Gr_{k,n}^{\ge 0}\) under a linear map \(Z:\mathbb{R}^n\to\mathbb{R}^{r}\), where \(k \le r\) and the \(r\times r\) minors of \(Z\) are all positive. One reason they required this positivity condition is to ensure that the map \( Gr_{k,n}^{\ge 0}\to Gr_{k,r}\) induced by \(Z\) is well defined, i.e.\ it takes every element of \( Gr_{k,n}^{\ge 0}\) to a \(k\)-dimensional subspace of \(\mathbb{R}^r\). Lam (2015) gave a sufficient condition for the induced map \( Gr_{k,n}^{\ge 0}\to Gr_{k,r}\) to be well defined, in which case he called the image a {\itshape Grassmann polytope}. (In the case \(k=1\), Grassmann polytopes are just polytopes, and amplituhedra are cyclic polytopes.) We give a necessary and sufficient condition for the induced map \( Gr_{k,n}^{\ge 0}\to Gr_{k,r}\) to be well defined, in terms of sign variation. Using previous work we presented at FPSAC 2015, we obtain an equivalent condition in terms of the \(r\times r\) minors of \(Z\) (assuming \(Z\) has rank \(r\)).
La {\itshape grassmannienne totalement non négative \( Gr_{k,n}^{\ge 0}\)} est l'ensemble des sous-espaces \(V\) de \(\mathbb{R}^n\) de dimension \(k\) dont les coordonnées plückeriennes non nulles ont toutes le même signe. Selon leur étude des amplitudes de diffusion dans la théorie supersymétrique \(\mathcal{N}=4\) de Yang-Mills, Arkani-Hamed et Trnka (2013) ont considéré l'image (appelée un {\itshape amplituèdre}) de \( Gr_{k,n}^{\ge 0}\) par une application linéaire \(Z:\mathbb{R}^n\to\mathbb{R}^r\), où \(k\le r\) et les mineurs de l'ordre \(r\) de \(Z\) sont tous positifs. Une des raisons pour lesquelles ils ont exigé cette condition de positivité est pour s'assurer que la carte \( Gr_{k,n}^{\ge 0}\to Gr_{k,r}\) induite par \(Z\) est bien définie, c'est à dire, elle prend tout élément de \( Gr_{k,n}^{\ge 0}\) à un sous-espace de \(\mathbb{R}^r\) de dimension \(k\). Lam (2015) a donné une condition suffisante pour que la carte induite \( Gr_{k,n}^{\ge 0}\to Gr_{k,r}\) soit bien définie, et dans ce cas, il a appelé l'image un {\itshape polytope de Grassmann}. (Dans le cas \(k=1\), les polytopes de Grassmann sont polytopes, et les amplituèdres sont polytopes cycliques.) Nous donnons une condition nécessaire et suffisante pour rendre la carte induite \( Gr_{k,n}^{\ge 0}\to Gr_{k,r}\) bien définie, en termes de variations de signe. En se basant sur un travail antérieur que nous avons présenté à SFCA 2015, nous obtenons une condition équivalente en termes des mineurs de l'ordre \(r\) de \(Z\) (en supposant que \(r\) est le rang de \(Z\)).
Total positivity for the Lagrangian Grassmannian
by Rachel Karpman
The positroid decomposition of the Grassmannian refines the well-known Schubert decomposition, and has a rich combinatorial structure. There are a number of interesting combinatorial posets which index positroid varieties, just as Young diagrams index Schubert varieties. In addition, Postnikov's boundary measurement map gives a family of parametrizations for each positroid variety. The domain of each parametrization is the space of edge weights of a weighted planar network. The positroid stratification of the Grassmannian provides an elementary example of Lusztig's theory of total nonnegativity for partial flag varieties, and has remarkable applications to particle physics. We generalize the combinatorics of positroid varieties to the Lagrangian Grassmannian, the moduli space of maximal isotropic subspaces with respect to a symplectic form.
La décomposition positroïde de la Grassmannienne raffine la décomposition bien connue par les variétés de Schubert. Plusieurs posets intéressants énumèrent les variétés positroïdes, tout comme les diagrammes de Young énumèrent les variétés de Schubert. Le fonction de mesure des bords (du à Postnikov) donne, de plus, une famille de paramétrages pour chaque variété positroïde. Un tel paramétrage a comme domaine de définition l'ensemble de poids des arêtes d'un réseau planaire pondéré. Cette décomposition fournit un exemple élémentaire de la théorie de Lusztig de la nonnégativité complète pour les variétés de drapeaux, ainsi que plusieurs applications remarquables à la physique des particules. Nous généralisons la combinatoire des variétés positroïdes à la grassmannienne lagrangienne, la variété des sous-espaces isotropes d'un espace vectoriel symplectique.
On q-integrals over order polytopes
by Jang Soo Kim and Dennis Stanton
A \(q\)-integral over an order polytope coming from a poset is interpreted as a generating function of linear extensions of the poset. As an application, the \(q\)-beta integral and a \(q\)-analog of Dirichlet's integral are computed. A combinatorial interpretation of a \(q\)-Selberg integral is also obtained.
Une \(q\)-intégrale sur un polytope provenant d'un poset est interprété comme une série génératrice d'extensions linéaires de la poset. En application, l'intégrale \(q\)-bêta et un \(q\)-analogue de l'intégrale de Dirichlet sont calculés. Une interprétation combinatoire de une intégrale \(q\)-Selberg est également obtenue.
Categorifying the tensor product of the Kirillov-Reshetikhin crystal \(B^{1,1}\) and a fundamental crystal
by Henry Kvinge and Monica Vazirani
We use Khovanov-Lauda-Rouquier (KLR) algebras to categorify a crystal isomorphism between a fundamental crystal and the tensor product of a Kirillov-Reshetikhin crystal and another fundamental crystal, all in affine type. The nodes of the Kirillov-Reshetikhin crystal correspond to a family of « trivial » modules. The nodes of the fundamental crystal correspond to simple modules of the corresponding cyclotomic KLR algebra. The crystal operators correspond to socle of restriction and behave compatibly with the rule for tensor product of crystal graphs.
Nous utilisons Khovanov-Lauda-Rouquier (KLR) algèbres à catègorifier un cristal isomorphisme entre un cristal fondamental et le produit tensoriel d'une Kirillov-Reshetikhin cristal et un autre cristal fondamentale, le tout dans le type affine. Les noeuds du cristal Kirillov-Reshetikhin correspondre à une famille de modules laquo; triviales ». Les noeuds du cristal fondamental correspondre à des modules simples du correspondant cyclotomique algèbre KLR. Les opérateurs de cristal correspondent à socle de la restriction et comporter la compatibilité avec la règle pour le produit de tenseur des graphes de cristal.
Order Filter Model for Minuscule Plucker Relations
by David Lax
The Plücker relations which define the Grassmann manifolds as projective varieties are well known. Grassmann manifolds are examples of minuscule flag manifolds. We study the generalized Plücker relations for minuscule flag manifolds independent of Lie type. To do this we combinatorially model the Plücker coordinates based on Wildberger's construction of minuscule Lie algebra representations; it uses the colored partially ordered sets known as minuscule posets. We obtain, uniformly across Lie type, descriptions of the Plücker relations of « extreme weight ». We show that these are « supported » by « double-tailed diamond » sublattices of minuscule lattices. From this, we obtain a complete set of Plücker relations for the exceptional minuscule flag manifolds. These Plücker relations are straightening laws for their coordinate rings.
Les relations de Plücker qui définissent les variétés de Grassmann comme variétés projectifs sont bien connus. Les variétés de Grassmann sont des exemples de variétés de drapeaux minuscules. Nous étudions les relations de Plücker généralisées pour variétés de drapeaux minuscules indépendantes de type. Pour ceci, nous créons une modélisation des coordonnées de Plücker basée sur la construction de Wildberger des représentations minuscules d'algèbres de Lie; elle utilise les ensembles ordonnés et colorés qu'on appelle « posets minuscules ». à travers ce modèl, nous obtenons une description uniforme des relations de Plücker de « poids extrêmes ». Nous montrons que ces relations sont supportés par un sous-réseau des réseaux minuscules . De cette façon, nous obtenons un ensemble complet de relations de Plücker pour les cas de types exceptionnels. Ces relations de Plücker sont des « lois de redressage » pour leurs anneaux coordonnées.
Combinatorial description of the cohomology of the affine flag variety
by Seungjin Lee
We construct the affine version of the Fomin-Kirillov algebra, called the affine FK algebra, to investigate the combinatorics of affine Schubert calculus for type \(A\). We introduce Murnaghan-Nakayama elements and Dunkl elements in the affine FK algebra. We show that they are commutative as Bruhat operators, and the commutative algebra generated by these operators is isomorphic to the cohomology of the affine flag variety. As a byproduct, we obtain Murnaghan-Nakayama rules both for the affine Schubert polynomials and affine Stanley symmetric functions. This enable us to express \(k\)-Schur functions in terms of power sum symmetric functions. We also provide the definition of the affine Schubert polynomials, polynomial representatives of the Schubert basis in the cohomology of the affine flag variety.
Nous construisons la version affine de l'algèbre Fomin-Kirillov, appelé l'algèbre FK affine, pour enquêter sur la combinatoire du calcul de Schubert affine pour le type \(A\). Nous introduisons des éléments Murnaghan-Nakayama et éléments de Dunkl dans l'algèbre FK affine. Nous montrons qu'ils sont commutative comme opérateurs Bruhat, et l'algèbre commutative généré par ces opérateurs est isomorphe à la cohomologie de la variété affine du pavillon. En tant que sous-produit, on obtient règles de Murnaghan-Nakayama tant pour les polynômes de Schubert affines et les fonctions symétriques de Stanley affines. Cela nous permet d'exprimer des fonctions \(k\) -Schur en termes de fonctions symétriques puissance de somme. Nous fournissons également la définition de les polynômes de Schubert affines, des représentants polynômes de la base Schubert dans la cohomologie de la variété affine du pavillon.
\(GL(n, q)\)-analogues of factorization problems in the symmetric group
by Joel Lewis and Alejandro Morales
We consider \(GL_n(\mathbf{F}_q)\)-analogues of certain factorization problems in the symmetric group \(\mathfrak{S}_n\): rather than counting factorizations of the long cycle \((1,2,\ldots,n)\) given the number of cycles of each factor, we count factorizations of a regular elliptic element given the fixed space dimension of each factor. We show that, as in \(\mathfrak{S}_n\), the generating function counting these factorizations has attractive coefficients after an appropriate change of basis. Our work generalizes several recent results on factorizations in \(GL_n(\mathbf{F}_q)\) and also uses a character-based approach. We end with an asymptotic application and some questions.
Nous considérons \(GL_n(\mathbf{F}_q)\)-analogues de certains problèmes de factorisation dans le groupe symétrique \(\mathfrak{S}_n\): plutôt que de compter factorisations d'un grand cycle \((1,2,\ldots,n)\) étant donné le nombre de cycles de chaque facteur, nous comptons factorisations de un élément elliptique régulière donné la dimension de l'espace fixe de chaque facteur. Nous montrons que, comme dans \(\mathfrak{S}_n\), la fonction génératrice de ces factorisations a des coefficients attirants après un changement de base. Notre travail généralise plusieurs résultats récents sur factorisations dans \(GL_n(\mathbf{F}_q)\) et utilise une approche basée sur les caractères. Nous terminons avec une application asymptotique et des questions.
A dual approach to structure constants for K-theory
by Huilan Li, Jennifer Morse and Pat Shields
The problem of computing products of Schubert classes in the cohomology ring can be formulated as the problem of expanding skew Schur polynomial into the basis of ordinary Schur polynomials. We reformulate the problem of computing the structure constants of the Grothendieck ring of a Grassmannian variety with respect to its basis of Schubert structure sheaves in a similar way; we address the problem of expanding the generating functions for skew reverse-plane partitions into the basis of polynomials which are Hall-dual to stable Grothendieck polynomials. From this point of view, we produce a chain of bijections leading to Buch's \(K\)-theoretic Littlewood-Richardson rule.
Le calcul des produits de classes de Schubert dans l'anneau de cohomologie correspond dans le langage des fonctions symétriques au développement des polynômes de Schur gauches dans la base des polynômes de Schur. Nous reformulons de façon similaire le calcul des constantes de structure de l'anneau de Grothendieck d'une variété grassmannienne dans la base des faisceaux de structure de Schubert; nous étudions le problème du développement des fonctions génératrices des partitions planes inversée gauches dans une base de polynômes duaux aux polynômes de Grothendieck stables. De cette reformulation s'ensuit une séquence de bijections qui permet de redériver la règle de Littlewood-Richardson en \(K\)-théorie obtenue par Buch.
A combinatorial analysis of Severi degrees
by Fu Liu
Based on results by Brugallé and Mikhalkin, Fomin and Mikhalkin give formulas for computing classical Severi degrees \(N^{d, \delta}\) using long-edge graphs. In 2012, Block, Colley and Kennedy considered the logarithmic version of a special function associated to long-edge graphs which appeared in Fomin-Mikhalkin's formula, and conjectured it to be linear. They have since proved their conjecture. At the same time, motivated by their conjecture, we consider a special multivariate function associated to long-edge graphs that generalizes their function. The main result of this paper is that the multivariate function we define is always linear. The first application of our linearity result is that by applying it to classical Severi degrees, we recover quadraticity of \(Q^{d, \delta}\) and a bound \(\delta\) for the threshold of polynomiality of \(N^{d, \delta}.\) Next, in joint work with Osserman, we apply the linearity result to a special family of toric surfaces and obtain universal polynomial results having connections to the Göttsche-Yau-Zaslow formula. As a result, we provide combinatorial formulas for the two unidentified power series \(B_1(q)\) and \(B_2(q)\) appearing in the Göttsche-Yau-Zaslow formula. The proof of our linearity result is completely combinatorial. We define \(\tau\)-graphs which generalize long-edge graphs, and a closely related family of combinatorial objects we call \((\tau, n)\)-words. By introducing height functions and a concept of irreducibility, we describe ways to decompose certain families of \((\tau, n)\)-words into irreducible words, which leads to the desired results.
Basé sur les travaux de Brugallé et Mikhalkin, Fomin et Mikhalkin ont donné des formules pour calculer les degrés de Severi classiques $N^{d, \delta}$ en utilisant des graphes aux arêtes longues. En 2012, Block, Colley et Kennedy ont considéré la version logarithmique d'une fonction spéciale associée aux graphes aux arêtes longues qui apparait dans la formule de Fomin et Mikhalkin, et ont conjecturé qu'elle est linéaire. Ils ont depuis montré leur conjecture. Au même moment, motivés par leur conjecture, nous avons considéré une fonction spéciale multivariée associée aux graphes aux arêtes longues qui généralise leur fonction. Le résultat principal de cet article est que la fonction multivariée que nous définissons est toujours linéaire. La première application de notre résultat de linéarité est qu'en l'appliquant aux degrés de Severi classiques, nous retrouvons le fait que \(Q^{d, \delta}\) est quadratique et une borne \(\delta\) pour le seuil de polynomialité de \(N^{d, \delta}\). Ensuite, dans un travail en commun avec Osserman, nous appliquons le résultat de linéarité pour une famille particulière de surfaces toriques et obtenons des résultats sur les polynômes universels ayant des connexions avec la formule de Göttsche, Yau et Zaslow. En conséquence, nous obtenons des formules combinatoires pour deux séries formelles \(B_1(q)\) et \(B_2(q)\) non-identifiées apparaissant dans la formule de Göttsche, Yau et Zaslow. La preuve de notre résultat de linéarité est purement combinatoire. Nous définissons des \(\tau\)-graphes qui généralisent les graphes aux arêtes longues, une famille étroitement liée d'objets combinatoires que nous appelons les \((\tau, n)\)-mots. En introduisant des fonctions de hauteur et un concept d'irreductibilité, nous décrivons des façons de décomposer certaines familles de \((\tau, n)\)-mots en mots irreductibles, ce qui nous conduit aux résultats souhaités.
Scheduling Problems and Generalized Graph Coloring
by John Machacek
We define a new type of vertex coloring which generalizes vertex coloring in graphs, hypergraphs, and simplicial complexes. To this coloring there is an associated symmetric function in noncommuting variables for which we give a deletion-contraction formula. In the case of graphs our symmetric function in noncommuting variables agrees with the chromatic symmetric function in noncommuting variables of Gebhard and Sagan. Our vertex coloring is a special case of the scheduling problems defined by Breuer and Klivans. We show how the deletion-contraction law can be applied to scheduling problems.
Nous définissons un nouveau type de coloration des sommets qui généralise les colorations dans les graphes, hypergraphes et complexes simpliciaux. Pour cette coloration, nous associons une fonction symétrique en variables non commutatives, pour laquelle nous donnons une formule de délétion - contraction. Dans le cas des graphes, notre fonction symétrique en variables non commutatives est en accord avec celle de Gebhard et Sagan. Notre coloration des sommets est un cas particulier des problémes d'ordonnancement définis par Breuer et Klivans; nous démontrons comment la loi de délétion - contraction peut être appliquée à ces problémes.
Tropical Ideals
by Diane Maclagan and Felipe Rincón
We introduce and study a special class of ideals over the semiring of tropical polynomials, which we call tropical ideals, with the goal of developing a useful and solid algebraic foundation for tropical geometry. We explore their rich combinatorial structure, and prove that they satisfy numerous properties analogous to classical ideals.
Nous introduisons et étudions une classe particulière d'idéals sur le demi-anneau des polynômes tropicaux, que nous appelons idéals tropicaux, dans la perspective de développer des fondations solides et utiles pour la géométrie tropicale. Nous explorons leur riche structure combinatoire, et nous prouvons qu'ils satisfont de nombreuses propriétés analogues à celles des idéaux classiques.
Rhombic alternative tableaux, assemblées of permutations, and the ASEP
by Olya Mandelshtam and Xavier Viennot
In this paper, we introduce the rhombic alternative tableaux, whose weight generating functions provide combinatorial formulae to compute the steady state probabilities of the two-species ASEP. In the ASEP, there are two species of particles, one heavy and one light, on a one-dimensional finite lattice with open boundaries, and the parameters \(\alpha\), \(\beta\), and \(q\) describe the hopping probabilities. The rhombic alternative tableaux are enumerated by the Lah numbers, which also enumerate certain assemblées of permutations. We describe a bijection between the rhombic alternative tableaux and these assemblées. We also provide an insertion algorithm that gives a weight generating function for the assembées. Combined, these results give a bijective proof for the weight generating function for the rhombic alternative tableaux.
Dans cet article, nous introduisons la notion de tableaux alternatifs rhomboïdaux, dont la série génératrice valuée permet de donner une formule combinatoire pour calculer les probabilités stationnaires du modèle ASEP avec deux types de particules. Dans ce modèle, il y a deux types de particules, lourde et légères, sur une bande finie avec extrémités ouvertes, et les paramètres \(\alpha\), \(\beta\) et \(q\) décrivent les probabilités de saut. Les tableaux alternatifs romboïdaux sont énumérés par les nombres de Lah, qui aussi énumèrent les assemblées de permutations. Nous décrivons une bijection entre ces tableaux et ces assemblées. Nous aussi décrivons une algorithme d'insertion qui donne la série génératrice valuée pour les assemblées. Combinée, ces resultats donnent une preuve bijective pour la série génératrice valuée pour les tableaux alternatifs rhomboïdaux.
Compatibility fans realizing graphical nested complexes
by Thibault Manneville and Vincent Pilaud
Graph associahedra are polytopes realizing the nested complex \(\mathcal{N}(mathrm{G})\) on connected subgraphs of a graph \(mathrm{G}\). While all known explicit constructions produce polytopes with the same normal fan, the great variety of fan realizations of classical associahedra and the analogy between finite type cluster complexes and nested complexes incited us to transpose S. Fomin and A. Zelevinsky's construction of compatibility fans for generalized associahedra (2003) to graph associahedra. Using a compatibility degree, we construct one fan realization of \(\mathcal{N}(mathrm{G})\) for each of its facets. Specifying \(mathrm{G}\) to paths and cycles, we recover a construction by F. Santos for classical associahedra (2011) and extend F. Chapoton, S. Fomin and A. Zelevinsky's construction (2002) for type \(B\) and \(C\) generalized associahedra.
Les associaèdres de graphe sont des réalisations polytopales du complexe emboîté \(\mathcal{N}(mathrm{G})\) des sous-graphes connexes d'un graphe \(mathrm{G}\). Si toutes les constructions explicites connues produisent des polytopes avec le même éventail normal, la pléthore de réalisations de l'associaèdre classique et l'analogie entre complexes amassés de type fini et complexes emboîtés nous ont incités {à} transposer la construction des associaèdres généralisés comme éventails de compatibilité par S. Fomin et A. Zelewinsky (2003) aux associaèdres de graphe. Grâce à un degré de compatibilité, nous construisons un éventail simplicial réalisant \(\mathcal{N}(mathrm{G})\) pour chacune de ses facettes. Quand \(mathrm{G}\) est un chemin ou un cycle, nous retrouvons une construction de F. Santos de l'associaèdre classique (2011) et étendons celle de F. Chapoton, S. Fomin et A. Zelewinsky (2002) pour les associaèdres généralisés de type \(B\) et \(C\).
Rectangular Young tableaux and the Jacobi ensemble
by Philippe Marchal
It has been shown by Pittel and Romik that the random surface associated with a large rectangular Young tableau converges to a deterministic limit. We study the fluctuations from this limit along the edges of the rectangle. We show that in the corner, these fluctuations are gaussian whereas, away from the corner and when the rectangle is a square, the fluctuations are given by the Tracy-Widom distribution. Our method is based on a connection with the Jacobi ensemble.
Pittel et Romik ont établi l'existence d'une forme limite pour la surface aléatoire associée à un tableau de Young rectangulaire de grande taille. Nous étudions les fluctuations autour de cette limite le long du bord du rectangle. Nous montrons que ces fluctuations sont gaussiennes en les coins et, dans le cas où le rectangle est un carré, données par la loi de Tracy-Widom sur les bords. Notre méthode s'appuie sur un lien avec l'ensemble de Jacobi.
Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II
by David Maslen, Daniel Rockmore and Sarah Wolff
We present a general diagrammatic approach to the construction of efficient algorithms for computing the Fourier transform of a function on a finite group. By extending work which connects Bratteli diagrams to the construction of Fast Fourier Transform algorithms we make explicit use of the path algebra connection and work in the setting of quivers. In this setting the complexity of an algorithm for computing a Fourier transform reduces to path counting in the Bratelli diagram, and we generalize Stanley's work on differential posets to provide such counts. Our methods give improved upper bounds for computing the Fourier transform for the general linear groups over finite fields, the classical Weyl groups, and homogeneous spaces of finite groups.
Nous présentons une approche schématique générale à la construction d'algorithmes efficaces pour le calcul de la transformée de Fourier d'une fonction sur un groupe fini. En étendant le travail qui relie diagrammes Bratelli à la construction d`algorithmes efficaces nous faisons usage explicite de la connexion de l`algèbre des chemins et le travail dans le cadre de carquois. Dans ce cadre la complexité d'un algorithme de calcul de transformée de Fourier réduit à des comptages de certains sous-carquois du diagramme Bratelli. Nos méthodes donnent améliorées limites supérieures pour le calcul de la transformée de Fourier pour les groupes linéaires généraux sur les corps finis, les groupes de Weyl classiques, et des espaces homogènes de groupes finis.
Asymptotics of lattice walks via analytic combinatorics in several variables
by Stephen Melczer and Mark C. Wilson
We consider the enumeration of walks on the two-dimensional non-negative integer lattice with steps defined by a finite set \(\mathcal{S} \subseteq \{\pm1,0\}^2\). Up to isomorphism there are 79 unique two-dimensional models to consider, and previous work in this area has used the kernel method, along with a rigorous computer algebra approach, to show that 23 of the 79 models admit D-finite generating functions. In 2009, Bostan and Kauers used Padé-Hermite approximants to guess differential equations which these 23 generating functions satisfy, in the process guessing asymptotics of their coefficient sequences. In this article we provide, for the first time, a complete rigorous verification of these guesses. Our technique is to use the kernel method to express 19 of the 23 generating functions as diagonals of tri-variate rational functions and apply the methods of analytic combinatorics in several variables (the remaining 4 models have algebraic generating functions and can thus be handled by univariate techniques). This approach also shows the link between combinatorial properties of the models and features of its asymptotics such as asymptotic and polynomial growth factors. In addition, we give expressions for the number of walks returning to the \(x\)-axis, the \(y\)-axis, and the origin, proving recently conjectured asymptotics of Bostan, Chyzak, van Hoeij, Kauers, and Pech.
Les travaux antérieurs dans ce domaine ont utilisé la méthode du noyau, jointe {à} une approche de calcul formel rigoureux, pour montrer que 23 des 79 modèles admettent des fonctions génératrices D-finies. En 2009, Bostan et Kauers ont utilisé des approximants de Padé-Hermite pour deviner d'abord des équations différentielles que ces 23 fonctions génératrices satisfont, puis le comportement asymptotique de leurs suites de coefficients. Dans cet article, nous fournissons, pour la première fois, une vérification rigoureuse complète de ces résultats conjecturés. Notre technique consiste {à} utiliser la méthode du noyau pour exprimer 19 des 23 fonctions génératrices comme diagonales de fonctions rationnelles trivariées et {à} leur appliquer les méthodes de combinatoire analytique en plusieurs variables (les 4 modèles restants ont des fonctions génératrices algébriques et peuvent donc être traités par des techniques du monde univarié). Cette approche montre également le lien entre les propriétés combinatoires des modèles et leurs caractéristiques asymptotiques. De plus, nous donnons des expressions pour le nombre de marches revenant {à} l'axe des x, {à} l'axe des y, ou {à} l'origine, prouvant des asymptotiques récemment conjecturées par Bostan, Chyzak, van Hoeij, Kauers et Pech.
Maximal green sequences for arbitrary triangulations of marked surfaces
by Matthew Mills
In general, the existence of a maximal green sequence is not mutation invariant. In this paper we show that it is in fact mutation invariant for cluster quivers associated to most marked surfaces. We develop a procedure to find maximal green sequences for cluster quivers associated to an arbitrary triangulation of closed higher genus marked surfaces with at least two punctures. As a corollary, it follows that any triangulation of a marked surface with at least one boundary component has a maximal green sequence.
En général, l'existence d'une suite verte maximale n'est pas invariante par mutation. Dans cet article, nous montrons qu'elle est invariante par mutation pour les carquois amassés associés à la plupart des surfaces marquées. Nous développons une méthode permettant de trouver des suites vertes maximales pour les carquois amassés associés à une triangulation arbitraire d'une surface marquée fermée de genre supérieur avec au moins deux ponctions. Nous obtenons comme corollaire que toute triangulation d'une surface marquée avec au moins une composante de bord admet une suite verte maximale.
Some results on counting roots of polynomials and the Sylvester resultant
by Michael Monagan and Baris Tuncer
We present two results, the first on the distribution of the roots of a polynomial over the ring of integers modulo \(n\) and the second on the distribution of the roots of the Sylvester resultant of two multivariate polynomials. The second result has application to polynomial GCD computation and solving polynomial diophantine equations.
Nous présentons deux résultats: le premier concerne la distribution des racines d'un polynôme sur l'anneau des entiers modulo \(n\) et le deuxième concerne la distribution des racines du déterminant de Sylvester de deux polynômes multivariés. Ceci est utile pour le calcul de PGCD et la résolution des équations diophantiennes polynomiales.
Hook formulas for skew shapes
by Alejandro Morales, Igor Pak and Greta Panova
The celebrated hook-length formula gives a product formula for the number of standard Young tableaux of a straight shape. In 2014, Naruse announced a more general formula for the number of standard Young tableaux of skew shapes as a positive sum over excited diagrams of products of hook-lengths. We give two \(q\)-analogues of Naruse's formula for the skew Schur functions and for counting reverse plane partitions of skew shapes. We also apply our results to border strip shapes and their generalizations.
La formule des équerres donne une formule de produit pour le nombre de tableaux standard de forme droite. En 2014, Naruse a annoncé une formule pour le nombre de tableaux standard de forme gauche comme une somme positive sur les {\em diagrammes excitées} de produits des équerres. Nous donnons deux \(q\)-analogues de la formule pour les tableaux semistandard et les partitions planes inversées. Nous appliquons aussi nos résultats aux diagrammes rubans et ses généralisations.
The twist for positroids
by Greg Muller and David Speyer
There are two reasonable ways to put a cluster structure on a positroid variety. In one, the initial seed is a set of Plücker coordinates. In the other, the initial seed consists of certain monomials in the edge weights of a plabic graph. We will describe an automorphism of the positroid variety, the twist, which takes one to the other. For the big positroid cell, this was already done by Marsh and Scott; we generalize their results to all positroid varieties. This also provides an inversion of the boundary measurement map which is more general than Talaska's, in that it works for all reduced plabic graphs rather than just Le-diagrams. This is the analogue for positroid varieties of the twist map of Berenstein, Fomin and Zelevinsky for double Bruhat cells. Our construction involved the combinatorics of dimer configurations on bipartite planar graphs.
Deux méthodes sont bien connues pour munir d'une structure amassée une variété positroïde. La première utilise comme graine initiale un ensemble de coordonnées plückeriennes. Dans la seconde, la graine initiale est composée de certains monômes dans les poids des arêtes d'un graphe planaire bicolore. Nous décrivons un automorphisme de la variété positroïde, le torsion, qui prend l'une à l'autre. Pour la grosse cellule positroïde, cela a déjà été fait par Marsh et Scott; nous généralisons leurs résultats à toute variété positroïde. Notre automorphisme fournit aussi une application inverse de la fonction de mesure des bords, plus générale que celle de Talaska : la nôtre s'applique a tous les graphes planaires bicolores réduits, plutôt que seulement les Le-diagrammes. Notre construction est l'analogue pour les variétés positroïdes de la fonction de torsion de Berenstein-Fomin-Zelevinsky pour les doubles cellules de Bruhat. Notre approche utilise la combinatoire des configurations de dimères sur les graphes planaires bicolores.
Symmetric Chain Decompositions and the Strong Sperner Property for Noncrossing Partition Lattices
by Henri Mühle
We prove that the noncrossing partition lattices associated with the complex reflection groups \(G(d,d,n)\) for \(d,n\geq 2\) admit a decomposition into saturated chains that are symmetric about the middle ranks. A consequence of this result is that these lattices have the strong Sperner property, which asserts that the cardinality of the union of the \(k\) largest antichains does not exceed the sum of the \(k\) largest ranks for all \(k\leq n\). Subsequently, we use a computer to complete the proof that any noncrossing partition lattice associated with a well-generated complex reflection group is strongly Sperner, thus affirmatively answering a special case of a question of D. Armstrong. This was previously established only for the Coxeter groups of type \(A\) and \(B\).
Nous prouvons que les treillis des partitions non-croisées associés aux groupes de réflexion complèxe \(G(d,d,n)\), o{ù} \(d,n\geq 2\), admettent une décomposition en chaînes saturées qui sont symétriques par rapport au rang moyen. Une conséquence de ce résultat est que ces treillis ont la propriété forte de Sperner qui affirme que le cardinal de l'union des \(k\) antichaînes les plus grands ne dépasse pas la somme des \(k\) rangs les plus grands pour tout \(k\leq n\). Ensuite, nous utilisons un ordinateur pour compléter la preuve que chaque treillis des partitions non-croisées associé {à} un groupe de réflexion complèxe bien engendré a la propriété forte de Sperner. Ce résultat résout un cas spécial d'un question de D. Armstrong, et avait été établi auparavant seulement pour les groupes de Coxeter de type \(A\) et \(B\).
Yang-Baxter basis of Hecke algebra and Casselman's problem (extended abstract)
by Maki Nakasuji and Hiroshi Naruse
We generalize the definition of Yang-Baxter basis of type \(A\) Hecke algebra introduced by A.Lascoux, B.Leclerc and J.Y.Thibon (Letters in Math. Phys., 40 (1997), 75-90) to all the Lie types and prove their duality. As an application we give a solution to Casselman's problem on Iwahori fixed vectors of principal series representation of \(p\)-adic groups.
Nous généralisons la définition de la base de l'algèbre de Hecke de Yang-Baxter de type \(A\) introduit par A.Lascoux, B.Leclerc and J.Y.Thibon (Letters in Math. Phys., 40 (1997), 75-90) à tous les types de Lie et prouvons la dualité. Comme application nous donnons une solution du problème de Casselman sur les vecteurs fixés par le sous-groupe d'Iwahori de la série principale des groupes \(p\)-adiques.
Almost simplicial polytopes: the lower and upper bound theorems
by Eran Nevo, Guillermo Pineda-Villavicencio, Julien Ugon and David Yost
This is an extended abstract of the full version. We study \(n\)-vertex \(d\)-dimensional polytopes with at most one nonsimplex facet with, say, \(d+s\) vertices, called {\it almost simplicial polytopes}. We provide tight lower and upper bounds for the face numbers of these polytopes as functions of \(d,n\) and \(s\), thus generalizing the classical Lower Bound Theorem by Barnette and Upper Bound Theorem by McMullen, which treat the case \(s=0\). We characterize the minimizers and provide examples of maximizers, for any \(d\).
Ceci est un résumé étendu de la version complète. Nous étudions \(n\)-vertex \(d\)-polytopes avec au plus une facette nonsimplex avec, par exemple, les sommets de \(d+s\), appelés {\ it polytopes presque simpliciaux}. Nous fournissons des théorèmes liés serré inférieures et supérieures pour ces polytopes que les fonctions de \(d,n\) et \(s\), généralisant ainsi le classique théorème borne inférieure Barnette et Haute Théorème Lié par McMullen, qui traitent le cas de \(s=0\). Nous caractérisons les minimiseurs et fournir des exemples de maximiseurs, pour tout \(d\).
An equivalence of multistatistics on permutations
by Arthur Nunge
We prove a conjecture of J.-C. Novelli, J.-Y. Thibon, and L. K. Williams (2010) about an equivalence of two triples of statistics on permutations. To prove this conjecture, we construct a bijection through different combinatorial objects, starting with a Catalan based object related to the PASEP.
Nous prouvons une conjecture de J.-C. Novelli, J.-Y. Thibon et L. K. Williams de l'article (2010) à propos d'une équivalence de statistiques sur les permutations. Pour prouver cette conjecture, nous construisons une bijection passant par différents objets combinatoires en commençant par un objet de type Catalan relié au PASEP.
Links in the complex of weakly separated collections(Extended Abstract)
by Suho Oh and David Speyer
Plabic graphs are combinatorial objects used to study the totally nonnegative Grassmannian. Faces of plabic graphs are labeled by \(k\)-element sets of positive integers, and a collection of such \(k\)-element sets are the face labels of a plabic graph if that collection forms a maximal weakly separated collection. There are moves that one can apply to plabic graphs, and thus to maximal weakly separated collections, analogous to mutations of seeds in cluster algebras. In this short note, we show if two maximal weakly separated collections can be mutated from one to another, then one can do so while freezing the face labels they have in common. In particular, this provides a new, and we think simpler, proof of Postnikov's result that any two reduced plabic graphs with the same decorated permutations can be mutated to each other.
Les graphes « plabic » sont des objets combinatoires utilisés pour l'étude de la Grassmannienne totalement positive. Les faces des graphes « plabic » sont étiquetées par des ensembles de \(k\) entiers positifs et une collection de tels ensembles correspond à un graphe « plabic » si cette collection est une collection maximale faiblement séparée. Certaines opérations peuvent être effectuées sur les graphes « plabic », et donc sur les collections faiblement séparées, analogues aux mutations de graines dans les algèbres amassées. Dans cet article, nous montrons que si deux collections maximales faiblement séparées peuvent être transformées l'une en l'autre par ces opérations, alors il est possible de le faire en gelant les étiquettes faciales qui sont communes aux deux collections. En particulier, ceci fournit une nouvelle (et de notre point de vue plus simple) preuve du résultat de Postnikov qui affirme que deux graphes « plabic » réduits avec les mêmes permutations faciales peuvent être transformés l'un en l'autre par ces opérations.
Counting connected graphs with large excess
by Élie de Panafieu
We enumerate the connected graphs that contain a linear number of edges with respect to the number of vertices. So far, only the first term of the asymptotics was known. Using analytic combinatorics, i.e. generating function manipulations, we derive the complete asymptotic expansion.
Nous énumérons les graphes connexes dont le nombre d'arêtes est proportionnel au nombre de sommets. Jusqu'ici, seul le terme dominant de l'asymptotique était connu. En employant la combinatoire analytique, c'est-à-dire des manipulations de séries génératrices, nous obtenons l'expansion asymtptotique complète.
A two-sided analogue of the Coxeter complex
by Kyle Petersen
For any Coxeter system \((W,S)\) of rank \(n\), we introduce an abstract boolean complex (simplicial poset) of dimension \(2n-1\) which contains the Coxeter complex as a relative subcomplex. Faces are indexed by triples \((J,w,K)\), where \(J\) and \(K\) are subsets of the set \(S\) of simple generators, and \(w\) is a minimal length representative for the double parabolic coset \(W_J w W_K\). There is exactly one maximal face for each element of the group \(W\). The complex is shellable and thin, which implies the complex is a sphere for the finite Coxeter groups. In this case, a natural refinement of the \(h\)-polynomial is given by the « two-sided » \(W\)-Eulerian polynomial, i.e., the generating function for the joint distribution of left and right descents in \(W\).
Pour tout système de Coxeter \((W, S)\) de rang \(n\), nous introduisons un complexe booléen (poset simplicial) de dimension \(2n-1\) qui contient le complexe de Coxeter comme sous-complexe relatif. Les faces sont indexées par les triplets \((J, w, K)\), où \(J\) et \(K\) sont des sous-ensembles de l'ensemble \(S\) de générateurs simples, et \(w\) est un représentant de la longueur minimale pour le double coset parabolique \(W_J w W_K\). Il y a exactement une face maximale pour chaque élément du groupe \(W\). Le complexe est épluchanble et maigre, ce qui implique que le complexe est une sphère pour les groupes de Coxeter finis. Dans ce cas, un raffinement naturel du \(h\)-polynomial est donné par le polynôme \(W\)-Eulérien laquo; deux côtés », à savoir, la fonction génératrice pour la distribution conjointe des descentes gauche et à droite dans \(W\).
Brick polytopes, lattices and Hopf algebras
by Vincent Pilaud
Generalizing the connection between the classes of the sylvester congruence and the binary trees, we show that the classes of the congruence of the weak order on \(\mathfrak{S}_n\) defined as the transitive closure of the rewriting rule \({U ac V_1 b_1 \cdots V_k b_k W \equiv^k U ca V_1 b_1 \cdots V_k b_k W}\), for letters \({a < b_1, \dots, b_k < c}\) and words \(U, V_1, \dots, V_k, W\) on \([n]\), are in bijection with acyclic \(k\)-triangulations of the \((n+2k)\)-gon, or equivalently with acyclic pipe dreams for the permutation \((1, \dots, k, n+k, \dots, k+1, n+k+1, \dots, n+2k)\). It enables us to transport the known lattice and Hopf algebra structures from the congruence classes of \(\equiv^k\) to these acyclic pipe dreams, and to describe the product and coproduct of this algebra in terms of pipe dreams. Moreover, it shows that the fan obtained by coarsening the Coxeter fan according to the classes of \(\equiv^k\) is the normal fan of the corresponding brick polytope.
Généralisant la connexion entre les classes de congruence sylvestre et les arbres binaires, nous montrons que les classes de la congruence de l'ordre faible sur \(\mathfrak{S}_n\) définie comme cloture transitive de la règle de réécriture \({U ac V_1 b_1 \cdots V_k b_k W \equiv^k U ca V_1 b_1 \cdots V_k b_k W}\), pour des lettres \({a < b_1, \dots, b_k < c}\) et des mots \(U, V_1, \dots, V_k, W\) sur \([n]\), sont en bijection avec les \(k\)-triangulations acycliques d'un \((n+2k)\)-gone, ou de manière équivalente avec des arrangements de tuyaux acycliques pour la permutation \((1, \dots, k, n+k, \dots, k+1, n+k+1, \dots, n+2k)\). Cela nous permet de transporter les structures connues de treillis et d'algèbre de Hopf des classes de congruence de \(\equiv^k\) à ces arrangements de tuyaux acycliques, et de décrire le produit et le coproduit de cette algèbre en termes d'arrangements de tuyaux. Par ailleurs, cela montre que l'éventail obtenu en recollant les chambres de l'éventail de Coxeter en fonction des classes de \(\equiv^k\) est l'éventail normal du polytope de briques correspondant.
Decomposition of the product of a monomial and a Demazure atom
by Anna Yang Pun
We prove that the product of a monomial and a Demazure atom is a positive sum of Demazure atoms combinatorially. This result proves one particular case in a conjecture which provides an approach to a combinatorial proof of Schubert positivity property.
Nous montrons combinatoirement que le produit d'un monôme et d'un atome de Demazure est une somme positive d'atomes de Demazure. Ce résultat montre un cas particulier d'une conjecture qui fournit une approche combinatoire de la propriété de positivité de Schubert.
Staircase diagrams and the enumeration of smooth Schubert varieties
by Edward Richmond and William Slofstra
In this extended abstract, we give a complete description and enumeration of smooth and rationally smooth Schubert varieties in finite type. In particular, we show that rationally smooth Schubert varieties are in bijection with a new combinatorial data structure called staircase diagrams.
Dans ce résumé étendu, nous donnons une description complète et le dénombrement de variétés lisses et rationnellement lisses Schubert type fini. Dans particulier, nous montrons que les variétés de Schubert rationnellement lisses sont en bijection avec une nouvelle structure de données combinatoire appelé escalier diagrammes.
A noncommutative geometric LR rule
by Edward Richmond, Vasu Tewari and Steph van Willigenburg
The geometric Littlewood-Richardson (LR) rule is a combinatorial algorithm for computing LR coefficients derived from degenerating the Richardson variety into a union of Schubert varieties in the Grassmannian. Such rules were first given by Vakil and later generalized by Coskun. In this paper we give a noncommutative version of the geometric LR rule. As a consequence, we establish a geometric explanation for the positivity of noncommutative LR coefficients in certain cases.
La règle de Littlewood-Richardson (LR) géométrique est un algorithme combinatoire de calcul des coefficients de LR, conçu à partir de l'étude des dégénérations d'une variété de Richardson en variétés de Schubert, dans la Grassmannienne. Vakil a été le premier à donner une telle règle, et Coskun en a produit des généralisations. Dans cet article, nous donnons une version non-commutative de la règle de LR géométrique. Comme conséquence, nous obtenons une explication géométrique de la positivité de certains coefficients de LR non-commutatifs.
Symmetric Fundamental Expansions to Schur Positivity
by Austin Roberts
We consider families of quasisymmetric functions with the property that if a symmetric function \(f\) is a positive sum of functions in one of these families, then \(f\) is necessarily a positive sum of Schur functions. Furthermore, in each of the families studied, we give a combinatorial description of the Schur coefficients of \(f\). We organize six such families into a poset, where functions in higher families in the poset are always positive integer sums of functions in each of the lower families.
Nous considérons les familles de fonctions quasi-symétriques avec la propriété suivante: si une fonction symétrique \(f\) est une somme positive de fonctions dans une de ces familles, alors \(f\) est nécessairement une somme positive de fonctions de Schur. Nous considérons familles de fonctions quasisymmetric avec la propriété que si une fonction symétrique \(f\) est une somme positive de fonctions dans une de ces familles, alors \(f\) est nécessairement une somme positive de fonctions de Schur. En outre, dans chacune des familles étudiées, nous donnons une description combinatoire des coefficients de Schur de \(f\). Nous organisons six de ces familles dans un ensemble ordonné, où les fonctions des familles plus élevées dans le poset sont toujours des sommes d'entiers positifs de fonctions dans chacune des familles inférieurs.
Combinatorial descriptions of the crystal structure on certain PBW bases
by Ben Salisbury, Adam Schultze and Peter Tingley
Lusztig's theory of PBW bases gives a way to realize the crystal \(B(\infty)\) for any simple complex Lie algebra where the underlying set consists of Kostant partitions. In fact, there are many different such realizations, one for each reduced expression for the longest element of the Weyl group. There is an algorithm to calculate the actions of the crystal operators, but it can be quite complicated. For ADE types, we give conditions on the reduced expression which ensure that the corresponding crystal operators are given by simple combinatorial bracketing rules. We then give at least one reduced expression satisfying our conditions in every type except \(E_8\), and discuss the resulting combinatorics. Finally, we describe the relationship with more standard tableaux combinatorics in types \(A\) and \(D\).
La théorie de Lusztig de bases PBW donne un moyen de réaliser le cristal \(B(\infty)\) pour toute algèbre de Lie complexe-simple où l'ensemble sous-jacent est constitué de partitions Kostant. En fait, il existe de nombreuses réalisations différentes, une pour chaque expression réduite de l'élément le plus long du groupe de Weyl. Il existe un algorithme pour calculer les actions des opérateurs de cristal, mais elle peut être assez compliqué. Pour les types ADE, nous donnons des conditions sur l'expression réduite qui assurent que les opérateurs de cristal correspondants sont donnés par une simple règle de d'appariement combinatoire. Nous donnons ensuite au moins une expression réduite satisfaite nos conditions pour chaque type, sauf \(E_8\), et discutons la combinatoire résultant. Enfin, nous décrivons les relations avec la combinatoire de tableaux standards dans les types \(A\) et \(D\).
Relaxations of the matroid axioms I: Independence, Exchange and Circuits
by Jose Samper
Motivated by a question of Duval and Reiner about higher Laplacians of simplicial complexes, we describe various relaxations of the defining axioms of matroid theory to obtain larger classes of simplicial complexes that contain pure shifted simplicial complexes. The resulting classes retain some of the matroid properties and allow us to classify matroid properties according to the relevant axioms needed to prove them. We illustrate this by discussing Tutte polynomials. Furthermore, we extend a conjecture of Stanley on \(h\)-vectors and provide evidence to show that the extension is better suited than matroids to study the conjecture.
Motivé par une question de Duval et Reiner concernant les Laplaciens d'ordres supérieurs des complexes simpliciaux, nous décrivons certaines relaxations des axiomes de la théorie des matroïdes afin d'obtenir des familles plus grandes de complexes simpliciaux qui contiennent les complexes simpliciaux pures décalés. Les classes obtenues conservent certaines propriétés des matroïdes et nous permettent de classifier les propriétés des matroïdes selon les axiomes nécessaires pour les démontrer. Nous illustrons ceci à l'aide des polynômes de Tutte. De plus, nous étendons une conjecture de Stanley concernant les \(h\)-vecteurs et supportons l'énoncé par des preuves montrant que l'extension est mieux adaptée à la conjecture que les matroïdes.
Elliptic rook and file numbers
by Michael Schlosser and Meesue Yoo
In this work, we construct elliptic analogues of the rook numbers and file numbers by attaching elliptic weights to the cells in a board. We show that our elliptic rook and file numbers satisfy elliptic extensions of corresponding factorization theorems which in the classical case were established by Goldman, Joichi and White and by Garsia and Remmel in the file number case. This factorization theorem can be used to define elliptic analogues of various kinds of Stirling numbers of the first and second kind as well as Abel numbers. We also give analogous results for matchings of graphs, elliptically extending the result of Haglund and Remmel.
Dans cet article nous construisons des analogues elliptiques des nombres de tour (rook numbers) et des nombres de file (file numbers), en attachant des poids elliptiques aux cases d'un damier. Nous montrons que nos nombres elliptiques de tour et de file satisfont des extensions elliptiques des théorèmes de factorisation correspondants établis dans le cas classique par Goldman, Joichi et White, et par Garsia et Remmel dans le cas des nombres de file. Ce théorème de factorisation peut être utilisé pour définir des analogues elliptiques de différentes sortes des nombres de Stirling de première et de deuxième espèces, et des nombres d'Abel. Nous donnons également des résultats analogues pour les appariements de graphes, en étendant elliptiquement le résultat de Haglund et Remmel.
A Formula for the Möbius Function of the Permutation Poset Based on a Topological Decomposition
by Jason Smith
The poset \(\mathcal{P}\) of all permutations ordered by pattern containment is a fundamental object of study in the field of permutation patterns. This poset has a very rich and complex topology and an understanding of its Möbius function has proved particularly elusive, although results have been slowly emerging in the last few years. Using a variety of topological techniques we present a two term formula for the Möbius function of intervals in \(\mathcal{P}\). The first term in this formula is, up to sign, the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is (still) complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. This is thus the first polynomial time formula for the Möbius function of what appears to be a large proportion of all intervals of \(\mathcal{P}\).
L'ensemble partiellement ordonné (EPO) \(\mathcal{P}\) de toutes les permutations, ordonnées par inclusion de motifs, est d'importance fondamentale dans l'étude des motifs de permutations. Cet EPO Possède une topologie très riche et complexe ; comprendre la fonction de Möbius associée s'est avéré particulièrement difficile, même si des résultats sont apparus lentement au cours des dernières années. En utilisant divers outils topologiques nous établissons une formule (contenant deux termes) pour la fonction de Möbius appliquée aux intervalles de \(\mathcal{P}\). Le premier terme de cette formule est, à un signe près, le nombre des occurrences dites normales d'une permutation dans une autre. Notre définition des occurrences normales est semblable à celles que l'on trouve à plusieurs endroits dans la littérature existante sur la fonction de Möbius, que ce soit de cet EPO ou d'autres ; mais elle semble plus simple que la plupart de celles-ci. Le second terme de la formule est compliqué, mais nous conjecturons qu'il se réduit à zéro pour bon nombre d'intervalles. Nous présentons des exemples où le second terme est réduit à zéro, ainsi que des exemples où ce n'est pas le cas. Le calcul de la fonction de Möbius en utilisant la formule de récurrence dans sa définition a une complexité exponentielle, tandis que le calcul du premier terme de notre formule a une complexité polynomiale, et la partie exponentielle est isolée dans le second terme, qui semble souvent réduit à zéro. Nous obtenons ainsi le premier algorithme polynomial pour calculer la fonction de Möbius de ce qui semble être une part importante d'intervalles de \(\mathcal{P}\).
The Smith normal form distribution of a random integer matrix
by Richard Stanley and Yinghui Wang
We show that the density \(\mu\) of the Smith normal form (SNF) of a random integer matrix exists and equals a product of densities \(\mu_{p^s}\) of SNF over \(\mathbb{Z}/p^s\mathbb{Z}\) with \(p\) a prime and \(s\) some positive integer. Our approach is to connect the SNF of a matrix with the greatest common divisors (gcds) of certain polynomials of matrix entries, and develop the theory of multi-gcd distribution of polynomial values at a random integer vector. We also derive a formula for \(\mu_{p^s}\) and determine the density \(\mu\) for several interesting types of sets.
Nous montrons ue la densité \(\mu\) de la forme normale de Smith (FNS) d'une matrice entière aléatoire existe et vaut le produit des densités \(\mu_{p^s}\) de la FNS sur \(\mathbb{Z}/p^s\mathbb{Z}\) avec \(p\) premier et \(s\) un entier positif. Notre approche est de relier la FNS d'une matrice avec les plus grand commun diviseurs (pgcds) de certains polynômes des entrées de la matrice, et de développer la théorie de la distribution du multi-pgcd de polynômes évalués sur un vecteur entier aléatoire. Nous obtenons aussi une formule pour \(\mu_{p^s}\) et déterminons la densité \(\mu\) pour plusieurs types d'ensembles intéressants.
Cataland: Why the Fuss?
by Christian Stump, Hugh Thomas and Nathan Williams
The main objects of noncrossing Catalan combinatorics associated to a finite Coxeter system are noncrossing partitions, sortable elements, and cluster complexes. The first and the third of these have known Fuss-Catalan generalizations. We provide new viewpoints for these, introduce a corresponding generalization of sortable elements as elements in the positive Artin monoid, and show how this perspective ties together all three generalizations.
Les objets principaux de la combinatoire de Catalan non-croisée associés à un système de Coxeter fini sont les partitions non-croisées, les éléments triables, et les complexes de clusters. Le premier et le troisième d'entre eux ont des généralisations Fuss-Catlan connues. Nous fournissons de nouveaux points de vue pour ceux-ci, nous introdusons une généralisation des éléments triables comme éléments dans le monoïde positif d'Artin, et nous montrons comment cette perspective regroupe les trois généralisations.
Symmetric matrices, Catalan paths, and correlations
by Bernd Sturmfels, Emmanuel Tsukerman and Lauren Williams
Kenyon and Pemantle (2014) gave a formula for the entries of a square matrix in terms of connected principal and almost-principal minors. Each entry is an explicit Laurent polynomial whose terms are the weights of domino tilings of a half Aztec diamond. They conjectured an analogue of this parametrization for symmetric matrices, where the Laurent monomials are indexed by Catalan paths. In this paper we prove the Kenyon-Pemantle conjecture, and apply this to a statistics problem pioneered by Joe (2006). Correlation matrices are represented by an explicit bijection from the cube to the elliptope.
Kenyon et Pemantle (2014) ont donné une formule pour les entrées d'une matrice carrée en termes des mineurs connectés principaux et presque principaux. Chaque entrée est un polynôme de Laurent explicite dont les termes sont les poids de pavages domino d'un demi-diamant Aztec. Ils ont conjecturé un analogue de cette paramétrisation pour les matrices symétriques, où les monômes de Laurent sont indexés par des chemins catalans. Dans cet article, nous prouvons la conjecture de Kenyon-Pemantle, et se rapportent à un problème de statistiques mis au point par Joe (2006). Les matrices de corrélation sont représentés par une bijection explicite du cube à l'elliptope.
Rational Shi tableaux and the skew length statistic
by Robin Sulzgruber
We define two refinements of the skew length statistic on simultaneous core partitions. The first one relies on hook lengths and is used to prove a refined version of the theorem stating that the skew length is invariant under conjugation of the core. The second one is equivalent to a generalisation of Shi tableaux to the rational level of Catalan combinatorics. We prove that the rational Shi tableau is injective. Moreover we present a uniform definition of the rational Shi tableau for Weyl groups and conjecture injectivity in the general case.
Nous définissons deux raffinements de la statistique de longueur gauche sur les partitions simultanément coeur. Le premier repose sur les longueurs d'équerre et est utilisé pour prouver une version plus fine du théorème d'invariance de la longueur gauche par conjugaison du coeur. Le second est équivalent à une généralisation des tableaux de Shi au niveau rationnel de la combinatoire de Catalan. Nous démontrons que le tableau de Shi rationnel est injectif. De plus nous présentons une définition uniforme du tableau de Shi rationnel pour les groupes de Weyl, et conjecturons l'injectivité dans le cas général.
Strange Expectations and Simultaneous Cores
by Marko Thiel and Nathan Williams
Let \(\gcd(a,b)=1\). J. Olsson and D. Stanton proved that the maximum number of boxes in a simultaneous \((a,b)\)-core is \(\frac{(a^2-1)(b^2-1)}{24}\), and showed that this maximum is achieved by a unique core. P. Johnson combined Ehrhart theory with the polynomial method to prove D. Armstrong's conjecture that the expected number of boxes in a simultaneous \((a,b)\)-core is \(\frac{(a-1)(b-1)(a+b+1)}{24}\). We apply P. Johnson's method to compute the variance and third moment. By extending the definitions of « simultaneous cores » and « number of boxes » to affine Weyl groups, we give uniform generalizations of these formulae to simply-laced affine types. We further explain the appearance of the number \(24\) using the « strange formula » of H. Freudenthal and H. de Vries.
Soit \(\gcd (a, b) = 1\). J. Olsson et D. Stanton ont prouvé que le nombre maximum de cases dans un \((a,b)\)-core simultané est \(\frac{(a^2-1)(b^2-1)}{24}\), et que ce maximum est atteint par un core unique. P. Johnson a combiné la théorie Ehrhart avec la méthode polynomiale afin de prouver une conjecture de D. Armstrong avançant que le nombre de cases dans un \((a,b)\)-core simultané est \(\frac{(a-1)(b-1)(a+b+1)}{24}\). Nous appliquons cette méthode de P. Johnson pour calculer la variance et le troisième moment. En étendant les définitions de « core simultanés » et « nombre de boîtes » aux groupes de Weyl affines, nous arrivons à des généralisations uniformes de ces formules pour tout type affine simplement-lacé. Nous expliquons l'apparition du nombre \(24\) en utilisant la « formule étrange » de H. Freudenthal et H. de Vries.
Extending the weak order on Coxeter groups
by François Viard
We introduce a new family of complete lattices, arising from a digraph together with a valuation on its vertices and generalizing a previous construction of the author. We then apply this to the study of two long-standing conjectures of Dyer, and we provide a description of the Tamari lattice with this theory.
On introduit une nouvelle famille de treillis complets, définis à partir de graphes orientés munis d'une valuation sur leurs sommets, qui généralisent une précédente construction de l'auteur. On applique ensuite cette construction à l'étude de deux conjectures de Dyer, et on fournit une description du treillis de Tamari à l'aide de notre théorie.
On (non-) freeness of some tridendriform algebras
by Vincent Vong
We present some results on the freeness or non freeness of some tridendriform algebras. In particular, we give a combinatorial proof of the freeness of WQSym, an algebra based on packed words, result already known with an algebraic proof. Then, we prove the non-freeness of an another tridendriform algebra, PQSym, a conjecture remained open. The method of these proofs is generalizable, in particular it has been used to prove the freeness of the dendriform algebra FQSym and the quadrialgebra of \(2\)-permutations.
Nous présentons des résultats de liberté concernant certaines algèbres tridendriformes. En particulier, nous prouvons par des arguments combinatoires que l'algèbre WQSym est tridendriforme libre, résultat déjà connu, mais obtenu par des méthodes purement algébriques. Puis nous prouvons que PQSym n'est pas une algèbre tridendriforme libre, conjecture restée ouverte jusqu'à présent. Les méthodes utilisées dans les preuves sont généralisable. En particulier, elles ont été utilisées pour prouver la liberté de l'algèbre dendriforme FQSym et de la quadrialgèbre des \(2\)-permutations.
Krasiewicz-Pragacz modules and Pieri and dual Pieri rules for Schubert polynomials
by Masaki Watanabe
In their 1987 paper Kraskiewicz and Pragacz defined certain modules, which we call KP modules, over the upper triangular Lie algebra whose characters are Schubert polynomials. In a previous work the author showed that the tensor product of Kraskiewicz-Pragacz modules always has KP filtration, i.e. a filtration whose each successive quotients are isomorphic to KP modules. In this paper we explicitly construct such filtrations for certain special cases of these tensor product modules, namely \(\mathcal{S}_w \otimes S^d(K^i)\) and \(\mathcal{S}_w \otimes \bigwedge^d(K^i)\), corresponding to Pieri and dual Pieri rules for Schubert polynomials.
Dans leur étude en 1987 Kraskiewicz et Pragacz ont defini certains modules, que nous appelons modules KP, sur les algébres de Lie des matrices triangulaires supérieures, dont les caractéres sont les polynômes de Schubert. Dans une étude récente l'auteur a prouvé que les produits tensoriels de deux modules KP ont des filtrations KP, c'est-à-dire des filtrations dont les quotients successifs sont des modules KP. Dans cet article nous construisons explicitement telles filtrations pour certains cas de ces produits tensoriels, à savoir \(\mathcal{S}_w \otimes S^d(K^i)\) et \(\mathcal{S}_w \otimes \bigwedge^d(K^i)\), correspondant aux formules de Pieri et de Pieri double pour les polynômes de Schubert.
The Prism tableau model for Schubert polynomials
by Anna Weigandt and Alexander Yong
The Schubert polynomials lift the Schur basis of symmetric polynomials into a basis for \({\mathbb Z}[x_1,x_2,\ldots]\). We suggest the prism tableau model for these polynomials. A novel aspect of this alternative to earlier results is that it directly invokes semistandard tableaux; it does so as part of a colored tableau amalgam. In the Grassmannian case, a prism tableau with colors ignored is a semistandard Young tableau. Our arguments are developed from the Gröbner geometry of matrix Schubert varieties.
Les polynômes de Schubert prolongent la base des polynômes de Schur des polynômes symétriques en une base de \({\mathbb Z}[x_1,x_2,...]\). Nous suggérons le modèle de tableaux de prismes pour ces polynômes. Un nouvel aspect de cette alternative aux résultats antérieurs est qu'elle utilise directement les tableaux semi-standards; Ces derniers apparaissent sous forme d'amalgames de tableaux colorés. Dans le cas Grassmannien, un tableau de prisme avec les couleurs omises est un tableau de Young semi-standard. Nos arguments sont basés sur la géométrie de Gröbner des variétés de matrices de Schubert.
Quasisymmetric functions from combinatorial Hopf monoids and Ehrhart Theory
by Jacob White
We investigate quasisymmetric functions coming from combinatorial Hopf monoids. We show that these invariants arise naturally in Ehrhart theory, and that some of their specializations are Hilbert functions for relative simplicial complexes. This class of complexes, called forbidden composition complexes, also forms a Hopf monoid, thus demonstrating a link between Hopf algebras, Ehrhart theory, and commutative algebra. We also study various specializations of quasisymmetric functions.
Nous étudions les fonctions quasisymétriques associées aux monoïdes de Hopf combinatoriaux. Nous démontrons que ces invariants sont des objets naturels à la théorie de Ehrhart. De plus, certains correspondent à des fonctions de Hilbert associées à des complexes simpliciaux relatifs. Cette classe de complexes, constitue un monoïde de Hopf, révélant ainsi un lien entre les algèbres de Hopf, la théorie de Ehrhart, et l'algèbre commutative. Nous étudions également diverses catégories de fonctions quasisymétriques.
The flag upper bound theorem for 3- and 5-manifolds
by Hailun Zheng
We prove that among all flag 3-manifolds on \(n\) vertices, the join of two circles with \(\left\lceil{\frac{n}{2}}\right \rceil\) and \(\left\lfloor{\frac{n}{2}}\right \rfloor\) vertices respectively is the unique maximizer of the face numbers. This solves the first case of a conjecture due to Lutz and Nevo. Further, we establish a sharp upper bound on the number of edges of flag 5-manifolds and characterize the cases of equality. We also show that the inequality part of the flag upper bound conjecture continues to hold for all flag 3-dimensional Eulerian complexes and characterize the cases of equality in this class.
Nous montrons que parmi tous les \(3\)-variétés à \(n\) sommets, le join de deux cercles avec \(\left\lceil{\frac{n}{2}}\right \rceil\) et \(\left\lfloor{\frac{n}{2}}\right \rfloor\) sommets respectivement est la seule variété qui maximise le nombre de faces. Cela prouve le premier cas d'une conjecture due à Lutz et Nevo. Par ailleurs, nous établissons une borne supérieure optimale pour le nombre d'arêtes des \(5\)-variétés de cliques et nous caractérisons les cas d'égalité. Nous montrons également que l'inégalité de la conjecture de la borne supérieure est satisfaite pour toutes les complexes de cliques Eulériens \(3\)-dimensionnels et nous caractérisons les cas d'égalité dans cette classe.

Valid XHTML 1.0 Strict CSS Valide !