bluuebunny/crossref_metadata_2025 huggingface dataset:
Pattern avoidance in partial permutations (extended abstract)
Authors: Claesson Anders , Jelínek Vít , Jelínková Eva , Kitaev Sergey
Published: August 2021

Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A $\textit{partial permutation of length n with k holes}$ is a sequence of symbols $\pi = \pi_1 \pi_2 \cdots \pi_n$ in which each of the symbols from the set $\{1,2,\ldots,n-k\}$ appears exactly once, while the remaining $k$ symbols of $\pi$ are "holes''. We introduce pattern-avoidance in partial permutations and prove that most of the previous results on Wilf equivalence of permutation patterns can be extended to partial permutations with an arbitrary number of holes. We also show that Baxter permutations of a given length $k$ correspond to a Wilf-type equivalence class with respect to partial permutations with $(k-2)$ holes. Lastly, we enumerate the partial permutations of length $n$ with $k$ holes avoiding a given pattern of length at most four, for each $n \geq k \geq 1$.

Nous introduisons un concept de permutations partielles. $\textit{Une permutation partielle de longueur n avec k trous}$ est une suite finie de symboles $\pi = \pi_1 \pi_2 \cdots \pi_n$ dans laquelle chaque nombre de l'ensemble $\{1,2,\ldots,n-k\}$ apparaît précisément une fois, tandis que les $k$ autres symboles de $\pi$ sont des "trous''. Nous introduisons l'étude des permutations partielles à motifs exclus et nous montrons que la plupart des résultats sur l'équivalence de Wilf peuvent être généralisés aux permutations partielles avec un nombre arbitraire de trous. De plus, nous montrons que les permutations de Baxter d'une longueur donnée $k$ forment une classe d'équivalence du type Wilf par rapport aux permutations partielles avec $(k-2)$ trous. Enfin, nous présentons l'énumération des permutations partielles de longueur $n$ avec $k$ trous qui évitent un motif de longueur $\ell \leq 4$, pour chaque $n \geq k \geq 1$.
Sums of Digits, Overlaps, and Palindromes
Authors: Allouche Jean-Paul , Shallit Jeffrey
Published: August 2021

Let s_k(n) denote the sum of the digits in the base-k representation of n. In a celebrated paper, Thue showed that the infinite word (s_2(n) \bmod 2)_n≥ 0 is \emphoverlap-free, i.e., contains no subword of the form axaxa where x is any finite word and a is a single symbol. Let k,m be integers with k>2, m≥ 1. In this paper, generalizing Thue's result, we prove that the infinite word t_k,m := (s_k(n) \bmod m)_n≥ 0 is overlap-free if and only if m≥ k. We also prove that t_k,m contains arbitrarily long squares (i.e., subwords of the form xx where x is nonempty), and contains arbitrarily long palindromes if and only if m≤ 2.
Tropical secant graphs of monomial curves
Authors: Cueto María Angélica , Lin Shaowei
Published: August 2021

We construct and study an embedded weighted balanced graph in $\mathbb{R}^{n+1}$ parametrized by a strictly increasing sequence of $n$ coprime numbers $\{ i_1, \ldots, i_n\}$, called the $\textit{tropical secant surface graph}$. We identify it with the tropicalization of a surface in $\mathbb{C}^{n+1}$ parametrized by binomials. Using this graph, we construct the tropicalization of the first secant variety of a monomial projective curve with exponent vector $(0, i_1, \ldots, i_n)$, which can be described by a balanced graph called the $\textit{tropical secant graph}$. The combinatorics involved in computing the degree of this classical secant variety is non-trivial. One earlier approach to this is due to K. Ranestad. Using techniques from tropical geometry, we give algorithms to effectively compute this degree (as well as its multidegree) and the Newton polytope of the first secant variety of any given monomial curve in $\mathbb{P}^4$.

On construit et on étude un graphe plongé dans $\mathbb{R}^{n+1}$ paramétrisé par une suite strictement croissante de $n$ nombres entiers $\{ i_1, \ldots, i_n\}$, premiers entre eux. Ce graphe s'appelle $\textit{graphe tropical surface sécante}$. On montre que ce graphe est la tropicalisation d'une surface dans $\mathbb{C}^{n+1}$ paramétrisé par des binômes. On utilise ce graphe pour construire la tropicalisation de la première sécante d'une courbe monomiale ayant comme vecteur d'exponents $(0, i_1, \ldots, i_n)$. On représente cette variété tropicale pour un graphe balancé (le $\textit{graphe tropical sécante}$). La combinatoire qu'on utilise pour le calcul du degré de ces variétés sécantes classiques n'est pas triviale, et a été developpée par K. Ranestad. En utilisant des techniques de la géométrie tropicale, on donne des algorithmes qui calculent le degré (même le multidegré) et le polytope de Newton de la première sécante d'une courbe monomiale de $\mathbb{P}^4$.
A Combinatorial Formula for Orthogonal Idempotents in the $0$-Hecke Algebra of $S_N$
Authors: Denton Tom
Published: August 2021

Building on the work of P.N. Norton, we give combinatorial formulae for two maximal decompositions of the identity into orthogonal idempotents in the $0$-Hecke algebra of the symmetric group, $\mathbb{C}H_0(S_N)$. This construction is compatible with the branching from $H_0(S_{N-1})$ to $H_0(S_N)$.

En s'appuyant sur le travail de P.N. Norton, nous donnons des formules combinatoires pour deux décompositions maximales de l'identité en idempotents orthogonaux dans l'algèbre de Hecke $H_0(S_N)$ du groupe symétrique à $q=0$. Ces constructions sont compatibles avec le branchement de $H_0(S_{N-1})$ à $H_0(S_N)$.
Crossings and nestings in set partitions of classical types
Authors: Rubey Martin , Stump Christian
Published: August 2021

In this extended abstract, we investigate bijections on various classes of set partitions of classical types that preserve openers and closers. On the one hand we present bijections for types $B$ and $C$ that interchange crossings and nestings, which generalize a construction by Kasraoui and Zeng for type $A$. On the other hand we generalize a bijection to type $B$ and $C$ that interchanges the cardinality of a maximal crossing with the cardinality of a maximal nesting, as given by Chen, Deng, Du, Stanley and Yan for type $A$. For type $D$, we were only able to construct a bijection between non-crossing and non-nesting set partitions. For all classical types we show that the set of openers and the set of closers determine a non-crossing or non-nesting set partition essentially uniquely.

Dans ce résumé, nous étudions des bijections entre diverses classes de partitions d'ensemble de types classiques qui préservent les "openers'' et les "closers''. D'une part, nous présentons des bijections pour les types $B$ et $C$ qui échangent croisées et emboôtées, qui généralisent une construction de Kasraoui et Zeng pour le type $A$. D'autre part, nous généralisons une bijection pour le type $B$ et $C$ qui échange la cardinalité d'un croisement maximal avec la cardinalité d'un emboîtement maximal comme il a été fait par Chen, Deng, Du, Stanley et Yan pour le type $A$. Pour le type $D$, nous avons seulement construit une bijection entre les partitions non croisées et non emboîtées. Pour tout les types classiques, nous montrons que l'ensemble des "openers'' et l'ensemble des "closers'' déterminent une partition non croisées ou non emboîtées essentiellement de façon unique.
Cyclic sieving for longest reduced words in the hyperoctahedral group
Authors: Petersen T. K. , Serrano L.
Published: August 2021

We show that the set $R(w_0)$ of reduced expressions for the longest element in the hyperoctahedral group exhibits the cyclic sieving phenomenon. More specifically, $R(w_0)$ possesses a natural cyclic action given by moving the first letter of a word to the end, and we show that the orbit structure of this action is encoded by the generating function for the major index on $R(w_0)$.

Nous montrons que l'ensemble $R(w_0)$ des expressions réduites pour l'élément le plus long du groupe hyperoctaédral présente le phénomène cyclique de tamisage. Plus précisément, $R(w_0)$ possède une action naturelle cyclique donnée par le déplacement de la première lettre d'un mot vers la fin, et nous montrons que la structure d'orbite de cette action est codée par la fonction génératrice pour l'indice majeur sur $R(w_0)$.
Bijective enumeration of permutations starting with a longest increasing subsequence
Authors: Panova Greta
Published: August 2021

We prove a formula for the number of permutations in $S_n$ such that their first $n-k$ entries are increasing and their longest increasing subsequence has length $n-k$. This formula first appeared as a consequence of character polynomial calculations in recent work of Adriano Garsia and Alain Goupil. We give two "elementary' bijective proofs of this result and of its q-analogue, one proof using the RSK correspondence and one only permutations.

Nous prouvons une formule pour le nombre des permutations dans $S_n$ dont les premiers $n-k$ entrées sont croissantes et dont la plus longue sous-suite croissante est de longueur $n-k$. Cette formule est d'abord apparue en conséquence de calculs sur les polynômes caractères des travaux récents de Adriano Garsia et Alain Goupil. Nous donnons deux preuves bijectifs "élémentaires" de cet résultat et de son q-analogue, une preuve employant le correspondance RSK et une autre n'employant que les permutations.
A unification of permutation patterns related to Schubert varieties
Authors: Úlfarsson Henning A.
Published: August 2021

We prove new connections between permutation patterns and singularities of Schubert varieties, by giving a new characterization of factorial and Gorenstein varieties in terms of so called bivincular patterns. These are generalizations of classical patterns where conditions are placed on the location of an occurrence in a permutation, as well as on the values in the occurrence. This clarifies what happens when the requirement of smoothness is weakened to factoriality and further to Gorensteinness, extending work of Bousquet-Mélou and Butler (2007), and Woo and Yong (2006). We also prove results that translate some known patterns in the literature into bivincular patterns.

Nous démontrons de nouveaux liens entre les motifs de permutation et les singularités des variétés de Schubert, par la méthode de donner une nouvelle caractérisation des variétés factorielles et de Gorenstein par rapport à les motifs bivinculaires. Ces motifs sont généralisations des motifs classiques où des conditions se posent sur la position d'une occurrence dans une permutation, aussi bien que sur les valeurs qui se présentent dans l'occurrence. Ceci éclaircit les phénomènes où la condition de nonsingularité s'affaiblit á factorialité et même à Gorensteinité, et augmente les travaux de Bousquet-Mélou et Butler (2007), et de Woo et Yong (2006). Nous démontrons également des résultats qui traduisent quelques motifs connus en la littérature en motifs bivinculaires.
Boolean complexes and boolean numbers
Authors: Tenner Bridget Eileen
Published: August 2021

The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of these spheres is the boolean number, which can be computed inductively from the unlabeled Coxeter system, thus defining a graph invariant. For certain families of graphs, the boolean numbers have intriguing combinatorial properties. This work involves joint efforts with Claesson, Kitaev, and Ragnarsson. \par

L'ordre de Bruhat munit tout groupe de Coxeter d'une structure de poset. L'idéal composé des éléments de ce poset engendrant des idéaux principaux ordonnés booléens, forme un poset simplicial. Ce poset simplicial définit le complexe booléen pour le groupe. Dans un système de Coxeter de rang n, nous montrons que le complexe booléen est homotopiquement équivalent à un bouquet de sphères de dimension (n-1). Le nombre de ces sphères est le nombre booléen, qui peut être calculé inductivement à partir du système de Coxeter non-étiquetté; définissant ainsi un invariant de graphe. Pour certaines familles de graphes, les nombres booléens satisfont des propriétés combinatoires intriguantes. Ce travail est une collaboration entre Claesson, Kitaev, et Ragnarsson.
Equivalence Relations of Permutations Generated by Constrained Transpositions
Authors: Linton Stephen , Propp James , Roby Tom , West Julian
Published: August 2021

We consider a large family of equivalence relations on permutations in $S_n$ that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of pattern-replacing moves of prescribed form; however, we limit our focus to patterns where two elements are transposed, conditional upon the presence of a third element of suitable value and location. For some relations of this type, we compute the number of equivalence classes, determine how many $n$-permutations are equivalent to the identity permutation, or characterise this equivalence class. Although our results include familiar integer sequences (e.g., Catalan, Fibonacci, and Tribonacci numbers) and special classes of permutations (layered, connected, and $123$-avoiding), some of the sequences that arise appear to be new.

Nous considérons une famille de relations d’équivalence sur l'ensemble $S_n$ des permutations, qui généralisent les relations de Knuth liées à la correspondance Robinson-Schensted. Dans notre contexte général, deux permutations sont considérées comme équivalentes si l'une peut être obtenue de l'autre auprès d'une séquence de remplacements d'un motif par un autre selon des règles précisées. Désormais, nous ne considérons dans l’œuvre actuelle que les motifs qui correspondent à la transposition de deux éléments, conditionné sur la présence d'un élément de valeur et de position approprié. Pour plusieurs exemples de ce problème, nous énumérons les classes d'équivalence, nous déterminons combien de permutations sur $n$ éléments sont équivalentes à l'identité, ou nous précisons la forme des éléments dans cette dernière classe. Bien que nos résultats retrouvent des séquences des entiers très bien connues (nombres de Catalan, de Fibonacci, de Tribonacci...) ainsi que des classes de permutations déjà étudiées (en couches, connexes, sans motif $123$), nous trouvons également des séquences qui paraissent être nouvelles.
Mixed Statistics on $01$-Fillings of Moon Polyominoes
Authors: Chen William Y. C. , Wang Andrew Y. Z. , Yan Catherine H. , Zhao Alina F. Y.
Published: August 2021

We establish a stronger symmetry between the numbers of northeast and southeast chains in the context of $01$-fillings of moon polyominoes. Let $\mathcal{M}$ be a moon polyomino. Consider all the $01$-fillings of $\mathcal{M}$ in which every row has at most one $1$. We introduce four mixed statistics with respect to a bipartition of rows or columns of $\mathcal{M}$. More precisely, let $S$ be a subset of rows of $\mathcal{M}$. For any filling $M$, the top-mixed (resp. bottom-mixed) statistic $\alpha (S; M)$ (resp. $\beta (S; M)$) is the sum of the number of northeast chains whose top (resp. bottom) cell is in $S$, together with the number of southeast chains whose top (resp. bottom) cell is in the complement of $S$. Similarly, we define the left-mixed and right-mixed statistics $\gamma (T; M)$ and $\delta (T; M)$, where $T$ is a subset of the columns. Let $\lambda (A; M)$ be any of these four statistics $\alpha (S; M)$, $\beta (S; M)$, $\gamma (T; M)$ and $\delta (T; M)$. We show that the joint distribution of the pair $(\lambda (A; M), \lambda (M/A; M))$ is symmetric and independent of the subsets $S, T$. In particular, the pair of statistics $(\lambda (A;M), \lambda (M/A; M))$ is equidistributed with $(\mathrm{se}(M), \mathrm{ne}(M))$, where $\mathrm{se}(M)$ and $\mathrm{ne}(M)$ are the numbers of southeast chains and northeast chains of $M$, respectively.

Nous établissons une symétrie plus forte entre les nombres de chaînes nord-est et sud-est dans le cadre des remplissages $01$ des polyominos lune. Soit $\mathcal{M}$ un polyomino lune. Considérez tous les remplissages $01$ de $\mathcal{M}$ dans lesquels chaque rangée contient au plus un $1$. Nous présentons quatre statistiques mixtes sur les bipartitions des rangées et des colonnes de $\mathcal{M}$. Plus précisément, soit $S$ un sous-ensemble de rangées de $\mathcal{M}$. Pour tout remplissage $M$, la statistique mixte du dessus (resp. du dessous) $\alpha (S; M)$ (resp. $\beta (S; M)$) est la somme du nombre de chaînes nord-est dont le dessus (resp. le dessous) est dans $S$, et du nombre de chaînes sud-est dont la cellule supérieure (resp. inférieure) est dans le complément de $S$. De même, nous définissons les statistiques mixtes à gauche et à droite $\gamma (T; M)$ et $\delta (T; M)$, où $T$ est un sous-ensemble des colonnes. Soit $\lambda (A; M)$ une des quatre statistiques$\alpha (S; M)$, $\beta (S; M)$, $\gamma (T; M)$ et $\delta (T; M)$. Nous montrons que la distribution commune des paires $(\lambda (A; M), \lambda (M/A; M))$ est symétrique et indépendante des sous-ensembles $S, T$. En particulier, la paire de statistiques $(\lambda (A;M), \lambda (M/A; M))$ est équidistribuée avec $(\mathrm{se}(M), \mathrm{ne}(M))$, où $\mathrm{se}(M)$ et $\mathrm{ne}(M)$ sont les nombres de chaînes sud-est et nord-est de $M$ respectivement.
On joint distribution of adjacencies, descents and some Mahonian statistics
Authors: Burstein Alexander
Published: August 2021

We prove several conjectures of Eriksen regarding the joint distribution on permutations of the number of adjacencies (descents with consecutive values in consecutive positions), descents and some Mahonian statistics. We also prove Eriksen's conjecture that a certain bistatistic on Viennot's alternative tableaux is Euler-Mahonian.

Nous démontrons plusieurs conjectures d'Eriksen concernant la distribution conjointe sur les permutations du nombre de contiguïtés (descentes avec des valeurs consécutives en positions consécutives), les descentes et quelques statistiques mahoniennes. Nous démontrons également une conjecture d'Eriksen qui affirme qu'une certaine bistatistique sur les tableaux alternatifs de Viennot est euler-mahonienne.
Valuative invariants for polymatroids
Authors: Derksen Harm , Fink Alex
Published: August 2021

Many important invariants for matroids and polymatroids, such as the Tutte polynomial, the Billera-Jia-Reiner quasi-symmetric function, and the invariant $\mathcal{G}$ introduced by the first author, are valuative. In this paper we construct the $\mathbb{Z}$-modules of all $\mathbb{Z}$-valued valuative functions for labelled matroids and polymatroids on a fixed ground set, and their unlabelled counterparts, the $\mathbb{Z}$-modules of valuative invariants. We give explicit bases for these modules and for their dual modules generated by indicator functions of polytopes, and explicit formulas for their ranks. Our results confirm a conjecture of the first author that $\mathcal{G}$ is universal for valuative invariants.

Beaucoup des invariants importants des matroïdes et polymatroïdes, tels que le polynôme de Tutte, la fonction quasi-symmetrique de Billera-Jia-Reiner, et l'invariant $\mathcal{G}$ introduit par le premier auteur, sont valuatifs. Dans cet article nous construisons les $\mathbb{Z}$-modules de fonctions valuatives aux valeurs entières des matroïdes et polymatroïdes étiquetés définis sur un ensemble fixe, et leurs équivalents pas étiquetés, les $\mathbb{Z}$-modules des invariants valuatifs. Nous fournissons des bases des ces modules et leurs modules duels, engendrés par fonctions caractéristiques des polytopes, et des formules explicites donnant leurs rangs. Nos résultats confirment une conjecture du premier auteur, que $\mathcal{G}$ soit universel pour les invariants valuatifs.
Weighted branching formulas for the hook lengths
Authors: Ciocan-Fontanine Ionuţ , Konvalinka Matjaž , Pak Igor
Published: August 2021

The famous hook-length formula is a simple consequence of the branching rule for the hook lengths. While the Greene-Nijenhuis-Wilf probabilistic proof is the most famous proof of the rule, it is not completely combinatorial, and a simple bijection was an open problem for a long time. In this extended abstract, we show an elegant bijective argument that proves a stronger, weighted analogue of the branching rule. Variants of the bijection prove seven other interesting formulas. Another important approach to the formulas is via weighted hook walks; we discuss some results in this area. We present another motivation for our work: $J$-functions of the Hilbert scheme of points.

La formule bien connue de la longueur des crochets est une conséquence simple de la règle de branchement des longueurs des crochets. La preuve la plus répandue de cette règle est de nature probabiliste et est due à Greene-Njenhuis-Wilf. Elle n'est toutefois pas complètement combinatoire et une simple bijection a été pendant longtemps un problème ouvert. Dans ce résumé étendu, nous proposons un argument bijectif élégant qui démontre une version à poids plus forte de cette règle. Des variantes de cette bijection permettent d'obtenir sept autres formules intéressantes. Une autre approche importante de ces formules est via les marches des crochets à poids. Nous discutons certains résultats dans cette direction. Enfin, nous présentons aussi une autre motivation à l'origine de ce travail: les $J$-fonctions du schéma d'Hilbert des points.
A canonical basis for Garsia-Procesi modules
Authors: Blasiak Jonah
Published: August 2021

We identify a subalgebra $\widehat{\mathscr{H}}^+_n$ of the extended affine Hecke algebra $\widehat{\mathscr{H}}_n$ of type $A$. The subalgebra $\widehat{\mathscr{H}}^+_n$ is a u-analogue of the monoid algebra of $\mathcal{S}_n ⋉ℤ_≥0^n$ and inherits a canonical basis from that of $\widehat{\mathscr{H}}_n$. We show that its left cells are naturally labeled by tableaux filled with positive integer entries having distinct residues mod $n$, which we term positive affine tableaux (PAT). We then exhibit a cellular subquotient $\mathscr{R}_1^n$ of $\widehat{\mathscr{H}}^+_n$ that is a $u$-analogue of the ring of coinvariants $ℂ[y_1,\ldots,y_n]/(e_1, \ldots,e_n)$ with left cells labeled by PAT that are essentially standard Young tableaux with cocharge labels. Multiplying canonical basis elements by a certain element $*π ∈ \widehat{\mathscr{H}}^+_n$ corresponds to rotations of words, and on cells corresponds to cocyclage. We further show that $\mathscr{R}_1^n$ has cellular quotients $\mathscr{R}_λ$ that are $u$-analogues of the Garsia-Procesi modules $R_λ$ with left cells labeled by (a PAT version of) the $λ$ -catabolizable tableaux.

On définit une sous-algèbre $\widehat{\mathscr{H}}^+_n$ de l'extension affine de l'algèbre de Hecke \$\widehat{\mathscr{H}}_n$ de type $A$. La sous-algèbre $\widehat{\mathscr{H}}^+_n$ est $u$-analogue à l'algèbre monoïde de $\mathcal{S}_n ⋉ℤ_≥0^n$ et hérite d'une base canonique de $\widehat{\mathscr{H}}_n$. On montre que ses cellules gauches sont naturellement classées par des tableaux remplis d'entiers naturels ayant chacun des restes différents modulo $n$, que l'on nomme Positive Affine Tableaux (PAT). On montre ensuite qu'un sous-quotient cellulaire $\mathscr{R}_1^n$ de $\widehat{\mathscr{H}}^+_n$ est une $u$-analogue de l'anneau des co-invariants $ℂ[y_1,\ldots,y_n]/(e_1, \ldots,e_n)$ avec des cellules gauches classées PAT qui sont essentiellement des tableaux de Young standards avec des labels cochargés. Multiplier les éléments de la base canonique par un certain élément $π ∈ \widehat{\mathscr{H}}^+_n$ correspond à des rotations de mots, et par rapport aux cellules cela correspond à un cocyclage. Plus loin, on montre que $\mathscr{R}_1^n$ a pour quotients cellulaires $\mathscr{R}_λ$ qui sont $u$- analogues aux modules de Garsia-Procesi $R_λ$ avec des cellules gauches définies par (une version PAT) des tableaux $λ$ -catabolisable.
Computing Node Polynomials for Plane Curves
Authors: Block Florian
Published: August 2021

According to the Göttsche conjecture (now a theorem), the degree $N^{d, \delta}$ of the Severi variety of plane curves of degree $d$ with $\delta$ nodes is given by a polynomial in $d$, provided $d$ is large enough. These "node polynomials'' $N_{\delta} (d)$ were determined by Vainsencher and Kleiman―Piene for $\delta \leq 6$ and $\delta \leq 8$, respectively. Building on ideas of Fomin and Mikhalkin, we develop an explicit algorithm for computing all node polynomials, and use it to compute $N_{\delta} (d)$ for $\delta \leq 14$. Furthermore, we improve the threshold of polynomiality and verify Göttsche's conjecture on the optimal threshold up to $\delta \leq 14$. We also determine the first 9 coefficients of $N_{\delta} (d)$, for general $\delta$, settling and extending a 1994 conjecture of Di Francesco and Itzykson.

Selon la Conjecture de Göttsche (maintenant un Théorème), le degré $N^{d, \delta}$ de la variété de Severi des courbes planes de degré $d$ avec $\delta$ noeuds est donné par un polynôme en $d$, pour $d$ assez grand. Ces $\textit{polynômes de nœuds}$ $N_{\delta} (d)$ ont été déterminés par Vainsencher et Kleiman―Piene pour $\delta \leq 6$ et $\delta \leq 8$, respectivement. S'appuyant sur les idées de Fomin et Mikhalkin, nous développons un algorithme explicite permettant de calculer tous les polynômes de nœuds, et l'utilisons pour calculer $N_{\delta} (d)$, pour $\delta \leq 14$. De plus, nous améliorons le seuil de polynomialité et vérifions la Conjecture de Göttsche sur le seuil optimal jusqu'à $\delta \leq 14$. Nous déterminons aussi les 9 premiers coéfficients de $N_{\delta} (d)$, pour un $\delta$ quelconque, confirmant et étendant la Conjecture de Di Francesco et Itzykson de 1994.
Random Walks in the Plane
Authors: Borwein Jonathan M. , Nuyens Dirk , Straub Armin , Wan James
Published: August 2021

We study the expected distance of a two-dimensional walk in the plane with unit steps in random directions. A series evaluation and recursions are obtained making it possible to explicitly formulate this distance for small number of steps. Formulae for all the moments of a 2-step and a 3-step walk are given, and an expression is conjectured for the 4-step walk. The paper makes use of the combinatorical features exhibited by the even moments which, for instance, lead to analytic continuations of the underlying integral.

Nous étudions la distance espérée d'une marche aléatoire à deux dimensions et à pas unité dans des directions aléatoires. Nous obtenons une évaluation des séries et des récurrences qui permettent de formuler explicitement cette distance pour un petit nombre de pas. Nous donnons des formules pour tous les moments d'une marche aléatoire à 2 et à 3 pas et nous formulons une conjecture pour l'expression d'une marche à 4 pas. Pour les moments pairs, nous utilisons des relations combinatoires qui, par exemple, permettent le prolongement analytique des intégrales.
Models and refined models for involutory reflection groups and classical Weyl groups
Authors: Caselli Fabrizio , Fulci Roberta
Published: August 2021

A finite subgroup $G$ of $GL(n,\mathbb{C})$ is involutory if the sum of the dimensions of its irreducible complex representations is given by the number of absolute involutions in the group, i.e. elements $g \in G$ such that $g \bar{g}=1$, where the bar denotes complex conjugation. A uniform combinatorial model is constructed for all non-exceptional irreducible complex reflection groups which are involutory including, in particular, all infinite families of finite irreducible Coxeter groups. If $G$ is a classical Weyl group this result is much refined in a way which is compatible with the Robinson-Schensted correspondence on involutions.

Un sous-groupe fini $G$ de GL(n,ℂ) est dit involutoire si la somme des dimensions de ses représentations irréductibles complexes est donné par le nombre de involutions absolues dans le groupe, c'est-a-dire le nombre de éléments $g \in G$ tels que $g \bar{g}=1$, où le bar dénote la conjugaison complexe. Un modèle combinatoire uniforme est construit pour tous les groupes de réflexions complexes irréductibles qui sont involutoires, en comprenant, toutes les familles de groupes de Coxeter finis irréductibles. Si $G$ est un groupe de Weyl ce résultat peut se raffiner d'une manière compatible avec la correspondance de Robinson-Schensted sur les involutions.
QSym over Sym has a stable basis
Authors: Lauve Aaron , Mason Sarah K
Published: August 2021

We prove that the subset of quasisymmetric polynomials conjectured by Bergeron and Reutenauer to be a basis for the coinvariant space of quasisymmetric polynomials is indeed a basis. This provides the first constructive proof of the Garsia―Wallach result stating that quasisymmetric polynomials form a free module over symmetric polynomials and that the dimension of this module is $n!$.

Nous prouvons que le sous-ensemble des polynômes quasisymétriques conjecturé par Bergeron et Reutenauer pour former une base pour l'espace coinvariant des polynômes quasisymétriques est en fait une base. Cela fournit la première preuve constructive du résultat de Garsia―Wallach indiquant que les polynômes quasisymétriques forment un module libre sur les polynômes symétriques et que la dimension de ce module est $n!$.
Combinatorial aspects of Escher tilings
Authors: Massé Alexandre Blondin , Brlek Srecko , Labbé Sébastien
Published: August 2021

In the late 30's, Maurits Cornelis Escher astonished the artistic world by producing some puzzling drawings. In particular, the tesselations of the plane obtained by using a single tile appear to be a major concern in his work, drawing attention from the mathematical community. Since a tile in the continuous world can be approximated by a path on a sufficiently small square grid - a widely used method in applications using computer displays - the natural combinatorial object that models the tiles is the polyomino. As polyominoes are encoded by paths on a four letter alphabet coding their contours, the use of combinatorics on words for the study of tiling properties becomes relevant. In this paper we present several results, ranging from recognition of these tiles to their generation, leading also to some surprising links with the well-known sequences of Fibonacci and Pell.

Lorsque Maurits Cornelis Escher commença à la fin des années 30 à produire des pavages du plan avec des tuiles, il étonna le monde artistique par la singularité de ses dessins. En particulier, les pavages du plan obtenus avec des copies d'une seule tuile apparaissent souvent dans son œuvre et ont attiré peu à peu l'attention de la communauté mathématique. Puisqu'une tuile dans le monde continu peut être approximée par un chemin sur un réseau carré suffisamment fin - une méthode universellement utilisée dans les applications utilisant des écrans graphiques - l'objet combinatoire qui modèle adéquatement la tuile est le polyomino. Comme ceux-ci sont naturellement codés par des chemins sur un alphabet de quatre lettres, l'utilisation de la combinatoire des mots devient pertinente pour l'étude des propriétés des tuiles pavantes. Nous présentons dans ce papier plusieurs résultats, allant de la reconnaissance de ces tuiles à leur génération, conduisant à des liens surprenants avec les célèbres suites de Fibonacci et de Pell.
The stability of the Kronecker product of Schur functions
Authors: Briand Emmanuel , Orellana Rosa , Rosas Mercedes
Published: August 2021

In the late 1930's Murnaghan discovered the existence of a stabilization phenomenon for the Kronecker product of Schur functions. For $n$ large enough, the values of the Kronecker coefficients appearing in the product of two Schur functions of degree $n$ do not depend on the first part of the indexing partitions, but only on the values of their remaining parts. We compute the exact value of n when this stable expansion is reached. We also compute two new bounds for the stabilization of a particular coefficient of such a product. Given partitions $\alpha$ and $\beta$, we give bounds for all the parts of any partition $\gamma$ such that the corresponding Kronecker coefficient is nonzero. Finally, we also show that the reduced Kronecker coefficients are structure coefficients for the Heisenberg product introduced by Aguiar, Ferrer and Moreira.

Dans les années 30 Murnaghan a découvert une propriété de stabilité pour le produit de Kronecker de fonctions de Schur. En degré assez grand, les valeurs des coefficients qui aparaissent dans le produit de Kronecker de deux fonctions de Schur ne dépendent pas de la première part des partitions en indice, mais seulement des parts suivantes. Dans ce travail nous calculons la valeur exacte du degré à partir duquel ce développement stable est atteint. Nous calculons aussi deux nouvelles bornes supérieures pour la stabilisation d'un coefficient particulier d'un tel produit. Nous donnons en outre, pour $\alpha$ et $\beta$ fixés, des bornes supérieures pour toutes les parts des partition $\gamma$ rendant le coefficient de Kronecker d'indices $\alpha$, $\beta$, $\gamma$ non―nul. Finalement, nous identifions les coefficients de Kronecker réduits comme des constantes de structures pour le produit de Heisenberg de fonctions symétriques défini par Aguiar, Ferrer et Moreira.
On $k$-crossings and $k$-nestings of permutations
Authors: Burrill Sophie , Mishna Marni , Post Jacob
Published: August 2021

We introduce $k$-crossings and $k$-nestings of permutations. We show that the crossing number and the nesting number of permutations have a symmetric joint distribution. As a corollary, the number of $k$-noncrossing permutations is equal to the number of $k$-nonnesting permutations. We also provide some enumerative results for $k$-noncrossing permutations for some values of $k$.

Nous introduisons les $k$-chevauchement d'arcs et les $k$-empilements d'arcs de permutations. Nous montrons que l'index de chevauchement et l'index de empilement ont une distribution conjointe symétrique pour les permutations de taille $n$. Comme corollaire, nous obtenons que le nombre de permutations n'ayant pas un $k$-chevauchement est égal au nombre de permutations n'ayant un $k$-empilement. Nous fournissons également quelques résultats énumératifs.
The Geometry of Lecture Hall Partitions and Quadratic Permutation Statistics
Authors: Bright Katie L. , Savage Carla D.
Published: August 2021

We take a geometric view of lecture hall partitions and anti-lecture hall compositions in order to settle some open questions about their enumeration. In the process, we discover an intrinsic connection between these families of partitions and certain quadratic permutation statistics. We define some unusual quadratic permutation statistics and derive results about their joint distributions with linear statistics. We show that certain specializations are equivalent to the lecture hall and anti-lecture hall theorems and another leads back to a special case of a Weyl group generating function that "ought to be better known.''

Nous regardons géométriquement les partitions amphithéâtre et les compositions planétarium afin de résoudre quelques questions énumératives ouvertes. Nous découvrons un lien intrinsèque entre ces familles des partitions et certaines statistiques quadratiques de permutation. Nous définissons quelques statistiques quadratiques peu communes des permutations et dérivons des résultats sur leurs distributions jointes avec des statistiques linéaires. Nous démontrons que certaines spécialisations sont équivalentes aux théorèmes amphithéâtre et planétarium. Une autre spécialisation mène à un cas spécial de la série génératrice d'un groupe de Weyl qui "devrait être mieux connue''.
Harmonics for deformed Steenrod operators (Extended Abstract)
Authors: Bergeron François , Garsia Adriano , Wallach Nolan
Published: August 2021

We explore in this paper the spaces of common zeros of several deformations of Steenrod operators. Proofs are omitted in view of pages limitation for the extended abstract. \par

Nous explorons dans cet article l'espace des zéros communs de plusieurs déformations d'opérateurs de Steenrod. Faute de place, les preuves sont omises.
Zonotopes, toric arrangements, and generalized Tutte polynomials
Authors: Moci Luca
Published: August 2021

We introduce a multiplicity Tutte polynomial $M(x,y)$, which generalizes the ordinary one and has applications to zonotopes and toric arrangements. We prove that $M(x,y)$ satisfies a deletion-restriction recurrence and has positive coefficients. The characteristic polynomial and the Poincaré polynomial of a toric arrangement are shown to be specializations of the associated polynomial $M(x,y)$, likewise the corresponding polynomials for a hyperplane arrangement are specializations of the ordinary Tutte polynomial. Furthermore, $M(1,y)$ is the Hilbert series of the related discrete Dahmen-Micchelli space, while $M(x,1)$ computes the volume and the number of integral points of the associated zonotope.

On introduit un polynôme de Tutte avec multiplicité $M(x, y)$, qui généralise le polynôme de Tutte ordinaire et a des applications aux zonotopes et aux arrangements toriques. Nous prouvons que $M(x, y)$ satisfait une récurrence de "deletion-restriction'' et a des coefficients positifs. Le polynôme caractéristique et le polynôme de Poincaré d'un arrangement torique sont des spécialisations du polynôme associé $M(x, y)$, de même que les polynômes correspondants pour un arrangement d'hyperplans sont des spécialisations du polynôme de Tutte ordinaire. En outre, $M(1, y)$ est la série de Hilbert de l'espace discret de Dahmen-Micchelli associé, et $M(x, 1)$ calcule le volume et le nombre de points entiers du zonotope associé.
Unitary Matrix Integrals, Primitive Factorizations, and Jucys-Murphy Elements
Authors: Matsumoto Sho , Novak Jonathan
Published: August 2021

A factorization of a permutation into transpositions is called "primitive'' if its factors are weakly ordered.We discuss the problem of enumerating primitive factorizations of permutations, and its place in the hierarchy of previously studied factorization problems. Several formulas enumerating minimal primitive and possibly non-minimal primitive factorizations are presented, and interesting connections with Jucys-Murphy elements, symmetric group characters, and matrix models are described.

Une factorisation en transpositions d'une permutation est dite "primitive'' si ses facteurs sont ordonnés. Nous discutons du problème de l'énumération des factorisations primitives de permutations, et de sa place dans la hiérarchie des problèmes de factorisation précédemment étudiés. Nous présentons plusieurs formules énumérant certaines classes de factorisations primitives,et nous soulignons des connexions intéressantes avec les éléments Jucys-Murphy, les caractères des groupes symétriques, et les modèles de matrices.
A Pieri rule for skew shapes
Authors: Assaf Sami H. , McNamara Peter R. W.
Published: August 2021

The Pieri rule expresses the product of a Schur function and a single row Schur function in terms of Schur functions. We extend the classical Pieri rule by expressing the product of a skew Schur function and a single row Schur function in terms of skew Schur functions. Like the classical rule, our rule involves simple additions of boxes to the original skew shape. Our proof is purely combinatorial and extends the combinatorial proof of the classical case.

La règle de Pieri exprime le produit d'une fonction de Schur et de la fonction de Schur d'une seule ligne en termes de fonctions de Schur. Nous étendons la règle classique de Pieri en exprimant le produit d'un fonction gauche de Schur et de la fonction de Schur d'une ligne en termes de fonctions gauches de Schur. Comme la règle classique, notre règle implique l'ajout de cases à la forme gauche initiale. Notre preuve est purement combinatoire et étend celle du cas classique.
Hyperplane Arrangements and Diagonal Harmonics
Authors: Armstrong Drew
Published: August 2021

In 2003, Haglund's bounce statistic gave the first combinatorial interpretation of the q,t-Catalan numbers and the Hilbert series of diagonal harmonics. In this paper we propose a new combinatorial interpretation in terms of the affine Weyl group of type A. In particular, we define two statistics on affine permutations; one in terms of the Shi hyperplane arrangement, and one in terms of a new arrangement — which we call the Ish arrangement. We prove that our statistics are equivalent to the area' and bounce statistics of Haglund and Loehr. In this setting, we observe that bounce is naturally expressed as a statistic on the root lattice. We extend our statistics in two directions: to "extended'' Shi arrangements and to the bounded chambers of these arrangements. This leads to a (conjectural) combinatorial interpretation for all integral powers of the Bergeron-Garsia nabla operator applied to elementary symmetric functions.

En 2003, la statistique bounce de Haglund a donné la première interprétation combinatoire de la somme des nombres q,t-Catalan et de la série de Hilbert des harmoniques diagonaux. Dans cet article nous proposons une nouvelle interprétation combinatoire à partir du groupe de Weyl affine de type A. En particulier, nous définissons deux statistiques sur les permutations affines; l'une à partir de l'arrangement d'hyperplans Shi, et l'autre à partir d'un nouvel arrangement — que nous appelons l'arrangement Ish. Nous prouvons que nos statistiques sont équivalentes aux statistiques area' et bounce de Haglund et Loehr. Dans ce contexte, nous observons que bounce s'exprime naturellement comme une statistique sur le réseau des racines. Nous prolongeons nos statistiques dans deux directions: arrangements Shi "étendus'', et chambres bornées associées. Cela conduit à une interprétation (conjecturale) combinatoire pour toutes les puissances entières de l'opérateur nabla de Bergeron-Garsia appliqué aux fonctions symétriques élémentaires.
A Degree-Decreasing Lemma for (MOD_q-MOD_p) Circuits
Authors: Grolmusz Vince
Published: August 2021

Consider a (MOD_q,MOD_p) circuit, where the inputs of the bottom MOD_p gates are degree-d polynomials with integer coefficients of the input variables (p, q are different primes). Using our main tool ―- the Degree Decreasing Lemma ―- we show that this circuit can be converted to a (MOD_q,MOD_p) circuit with \emphlinear polynomials on the input-level with the price of increasing the size of the circuit. This result has numerous consequences: for the Constant Degree Hypothesis of Barrington, Straubing and Thérien, and generalizing the lower bound results of Yan and Parberry, Krause and Waack, and Krause and Pudlák. Perhaps the most important application is an exponential lower bound for the size of (MOD_q,MOD_p) circuits computing the n fan-in AND, where the input of each MOD_p gate at the bottom is an \empharbitrary integer valued function of cn variables (c<1) plus an arbitrary linear function of n input variables.
The Murnaghan―Nakayama rule for k-Schur functions
Authors: Bandlow Jason , Schilling Anne , Zabrocki Mike
Published: August 2021

We prove a Murnaghan–Nakayama rule for k-Schur functions of Lapointe and Morse. That is, we give an explicit formula for the expansion of the product of a power sum symmetric function and a k-Schur function in terms of k-Schur functions. This is proved using the noncommutative k-Schur functions in terms of the nilCoxeter algebra introduced by Lam and the affine analogue of noncommutative symmetric functions of Fomin and Greene.

Nous prouvons une règle de Murnaghan-Nakayama pour les fonctions de k-Schur de Lapointe et Morse, c'est-à-dire que nous donnons une formule explicite pour le développement du produit d'une fonction symétrique "somme de puissances'' et d'une fonction de k-Schur en termes de fonctions k-Schur. Ceci est prouvé en utilisant les fonctions non commutatives k-Schur en termes d'algèbre nilCoxeter introduite par Lam et l'analogue affine des fonctions symétriques non commutatives de Fomin et Greene.
Enumerating projective reflection groups
Authors: Biagioli Riccardo , Caselli Fabrizio
Published: August 2021

Projective reflection groups have been recently defined by the second author. They include a special class of groups denoted G(r,p,s,n) which contains all classical Weyl groups and more generally all the complex reflection groups of type G(r,p,n). In this paper we define some statistics analogous to descent number and major index over the projective reflection groups G(r,p,s,n), and we compute several generating functions concerning these parameters. Some aspects of the representation theory of G(r,p,s,n), as distribution of one-dimensional characters and computation of Hilbert series of some invariant algebras, are also treated.

Les groupes de réflexions projectifs ont été récemment définis par le deuxième auteur. Ils comprennent une classe spéciale de groupes notée G(r,p,s,n), qui contient tous les groupes de Weyl classiques et plus généralement tous les groupes de réflexions complexes du type G(r,p,n). Dans ce papier on définit des statistiques analogues au nombre de descentes et à l'indice majeur pour les groupes G(r,p,s,n), et on calcule plusieurs fonctions génératrices. Certains aspects de la théorie des représentations de G(r,p,s,n), comme la distribution des caractères linéaires et le calcul de la série de Hilbert de quelques algèbres d'invariants, sont aussi abordés.
Finite Eulerian posets which are binomial or Sheffer
Authors: Bidkhori Hoda
Published: August 2021

In this paper we study finite Eulerian posets which are binomial or Sheffer. These important classes of posets are related to the theory of generating functions and to geometry. The results of this paper are organized as follows: (1) We completely determine the structure of Eulerian binomial posets and, as a conclusion, we are able to classify factorial functions of Eulerian binomial posets; (2) We give an almost complete classification of factorial functions of Eulerian Sheffer posets by dividing the original question into several cases; (3) In most cases above, we completely determine the structure of Eulerian Sheffer posets, a result stronger than just classifying factorial functions of these Eulerian Sheffer posets. We also study Eulerian triangular posets. This paper answers questions posed by R. Ehrenborg and M. Readdy. This research is also motivated by the work of R. Stanley about recognizing the \emphboolean lattice by looking at smaller intervals.

Nous étudions les ensembles partiellement ordonnés finis (EPO) qui sont soit binomiaux soit de type Sheffer (deux notions reliées aux séries génératrices et à la géométrie). Nos résultats sont les suivants: (1) nous déterminons la structure des EPO Euleriens et binomiaux; nous classifions ainsi les fonctions factorielles de tous ces EPO; (2) nous donnons une classification presque complète des fonctions factorielles des EPO Euleriens de type Sheffer; (3) dans la plupart de ces cas, nous déterminons complètement la structure des EPO Euleriens et Sheffer, ce qui est plus fort que classifier leurs fonctions factorielles. Nous étudions aussi les EPO Euleriens triangulaires. Cet article répond à des questions de R. Ehrenborg and M. Readdy. Il est aussi motivé par le travail de R. Stanley sur la reconnaissance du treillis booléen via l'étude des petits intervalles.