bluuebunny/crossref_metadata_2025_split huggingface dataset:
Kazhdan-Lusztig polynomials of boolean elements
Authors: Mongelli Pietro 
Published: August 2021

We give closed combinatorial product formulas for Kazhdan–Lusztig poynomials and their parabolic analogue of type $q$ in the case of boolean elements, introduced in [M. Marietti, Boolean elements in Kazhdan–Lusztig theory, J. Algebra 295 (2006)], in Coxeter groups whose Coxeter graph is a tree. Such formulas involve Catalan numbers and use a combinatorial interpretation of the Coxeter graph of the group. In the case of classical Weyl groups, this combinatorial interpretation can be restated in terms of statistics of (signed) permutations. As an application of the formulas, we compute the intersection homology Poincaré polynomials of the Schubert varieties of boolean elements.
Nous donnons des formules combinatoires pour les polynômes de Kazhdan-Lusztig et leurs analogues paraboliques de type $q$ pour les éléments booléens, introduite dans [M. Marietti, Boolean elements in Kazhdan–Lusztig theory, J. Algebra 295 (2006)], dans les groupes de Coxeter dont le graphe de Coxeter est un arbre. Ces formules utilisent les nombres de Catalan et une interprétation combinatoire des graphes du groupe de Coxeter. Dans le cas des groupes de Weyl classiques, cette interprétation combinatoire peut être reformulée en termes de statistiques de permutations avec signe. Avec ces formules, on peut calculer le polynôme de l’intersection homologie de Poincaré pour la variété de Schubert de éléments booléens.
Some simple varieties of trees arising in permutation analysis
Authors: Bouvel Mathilde , Mishna Marni , Nicaud Cyril 
Published: August 2021

After extending classical results on simple varieties of trees to trees counted by their number of leaves, we describe a filtration of the set of permutations based on their strong interval trees. For each subclass we provide asymptotic formulas for number of trees (by leaves), average number of nodes of fixed arity, average subtree size sum, and average number of internal nodes. The filtration is motivated by genome comparison of related species.
Nous commençons par étendre les résultats classiques sur les variétés simples d'arbres aux arbres comptés selon leur nombre de feuilles, puis nous décrivons une filtration de l'ensemble des permutations qui repose sur leurs arbres des intervalles communs. Pour toute sous-classe, nous donnons des formules asymptotiques pour le nombre d'arbres (comptés selon les feuilles), le nombre moyen de nœuds d'arité fixée, la moyenne de la somme des tailles des sous-arbres, et le nombre moyen de nœuds internes. Cette filtration est motivée par des problématiques de comparaison de génomes.
Long Cycle Factorizations: Bijective Computation in the General Case
Authors: Vassilieva Ekaterina A. 
Published: August 2021

This paper is devoted to the computation of the number of ordered factorizations of a long cycle in the symmetric group where the number of factors is arbitrary and the cycle structure of the factors is given. Jackson (1988) derived the first closed form expression for the generating series of these numbers using the theory of the irreducible characters of the symmetric group. Thanks to a direct bijection we compute a similar formula and provide the first purely combinatorial evaluation of these generating series.
Cet article est dédié au calcul du nombre de factorisations d’un long cycle du groupe symétrique pour lesquels le nombre de facteurs est arbitraire et la structure des cycles des facteurs est donnée. Jackson (1988) a dérivé la première expression compacte pour les séries génératrices de ces nombres en utilisant la théorie des caractères irréductibles du groupe symétrique. Grâce à une bijection directe nous démontrons une formule similaire et donnons ainsi la première évaluation purement combinatoire de ces séries génératrices.
Two bijections on Tamari Intervals
Authors: Chapoton Frédéric , Chatel Gregory , Pons Viviane 
Published: August 2021

We use a recently introduced combinatorial object, the $\textit{interval-poset}$, to describe two bijections on intervals of the Tamari lattice. Both bijections give a combinatorial proof of some previously known results. The first one is an inner bijection between Tamari intervals that exchanges the $\textit{initial rise}$ and $\textit{lower contacts}$ statistics. Those were introduced by Bousquet-Mélou, Fusy, and Préville-Ratelle who proved they were symmetrically distributed but had no combinatorial explanation. The second bijection sends a Tamari interval to a closed flow of an ordered forest. These combinatorial objects were studied by Chapoton in the context of the Pre-Lie operad and the connection with the Tamari order was still unclear.
Nous utilisons les $\textit{intervalles-posets}$, très récemment introduits, pour décrire deux bijections sur les intervalles du treillis de Tamari. Nous obtenons ainsi des preuves combinatoires de précédents résultats. La première bijection est une opération interne sur les intervalles qui échange les statistiques de la $\textit{montée initiale}$ et du $\textit{nombre de contacts}$. Ces dernières ont été introduites par Bousquet-Mélou, Fusy et Préville-Ratelle qui ont prouvé qu’elles étaient symétriquement distribuées sans pour autant proposer d’explication combinatoire. La seconde bijection fait le lien avec un objet étudié par Chapoton dans le cadre de l’opérade Pré-Lie : les flots sur les forêts ordonnées. Le lien avec l’ordre de Tamari avait déjà été remarqué sans pour autant être expliqué.
Estimating deep Littlewood-Richardson Coefficients
Authors: Narayanan Hariharan 
Published: August 2021

Littlewood Richardson coefficients are structure constants appearing in the representation theory of the general linear groups $(GL_n)$. The main results of this paper are: 1. A strongly polynomial randomized approximation scheme for Littlewood-Richardson coefficients corresponding to indices sufficiently far from the boundary of the Littlewood Richardson cone. 2. A proof of approximate log-concavity of the above mentioned class of Littlewood-Richardson coefficients.
Coefficients de Littlewood Richardson sont des constantes de structure apparaissant dans la théorie de la représentation des groupes linéaires généraux $(GL_n)$. Les principaux résultats de cette étude sont les suivants: 1. Un schéma d’approximation polynomiale randomisée fortement pour des coefficients de Littlewood-Richardson correspondant aux indices suffisamment loin de la limite du cône Littlewood Richardson. 2. Une preuve de l’approximatif log-concavité de la classe de coefficients de Littlewood-Richardson mentionné ci-dessus.
Descents of $\lambda$-unimodal cyclic permutations
Authors: Archer Kassie 
Published: August 2021

We prove an identity conjectured by Adin and Roichman involving the descent set of $\lambda$-unimodal cyclic permutations. These permutations appear in the character formulas for certain representations of the symmetric group and these formulas are usually proven algebraically. Here, we give a combinatorial proof for one such formula and discuss the consequences for the distribution of the descent set on cyclic permutations.
Nous prouvons une identité conjecturée par Adin et Roichman impliquant les ensembles des descentes des permutations cycliques $\lambda$-unimodales. Ces permutations apparaissent dans les formules des caractères pour certaines représentations du groupe symétrique, et ces formules sont généralement prouvées dans une manière algébrique. Ici, nous donnons une preuve combinatoire pour une telle formule et discutons les conséquences pour la distribution de l’ensemble des descentes sur des permutations cycliques.
Bijections on m-level Rook Placements
Authors: Barrese Kenneth , Sagan Bruce 
Published: August 2021

Partition the rows of a board into sets of $m$ rows called levels. An $m$-level rook placement is a subset of squares of the board with no two in the same column or the same level. We construct explicit bijections to prove three theorems about such placements. We start with two bijections between Ferrers boards having the same number of $m$-level rook placements. The first generalizes a map by Foata and Schützenberger and our proof applies to any Ferrers board. The second generalizes work of Loehr and Remmel. This construction only works for a special class of Ferrers boards but also yields a formula for calculating the rook numbers of these boards in terms of elementary symmetric functions. Finally we generalize another result of Loehr and Remmel giving a bijection between boards with the same hit numbers. The second and third bijections involve the Involution Principle of Garsia and Milne.
Nous considérons les rangs d’un échiquier partagés en ensembles de $m$ rangs appelés les niveaux. Un $m$-placement des tours est un sous-ensemble des carrés du plateau tel qu’il n’y a pas deux carrés dans la même colonne ou dans le même niveau. Nous construisons deux bijections explicites entre des plateaux de Ferrers ayant les mêmes nombres de $m$-placements. La première est une généralisation d’une fonction de Foata et Schützenberger et notre démonstration est pour n’importe quels plateaux de Ferrers. La deuxième généralise une bijection de Loehr et Remmel. Cette construction marche seulement pour des plateaux particuliers, mais ça donne une formule pour le nombre de $m$-placements en terme des fonctions symétriques élémentaires. Enfin, nous généralisons un autre résultat de Loehr et Remmel donnant une bijection entre deux plateaux ayant les mêmes nombres de coups. Les deux dernières bijections utilisent le Principe des Involutions de Garsia et Milne.
Some combinatorial identities involving noncommuting variables
Authors: Schlosser Michael , Yoo Meesue 
Published: August 2021

We derive combinatorial identities for variables satisfying specific sets of commutation relations. The identities thus obtained extend corresponding ones for $q$-commuting variables $x$ and $y$ satisfying $yx=qxy$. In particular, we obtain weight-dependent binomial theorems, functional equations for generalized exponential functions, we propose a derivative of noncommuting variables, and finally utilize one of the considered weight functions to extend rook theory. This leads us to an extension of the $q$-Stirling numbers of the second kind, and of the $q$-Lah numbers.
Nous obtenons des identités combinatoires pour des variables satisfaisant des ensembles spécifiques de relations de commutation. Ces identités ainsi obtenues généralisent leurs analogues pour des variables $q$-commutantes $x$ et $y$ satisfaisant $yx=qxy$. En particulier, nous obtenons des théorèmes binomiaux dépendant du poids, des équations fonctionnelles pour les fonctions exponentielles généralisées, nous proposons une dérivée des variables non-commutatives, et finalement nous utilisons l’une des fonctions de poids considérées pour étendre la théorie des tours. Nous en déduisons une généralisation des $q$-nombres de Stirling de seconde espèce et des $q$-nombres de Lah.
A Categorification of One-Variable Polynomials
Authors: Khovanov Mikhail , Sazdanovic Radmila 
Published: August 2021

We develop a diagrammatic categorification of the polynomial ring $\mathbb{Z} [x]$, based on a geometrically-defined graded algebra and show how to lift various operations on polynomials to the categorified setting. Our categorification satisfies a version of the Bernstein-Gelfand-Gelfand reciprocity property, with indecomposable projective modules corresponding to $x^n$ and standard modules to $(x -1)^n$ in the Grothendieck ring. This construction generalizes tocategorification of various orthogonal polynomials.
Résumé. Catégorification de l’anneau des polynômes $\mathbb{Z} [x]$, Nous développons une catégorification diagrammatique de l’anneau des polynômes $\mathbb{Z} [x]$, s’appuyant sur une algèbre graduée définie de manière géométrique, et nous décrivons comment on peut relever certaines opérations sur les polynômes dans cette catégorification. Notre catégorification vérifie une version de la réciprocité de Bernstein-Gelfand-Gelfand, avec les modules projectifs indécomposables correspondants à $x^n$ et les modules standards correspondants à $(x - 1)^n$ dans l’anneau de Grothendieck. Cette construction se généralise à certains polynômes orthogonaux.
The polytope of Tesler matrices
Authors: Mészáros Karola , Morales Alejandro H. , Rhoades Brendon 
Published: August 2021

26 pages, 4 figures. v2 has typos fixed, updated references, and a final remarks section including remarks from previous sections
We introduce the Tesler polytope $Tes_n(a)$, whose integer points are the Tesler matrices of size n with hook sums $a_1,a_2,...,a_n in Z_{\geq 0}$. We show that $Tes_n(a)$ is a flow polytope and therefore the number of Tesler matrices is counted by the type $A_n$ Kostant partition function evaluated at $(a_1,a_2,...,a_n,-\sum_{i=1}^n a_i)$. We describe the faces of this polytope in terms of "Tesler tableaux" and characterize when the polytope is simple. We prove that the h-vector of $Tes_n(a)$ when all $a_i>0$ is given by the Mahonian numbers and calculate the volume of $Tes_n(1,1,...,1)$ to be a product of consecutive Catalan numbers multiplied by the number of standard Young tableaux of staircase shape.
On présente le polytope de Tesler $Tes_n(a)$, dont les points réticuilaires sont les matrices de Tesler de taillen avec des sommes des équerres $a_1,a_2,...,a_n in Z_{\geq 0}$. On montre que $Tes_n(a)$ est un polytope de flux. Donc lenombre de matrices de Tesler est donné par la fonction de Kostant de type An évaluée à ($(a_1,a_2,...,a_n,-\sum_{i=1}^n a_i)$On décrit les faces de ce polytope en termes de “tableaux de Tesler” et on caractérise quand le polytope est simple.On montre que l’h-vecteur de $Tes_n(a)$ , quand tous les $a_i>0$ , est donnée par le nombre de permutations avec unnombre donné d’inversions et on calcule le volume de T$Tes_n(1,1,...,1)$ comme un produit de nombres de Catalanconsécutives multiplié par le nombre de tableaux standard de Young en forme d’escalier
Genomic Tableaux and Combinatorial $K$-Theory
Authors: Pechenik Oliver , Yong Alexander 
Published: August 2021

We introduce genomic tableaux, with applications to Schubert calculus. We report a combinatorial rule for structure coefficients in the torus-equivariant $K$-theory of Grassmannians for the basis of Schubert structure sheaves. This rule is positive in the sense of [Anderson-Griffeth-Miller ’11]. We thereby deduce an earlier conjecture of [Thomas-Yong ’13] for the coefficients. Moreover, our rule specializes to give a new Schubert calculus rule in the (non-equivariant) $K$-theory of Grassmannians. From this perspective, we also obtain a new rule for $K$-theoretic Schubert structure constants of maximal orthogonal Grassmannians, and give conjectural bounds on such constants for Lagrangian Grassmannians.
Nous introduisons la notion de tableau génomique, pour l’appliquer au calcul de Schubert. Nous énonçons une règle combinatoire pour les coefficients de structure de la $K$-théorie tore-équivariante des grassmanniennes, dans la base définie par les classes des faisceaux structuraux des variétés de Schubert. Cette règle est positive au sens de [Anderson-Griffeth-Miller ’11]. Nous en déduisons une conjecture de [Thomas-Yong ’13]. De plus, notre règle se spécialise en une règle nouvelle pour le calcul de Schubert dans la $K$-théorie (non équivariante) des grassmanniennes. Nous obtenons également une nouvelle règle pour les coefficients de structure de la $K$-théorie des grassmanniennes orthogonales maximales dans la base de Schubert, et nous conjecturons certaines bornes pour ces coefficients dans le cas des grassmanniennes lagrangiennes.
The freeness of Ish arrangements
Authors: Abe Takuro , Suyama Daisuke , Tsujie Shuhei 
Published: August 2021

The Ish arrangement was introduced by Armstrong to give a new interpretation of the $q; t$-Catalan numbers of Garsia and Haiman. Armstrong and Rhoades showed that there are some striking similarities between the Shi arrangement and the Ish arrangement and posed some problems. One of them is whether the Ish arrangement is a free arrangement or not. In this paper, we verify that the Ish arrangement is supersolvable and hence free. Moreover, we give a necessary and sufficient condition for the deleted Ish arrangement to be free
L’arrangement Ish a été introduit par Armstrong pour donner une nouvelle interprétation des nombres $q; t$-Catalan de Garsia et Haiman. Armstrong et Rhoades ont montré qu’il y avait des ressemblances frappantes entre l’arrangement Shi et l’arrangement Ish et ont posé des conjectures. L’une d’elles est de savoir si l’arrangement Ish est un arrangement libre ou pas. Dans cet article, nous vérifions que l’arrangement Ish est supersoluble et donc libre. De plus, on donne une condition nécessaire et suffisante pour que l’arrangement Ish réduit soit libre.
Formal Group Laws and Chromatic Symmetric Functions of Hypergraphs
Authors: Taylor Jair 
Published: August 2021

If $f(x)$ is an invertible power series we may form the symmetric function $f(f^{-1}(x_1)+f^{-1}(x_2)+...)$ which is called a formal group law. We give a number of examples of power series $f(x)$ that are ordinary generating functions for combinatorial objects with a recursive structure, each of which is associated with a certain hypergraph. In each case, we show that the corresponding formal group law is the sum of the chromatic symmetric functions of these hypergraphs by finding a combinatorial interpretation for $f^{-1}(x)$. We conjecture that the chromatic symmetric functions arising in this way are Schur-positive.
Si $f(x)$ est une série entière inversible, nous pouvons former la fonction symétrique $f(f^{-1}(x_1)+f^{-1}(x_2)+...)$ que nous appelons une loi de groupe formel. Nous donnons plusieurs exemples de séries entières $f(x)$ qui sont séries génératrices ordinaires pour des objets combinatoires avec une structure récursive, chacune desquelles est associée à un certain hypergraphe. Dans chaque cas, nous donnons une interprétation combinatoire à $f^{-1}(x)$, ce qui nous permet de montrer que la loi de groupe formel correspondante est la somme des fonctions symétriques chromatiques de ces hypergraphes. Nous conjecturons que les fonctions symétriques chromatiques apparaissant de cette manière sont Schur-positives.
Combinatorial Hopf Algebras of Simplicial Complexes
Authors: Benedetti Carolina , Hallam Joshua , Machacek John 
Published: August 2021

We consider a Hopf algebra of simplicial complexes and provide a cancellation-free formula for its antipode. We then obtain a family of combinatorial Hopf algebras by defining a family of characters on this Hopf algebra. The characters of these Hopf algebras give rise to symmetric functions that encode information about colorings of simplicial complexes and their $f$-vectors. We also use characters to give a generalization of Stanley’s $(-1)$-color theorem.
Nous considérons une algèbre de Hopf de complexes simpliciaux et fournissons une formule sans multiplicité pour son antipode. On obtient ensuite une famille d'algèbres de Hopf combinatoires en définissant une famille de caractères sur cette algèbre de Hopf. Les caractères de ces algèbres de Hopf donnent lieu à des fonctions symétriques qui encode de l’information sur les coloriages du complexe simplicial ainsi que son vecteur-$f$. Nousallons également utiliser des caractères pour donner une généralisation du théorème $(-1)$ de Stanley.
Fan realizations of type $A$ subword complexes and multi-associahedra of rank 3
Authors: Bergeron Nantel , Ceballos Cesar , Labbé Jean-Philippe 
Published: August 2021

We present complete simplicial fan realizations of any spherical subword complex of type $A_n$ for $n\leq 3$. This provides complete simplicial fan realizations of simplicial multi-associahedra $\Delta_{2k+4,k}$, whose facets are in correspondence with $k$-triangulations of a convex $(2k+4)$-gon. This solves the first open case of the problem of finding fan realizations where polytopality is not known. The techniques presented in this paper work for all finite Coxeter groups and we hope that they will be useful to construct fans realizing subword complexes in general. In particular, we present fan realizations of two previously unknown cases of subword complexes of type $A_4$, namely the multi-associahedra $\Delta_{9,2}$ and $\Delta_{11,3}$.
Nous construisons des éventails simpliciaux complets ayant la combinatoire des complexes de sous-mots de type $A_n$ pour $n\leq 3$. Par conséquent, nous obtenons des constructions d’éventails des multi-associaèdres $\Delta_{2k+4,k}$, dont les facettes correspondent aux $k$-triangulations d’un $(2k+4)$-gone. Cette construction confirme l’existence d’éventails ayant la combinatoire du multi-associaèdres pour une famille dont la polytopalité n’est pas confirmée. Les techniques utilisées fonctionnent pour tous les groupes de Coxeter et nous espérons qu’elles seront utiles afin de construire des éventails réalisant les complexes de sous-mots en général. En particulier, nous présentons des éventails pour deux complexes de sous-mots de type $A_4$ dont l’existence était inconnue: les multi-associaèdres $\Delta_{9,2}$ et $\Delta_{11,3}$.
Sign variation, the Grassmannian, and total positivity
Authors: Karp Steven N. 
Published: August 2021

The <i>totally nonnegative Grassmannian</i> is the set of $k$-dimensional subspaces $V$ of &#8477;<sup>$n$</sup> whose nonzero Plücker coordinates (i.e. $k &times; k$ minors of a $k &times; n$ matrix whose rows span $V$) all have the same sign. Total positivity has been much studied in the past two decades from an algebraic, combinatorial, and topological perspective, but first arose in the theory of oscillations in analysis. It was in the latter context that Gantmakher and Krein (1950) and Schoenberg and Whitney (1951) independently showed that a subspace $V$ is totally nonnegative iff every vector in $V$, when viewed as a sequence of $n$ numbers and ignoring any zeros, changes sign fewer than $k$ times. We generalize this result, showing that the vectors in $V$ change sign fewer than $l$ times iff certain sequences of the Plücker coordinates of some <i>generic perturbation</i> of $V$ change sign fewer than $l &minus; k &plus; 1$ times. We give an algorithm which constructs such a generic perturbation. Also, we determine the <i>positroid cell</i> of each totally nonnegative $V$ from sign patterns of vectors in $V$. These results generalize to oriented matroids.
La <i>grassmannienne totalement non négative</i> est l’ensemble des sous-espaces $V$ de &#8477;<sup>$n$</sup> de dimension $k$ dont coordonnées plückeriennes non nulles (mineurs de l’ordre $k$ d’une matrice $k &times; n$ dont les lignes engendrent $V$) ont toutes le même signe. La positivité totale a beaucoup été étudiée durant les deux dernières décennies d’une perspective algébrique, combinatoire, et topologique, mais a pris naissance dans la théorie analytique des oscillations. C’est dans ce contexte que Gantmakher et Krein (1950) et Schoenberg et Whitney (1951) ont indépendamment démontré qu’un sous-espace $V$ est totalement non négatif ssi chaque vecteur dans $V$, lorsque considéré comme une séquence de $n$ nombres et dont on ignore les zéros, change de signe moins de $k$ fois. Nous généralisons ce résultat, démontrant que les vecteurs dans $V$ changent de signe moins de $l$ fois ssi certaines séquences des coordonnées plückeriennes d’une <i>perturbation générique</i> de $V$ changent de signe moins de $l &minus; k &plus; 1$ fois. Un algorithme construisant une telle perturbation générique est obtenu. De plus, nous déterminons la <i>cellule positroïde</i> de chaque $V$ totalement non négatif à partir des données de signe des vecteurs dans $V$. Ces résultats sont valides pour les matroïdes orientés.