bluuebunny/crossref_metadata_2025_split huggingface dataset:
Classification of Ehrhart polynomials of integral simplices
Authors: Higashitani Akihiro 
Published: August 2021

Let $δ (\mathcal{P} )=(δ _0,δ _1,\ldots,δ _d)$ be the $δ$ -vector of an integral convex polytope $\mathcal{P}$ of dimension $d$. First, by using two well-known inequalities on $δ$ -vectors, we classify the possible $δ$ -vectors with $\sum_{i=0}^d δ _i ≤3$. Moreover, by means of Hermite normal forms of square matrices, we also classify the possible $δ$ -vectors with $\sum_{i=0}^d δ _i = 4$. In addition, for $\sum_{i=0}^d δ _i ≥5$, we characterize the $δ$ -vectors of integral simplices when $\sum_{i=0}^d δ _i$ is prime.
Soit $δ (\mathcal{P} )=(δ _0,δ _1,\ldots,δ _d)$ le $δ$ -vecteur d'un polytope intégrante de dimension d. Tout d'abord, en utilisant deux bien connus des inégalités sur $δ$ -vecteurs, nous classons les $δ$ -vecteurs possibles avec $\sum_{i=0}^d δ _i ≤3$ En outre, par le biais de Hermite formes normales, nous avons également classer les $δ$ -vecteurs avec $\sum_{i=0}^d δ _i = 4$. De plus, pour $\sum_{i=0}^d δ _i ≥5$, nous caractérisons les $δ$-vecteurs des simplex inégalités lorsque $\sum_{i=0}^d δ _i$ est premier.
The multivariate arithmetic Tutte polynomial
Authors: Brändèn Petter , Moci Luca 
Published: August 2021

We introduce an arithmetic version of the multivariate Tutte polynomial recently studied by Sokal, and a quasi-polynomial that interpolates between the two. We provide a generalized Fortuin-Kasteleyn representation for representable arithmetic matroids, with applications to arithmetic colorings and flows. We give a new proof of the positivity of the coefficients of the arithmetic Tutte polynomial in the more general framework of pseudo-arithmetic matroids. In the case of a representable arithmetic matroid, we provide a geometric interpretation of the coefficients of the arithmetic Tutte polynomial.
Nous introduisons une version arithmétique du polynôme de Tutte multivariée récemment étudié par Sokal, et un quasi-polynôme qui interpole entre les deux. Nous proposons une représentation de Fortuin-Kasteleyn neutralise pour les matroïdes arithmétiques représentables, avec des applications aux colorations et flux arithmétiques. Nous donnons une nouvelle preuve de la positivité des coefficients du polynôme de Tutte arithmétique dans le cadre plus général des matroïdes pseudo-arithmétiques. Dans le cas d'un matroïde arithmétique représentable, nous proposons une interprétation géométrique des coefficients du polynôme de Tutte arithmétique.
Cumulants of the q-semicircular law, Tutte polynomials, and heaps
Authors: Josuat-Vergès Matthieu 
Published: August 2021

The q-semicircular law as introduced by Bożejko and Speicher interpolates between the Gaussian law and the semicircular law, and its moments have a combinatorial interpretation in terms of matchings and crossings. We prove that the cumulants of this law are, up to some factor, polynomials in q with nonnegative coefficients. This is done by showing that they are obtained by an enumeration of connected matchings, weighted by the evaluation at (1,q) of a Tutte polynomial. The two particular cases q=0 and q=2 have also alternative proofs, related with the fact that these particular evaluation of the Tutte polynomials count some orientations on graphs. Our methods also give a combinatorial model for the cumulants of the free Poisson law.
La loi q-semicirculaire introduite par Bożejko et Speicher interpole entre la loi gaussienne et la loi semi-circulaire, et ses moments ont une interprétation combinatoire en termes de couplages et croisements. Nous prouvons que les cumulants de cette loi sont, à un facteur près, des polynômes en q à coefficients positifs. La méthode consiste à obtenir ces cumulants par une énumération de couplages connexes, pondérés par l’évaluation en (1,q) d'un polynôme de Tutte. Les cas particuliers q=0 et q=2 ont une preuve alternative, reliè au fait que des évaluations particulières du polynôme de Tutte comptent certaines orientations de graphes. Nos méthodes donnent aussi un modèle combinatoire aux cumulants de la loi de Poisson libre.
Involutions on Baxter Objects
Authors: Dilks Kevin 
Published: August 2021

Baxter numbers are known to count several families of combinatorial objects, all of which come equipped with natural involutions. In this paper, we add a combinatorial family to the list, and show that the known bijections between these objects respect these involutions. We also give a formula for the number of objects fixed under this involution, showing that it is an instance of Stembridge's "$q=-1$ phenomenon''.
Les nombres Baxter comptent plusieurs familles d'objets combinatoires, qui sont tous équipés avec des involutions naturels. Dans ce papier, nous ajoutons une famille combinatoire à la liste, et nous montrons que les bijections connus entre ces objets respectent ces involutions. En plus, nous donnons une formule pour le nombre d'objets fixés par cette involution et nous montrons qu'elle est une instance du "phénomène $q =-1$'' de Stembridge.
Enumeration of permutations sorted with two passes through a stack and D_8 symmetries
Authors: Bouvel Mathilde , Guibert Olivier 
Published: August 2021

We examine the sets of permutations that are sorted by two passes through a stack with a $D_8$ operation performed in between. From a characterization of these in terms of generalized excluded patterns, we prove two conjectures on their enumeration, that can be refined with the distribution of some statistics. The results are obtained by generating trees.
On étudie les ensembles de permutations qui sont triées par deux passages dans une pile séparés par une opération du groupe $D_8$. À partir d'une caractérisation de ces ensembles en termes de motifs exclus généralisés, on démontre deux conjectures sur leur énumération, qui peuvent être raffinées par la distribution de certaines statistiques. Ces résultats sont obtenus à l'aide d'arbres de génération.
Computing Tutte Polynomials
Authors: Monagan Michael 
Published: August 2021

We present a new edge selection heuristic and vertex ordering heuristic that together enable one to compute the Tutte polynomial of much larger sparse graphs than was previously doable. As a specific example, we are able to compute the Tutte polynomial of the truncated icosahedron graph using our Maple implementation in under 4 minutes on a single CPU. This compares with a recent result of Haggard, Pearce and Royle whose special purpose C++ software took one week on 150 computers.
Nous présentons deux nouvelles heuristiques pour le calcul du polynôme de Tutte de graphes de faible densité, basées sur les principes de sélection d'arêtes et d'arrangement linéaire de sommets, et qui permettent de traiter des graphes de bien plus grande tailles que les méthodes existantes. Par exemple, en utilisant notre implémentation en Maple, nous pouvons calculer le polynôme de Tutte de l'isocahédron tronqué en moins de 4 minutes sur un ordinateur à processeur unique, alors qu'un programme ad-hoc récent de Haggard, Pearce et Royle, utilisant 150 ordinateurs, a nécessité une semaine de calcul pour obtenir le même résultat.
Universal Polynomials for Severi Degrees of Toric Surfaces
Authors: Ardila Federico , Block Florian 
Published: August 2021

The Severi variety parametrizes plane curves of degree $d$ with $\delta$ nodes. Its degree is called the Severi degree. For large enough $d$, the Severi degrees coincide with the Gromov-Witten invariants of $\mathbb{CP}^2$. Fomin and Mikhalkin (2009) proved the 1995 conjecture that for fixed $\delta$, Severi degrees are eventually polynomial in $d$. In this paper, we study the Severi varieties corresponding to a large family of toric surfaces. We prove the analogous result that the Severi degrees are eventually polynomial as a function of the multidegree. More surprisingly, we show that the Severi degrees are also eventually polynomial "as a function of the surface". Our strategy is to use tropical geometry to express Severi degrees in terms of Brugallé and Mikhalkin's floor diagrams, and study those combinatorial objects in detail. An important ingredient in the proof is the polynomiality of the discrete volume of a variable facet-unimodular polytope.
La variété de Severi paramétrise les courbes planes de degré $d$ avec $\delta$ nœuds. Son degré s'appelle le degré de Severi. Pour $d$ assez grand, les degrés de Severi coïncident avec les invariants de Gromov-Witten de $\mathbb{CP}^2$. Fomin et Mikhalkin (2009) ont prouvé une conjecture de 1995 que pour $\delta$ fixé, les degrés de Severi sont à terme des polynômes en $d$. Nous étudions les variétés de Severi correspondant à une large famille de surfaces toriques. Nous prouvons le résultat analogue que les degrés de Severi sont à terme des fonctions polynomiales du multidegré. De manière plus surprenante, nous montrons que les degrés de Severi sont à terme des polynômes en tant que "fonction de la surface''. Notre stratégie est d'utiliser la géométrie tropicale pour exprimer les degrés de Severi en fonction des "floor diagrams" de Brugallé et Mikhalkin, et d'utiliser ces objets combinatoires en détail. Un autre ingrédient important de la preuve est la polynomialité du volume discret d'un polytope face-unimodulaire variable.
The ABC's of affine Grassmannians and Hall-Littlewood polynomials
Authors: Dalal Avinash J. , Morse Jennifer 
Published: August 2021

We give a new description of the Pieri rule for $k$-Schur functions using the Bruhat order on the affine type-$A$ Weyl group. In doing so, we prove a new combinatorial formula for representatives of the Schubert classes for the cohomology of affine Grassmannians. We show how new combinatorics involved in our formulas gives the Kostka-Foulkes polynomials and discuss how this can be applied to study the transition matrices between Hall-Littlewood and $k$-Schur functions.
Nous présentons une nouvelle description, issue de l'ordre de Bruhat du groupe de Weyl affine de type $A$, de la règle de Pieri pour les fonctions $k$-Schur. Ce faisant, nous obtenons une nouvelle formule combinatoire pour les représentants des classes de Schubert de la cohomologie des Grassmannienne affines. Nous décrivons aussi comment notre approche permet d'obtenir les polynômes de Kostka-Foulkes et comment elle peut être appliquée à l’étude des matrices de transition entre les polynômes de Hall-Littlewood et les fonctions $k$-Schur.
Perturbation of transportation polytopes
Authors: Liu Fu 
Published: August 2021

We describe a perturbation method that can be used to compute the multivariate generating function (MGF) of a non-simple polyhedron, and then construct a perturbation that works for any transportation polytope. Applying this perturbation to the family of central transportation polytopes of order $kn \times n$, we obtain formulas for the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order $kn \times n$.
Nous décrivons une méthode de perturbation qui peut être utilisée pour calculer la fonction génératrice multivariée (MGF) d'un polyèdre non-simple, et ensuite construire une perturbation qui fonctionne pour tout polytope de transport. Appliquant cette perturbation à la famille des centraux de transport polytopes de l'ordre $kn \times n$, nous obtenons des formules pour le MGF du polytope. Les formules que nous obtenons sont énumérées par les objets combinatoires. Un cas spécial des formules récupère les résultats sur des polytopes de Birkhoff donnés par l'auteur et De Loera et Yoshida. Nous récupérons également la formule pour le nombre de sommets maximum des de transport polytopes d'ordre $kn \times n$.
Reduction formulae from the factorization Theorem of Littlewood-Richardson polynomials by King, Tollu and Toumazet
Authors: Cho Soojin , Jung Eun-Kyoung , Moon Dongho 
Published: August 2021

The factorization theorem by King, Tollu and Toumazet gives four different reduction formulae of Littlewood-Richardson coefficients. One of them is the classical reduction formula of the first type while others are new. Moreover, the classical reduction formula of the second type is not a special case of KTT theorem. We give combinatorial proofs of reduction formulae in terms of tableaux or hives. The proofs for the cases $r=1, 2, n-2$ in terms of tableaux and the proof for the classical reduction formula of the second type in terms of hives are new.
Le Théorème de factorisation par King, Tollu, et Toumazet donne quatre formules différentes de réduction des coefficients de Littlewood-Richardson. L'une d'entre eux est la formule classique de réduction du premier type alors que les trois autres sont nouvelles. De plus, la formule classique de réduction du deuxième type n'est pas un cas spécial du KTT théorème. Nous donnons preuves combinatoires des formules de réduction en termes de tableaux ou $\textit{hives}$. Les preuves pour les cas $r = 1, 2, n-2$ en termes de tableaux et la preuve pour la formule classique de réduction du deuxième type en termes de $\textit{hives}$ sont nouvelles.
The cluster basis $\mathbb{Z}[x_{1,1},…,x_{3,3}]
Authors: Skandera Mark 
Published: August 2021

We show that the set of cluster monomials for the cluster algebra of type $D_4$ contains a basis of the $\mathbb{Z}$-module $\mathbb{Z}[x_{1,1},\ldots ,x_{3,3}]$. We also show that the transition matrices relating this cluster basis to the natural and the dual canonical bases are unitriangular and nonnegative. These results support a conjecture of Fomin and Zelevinsky on the equality of the cluster and dual canonical bases. In the event that this conjectured equality is true, our results also imply an explicit factorization of each dual canonical basis element as a product of cluster variables.
Nous montrons que l'ensemble des monômes de l'algebre "cluster'' $D_4$ contient une base-$\mathbb{Z}$ pour le module $\mathbb{Z}[x_{1,1},\ldots ,x_{3,3}]$. Nous montrons aussi que les matrices transitoires qui relient cette base à la base canonique duale sont unitriangulaires. Ces résultats renforcent une conjecture de Fomin et de Zelevinsky sur l'égalité de ces deux bases. Si cette égalité s'avérait être vraie, notre résultat donnerait aussi une factorisation des éléments de la base canonique duale.
The quasiinvariants of the symmetric group
Authors: Bandlow Jason , Musiker Gregg 
Published: August 2021

For $m$ a non-negative integer and $G$ a Coxeter group, we denote by $\mathbf{QI_m}(G)$ the ring of $m$-quasiinvariants of $G$, as defined by Chalykh, Feigin, and Veselov. These form a nested series of rings, with $\mathbf{QI_0}(G)$ the whole polynomial ring, and the limit $\mathbf{QI}_{\infty}(G)$ the usual ring of invariants. Remarkably, the ring $\mathbf{QI_m}(G)$ is freely generated over the ideal generated by the invariants of $G$ without constant term, and the quotient is isomorphic to the left regular representation of $G$. However, even in the case of the symmetric group, no basis for $\mathbf{QI_m}(G)$ is known. We provide a new description of $\mathbf{QI_m}(S_n)$, and use this to give a basis for the isotypic component of $\mathbf{QI_m}(S_n)$ indexed by the shape $[n-1,1]$.
Pour $m$ un entier positif ou nul et $G$ un groupe de Coxeter, nous notons $\mathbf{QI_m}(G)$ l'anneau des quasiinvariants définis par Chalykh, Feigin et Veselov. On obtient ainsi une série d'anneaux emboités, $\mathbf{QI_0}(G)$ étant l'anneau des polynômes, et la limite $\mathbf{QI}_{\infty}(G)$ l'anneau des invariants usuels. Il est remarquable que l'anneau $\mathbf{QI_m}(G)$ est librement généré sur l'idéal engendré par les invariants de $G$ sans terme constant, et le quotient est isomorphe à la représentation régulière à gauche de $G$. Cependant, même dans le cas du groupe symétrique, aucune base de $\mathbf{QI_m}(G)$ n'est connue. Nous donnons une nouvelle description de $\mathbf{QI_m}(G)$ et l'utilisons pour obtenir une base du composant isotypique de $\mathbf{QI_m}(S_n)$ indexée par la partition $(n-1,1)$.
Enumerating alternating tree families
Authors: Kuba Markus , Panholzer Alois 
Published: August 2021

We study two enumeration problems for $\textit{up-down alternating trees}$, i.e., rooted labelled trees $T$, where the labels $ v_1, v_2, v_3, \ldots$ on every path starting at the root of $T$ satisfy $v_1 < v_2 > v_3 < v_4 > \cdots$. First we consider various tree families of interest in combinatorics (such as unordered, ordered, $d$-ary and Motzkin trees) and study the number $T_n$ of different up-down alternating labelled trees of size $n$. We obtain for all tree families considered an implicit characterization of the exponential generating function $T(z)$ leading to asymptotic results of the coefficients $T_n$ for various tree families. Second we consider the particular family of up-down alternating labelled ordered trees and study the influence of such an alternating labelling to the average shape of the trees by analyzing the parameters $\textit{label of the root node}$, $\textit{degree of the root node}$ and $\textit{depth of a random node}$ in a random tree of size $n$. This leads to exact enumeration results and limiting distribution results.
Nous étudions deux problèmes de dénombrement d'$\textit{arbres alternés haut-bas}$ : par définition, ce sont des arbres munis d'une racine et tels que, pour tout chemin partant de la racine, les valeurs $v_1,v_2,v_3,\ldots$ associées aux nœuds du chemin satisfont la chaîne d'inégalités $v_1 < v_2 > v_3 < v_4 > \cdots$. D'une part, nous considérons diverses familles d'arbres intéressantes du point de vue de l'analyse combinatoire (comme les arbres de Motzkin, les arbres non ordonnés, ordonnés et $d$-aires) et nous étudions pour chaque famille le nombre total $T_n$ d'arbres alternés haut-bas de taille $n$. Nous obtenons pour toutes les familles d'arbres considérées une caractérisation implicite de la fonction génératrice exponentielle $T(z)$. Cette caractérisation nous renseigne sur le comportement asymptotique des coefficients $T_n$ de plusieurs familles d'arbres. D'autre part, nous examinons le cas particulier de la famille des arbres ordonnés : nous étudions l'influence de l'étiquetage alterné haut-bas sur l'allure générale de ces arbres en analysant trois paramètres dans un arbre aléatoire (valeur de la racine, degré de la racine et profondeur d'un nœud aléatoire). Nous obtenons alors des résultats en terme de distribution limite, mais aussi de dénombrement exact.
Combinatorial interpretation and positivity of Kerov's character polynomials
Authors: Féray Valentin 
Published: August 2021

Kerov's polynomials give irreducible character values of the symmetric group in term of the free cumulants of the associated Young diagram. Using a combinatorial approach with maps, we prove in this article a positivity result on their coefficients, which extends a conjecture of S. Kerov.
Les polynômes de Kerov expriment les valeurs des caractères irréductibles du groupe symétrique en fonction des cumulants libres du diagramme de Young associé. Grâce à une approche combinatoire à base de cartes, nous prouvons dans cet article un résultat de positivité sur leurs coefficients, qui généralise une conjecture de S. Kerov.
Pattern avoidance in dynamical systems
Authors: Amigó José María , Elizalde Sergi , Kennel Matthew B. 
Published: August 2021

Orbits generated by discrete-time dynamical systems have some interesting combinatorial properties. In this paper we address the existence of forbidden order patterns when the dynamics is generated by piecewise monotone maps on one-dimensional closed intervals. This means that the points belonging to a sufficiently long orbit cannot appear in any arbitrary order. The admissible patterns are then (the inverses of) those permutations avoiding the so-called forbidden root patterns in consecutive positions. The last part of the paper studies and enumerates forbidden order patterns in shift systems, which are universal models in information theory, dynamical systems and stochastic processes. In spite of their simple structure, shift systems exhibit all important features of low-dimensional chaos, allowing to export the results to other dynamical systems via order-isomorphisms. This paper summarizes some results from [1] and [11].
Les orbites générées par des systèmes dynamiques à temps discret ont quelques propriétés combinatoires intéressantes. Dans cet article on adresse l’existence de motifs d’ordre exclus quand la dynamique est générée par des applications monotones à parts sur des intervalles fermés en une dimension. Ceci signifie que les points appartenant à une orbite suffisamment longue ne peuvent pas apparaître dans un ordre arbitraire. Les motifs admissibles sont alors (les inverses de) ces permutations qui évitent les motifs exclus fondamentaux en positions consécutives. La dernière partie de l’article étudie et énumère les motifs exclus dans les systèmes de déplacement, qui sont des modèles universels dans la théorie de l’information, les systèmes dynamiques et les processus stochastiques. Malgré leur structure simple, les systèmes de déplacement manifestent toutes les propriétés importantes du chaos en basse dimension, permettant exporter les résultats aux autres systèmes dynamiques via des isomorphismes d’ordre. Cet article résume quelques résultats de [1] et [11].
Nested Hilbert Schemes and the nested $q,t$-Catalan series
Authors: Can Mahir Bilen 
Published: August 2021

In this paper we study the tangent spaces of the smooth nested Hilbert scheme $\mathrm{Hilb}^{n,n-1}(\mathbb{A}^2)$ of points in the plane, and give a general formula for computing the Euler characteristic of a $\mathbb{T}^2$-equivariant locally free sheaf on $\mathrm{Hilb}^{n,n-1}(\mathbb{A}^2)$. Applying our result to a particular sheaf, we conjecture that the result is a polynomial in the variables $q$ and $t$ with non-negative integer coefficients. We call this conjecturally positive polynomial as the "nested $q,t$-Catalan series,'' for it has many conjectural properties similar to that of the $q,t$-Catalan series.
Dans cet article, nous étudions les espaces tangents du schéma de Hilbert emboité lisse $\mathrm{Hilb}^{n,n-1}(\mathbb{A}^2)$ de points du plan, et donnons une formule générale pour le calcul de la caractéristique d’Euler d’un faisceau $\mathbb{T}^2$-équivariant localement libre sur $\mathrm{Hilb}^{n,n-1}(\mathbb{A}^2)$. En appliquant notre resultat a un faisceau particulier, nous conjecturons que le résultat est un polynôme en$q$ et $t$ à coefficents positifs ou nuls. Nous appelons ce polynôme conjecturalement positif la “série de $q; t$-Catalan emboîtée”, car il a de nombreuses propriétés (conjecturées) similaires à celles de la série de $q; t$-Catalan.
Polyominoes determined by involutions
Authors: Disanto Filippo , Rinaldi Simone 
Published: August 2021

A permutomino of size n is a polyomino determined by particular pairs $(\pi_1, \pi_2)$ of permutations of length $n$, such that $\pi_1(i) \neq \pi_2(i)$, for $1 \leq i \leq n$. In this paper we consider the class of convex permutominoes which are symmetric with respect to the diagonal $x = y$. We determine the number of these permutominoes according to the dimension and we characterize the class of permutations associated to these objects as particular involutions of length $n$.
Les permutominos de taille $n$ sont des polyominos déterminés par certaines paires de permutations $(\pi_1,\pi_2)$ de taille $n$, telles que $\pi_1(i) \neq \pi_2(i)$, pour tout $1 \leq i \leq n$. Dans cet article nous considérons la classe des permutominos convexes qui sont symétriques par rapport à la diagonale $x=y$. Nous déterminons le nombre de ces permutominos en fonction de leur taille et nous caractérisons la classe des permutations associées à ces objets comme un certain ensemble d'involutions de taille $n$.