bluuebunny/crossref_metadata_2025 huggingface dataset:
Gelfand―Tsetlin Polytopes and Feigin―Fourier―Littelmann―Vinberg Polytopes as Marked Poset Polytopes
Authors: Ardila Federico , Bliem Thomas , Salazar Dido
Published: August 2021

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements. Through this construction, we explain combinatorially the relationship between the Gelfand–Tsetlin polytopes (1950) and the Feigin–Fourier–Littelmann–Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand–Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin–Fourier–Littelmann–Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.

Stanley (1986) a montré que chaque ensemble fini partiellement ordonné permet de définir deux polyèdres, le polyèdre de l'ordre et le polyèdre des cha\^ınes. Ces polyèdres ont le même polynôme de Ehrhart, bien qu'ils soient tout à fait distincts du point de vue combinatoire. On généralise ce résultat à une famille plus générale de polyèdres, construits à partir d'un ensemble partiellement ordonné ayant des entiers attachés à certains de ses éléments. Par cette construction, on explique en termes combinatoires la relation entre les polyèdres de Gelfand-Tsetlin (1950) et ceux de Feigin-Fourier-Littelmann-Vinberg (2010, 2005), qui apparaissent dans la théorie des représentations des algèbres de Lie linéaires spéciales. On utilise les polyèdres de Gelfand-Tsetlin généralisés par Berenstein et Zelevinsky (1989) afin d'obtenir des analogues (conjecturés) des polytopes de Feigin-Fourier-Littelmann-Vinberg pour les algèbres de Lie symplectiques et orthogonales impaires.
Rational smoothness and affine Schubert varieties of type A
Authors: Billey Sara , Crites Andrew
Published: August 2021

The study of Schubert varieties in G/B has led to numerous advances in algebraic combinatorics and algebraic geometry. These varieties are indexed by elements of the corresponding Weyl group, an affine Weyl group, or one of their parabolic quotients. Often times, the goal is to determine which of the algebraic and topological properties of the Schubert variety can be described in terms of the combinatorics of its corresponding Weyl group element. A celebrated example of this occurs when G/B is of type A, due to Lakshmibai and Sandhya. They showed that the smooth Schubert varieties are precisely those indexed by permutations that avoid the patterns 3412 and 4231. Our main result is a characterization of the rationally smooth Schubert varieties corresponding to affine permutations in terms of the patterns 4231 and 3412 and the twisted spiral permutations.

L'étude des variétés de Schubert dans G/B a mené à plusieurs avancées en combinatoire algébrique. Ces variétés sont indexées soit par l'élément du groupe de Weyl correspondant, soit par un groupe de Weyl affine, soit par un de leurs quotients paraboliques. Souvent, le but est de déterminer quelles propriétés algébriques et topologiques des variétés de Schubert peuvent être décrites en termes des propriétés combinatoires des éléments du groupe de Weyl correspondant. Un exemple bien connu, dû à Lakshmibai et Sandhya, concerne le cas où G/B est de type A. Ils ont montré que les variétés de Schubert lisses sont exactement celles qui sont indexées par les permutations qui évitent les motifs 3412 et 4231. Notre résultat principal est une caractérisation des variétés de Schubert lisses et rationnelles qui correspondent à des permutations affines pour les motifs 4231 et 3412 et les permutations spirales tordues.
Path tableaux and combinatorial interpretations of immanants for class functions on $S_n$
Authors: Clearman Sam , Shelton Brittany , Skandera Mark
Published: August 2021

Let $χ ^λ$ be the irreducible $S_n$-character corresponding to the partition $λ$ of $n$, equivalently, the preimage of the Schur function $s_λ$ under the Frobenius characteristic map. Let $\phi ^λ$ be the function $S_n →ℂ$ which is the preimage of the monomial symmetric function $m_λ$ under the Frobenius characteristic map. The irreducible character immanant $Imm_λ {(x)} = ∑_w ∈S_n χ ^λ (w) x_1,w_1 ⋯x_n,w_n$ evaluates nonnegatively on each totally nonnegative matrix $A$. We provide a combinatorial interpretation for the value $Imm_λ (A)$ in the case that $λ$ is a hook partition. The monomial immanant $Imm_{{\phi} ^λ} (x) = ∑_w ∈S_n φ ^λ (w) x_1,w_1 ⋯x_n,w_n$ is conjectured to evaluate nonnegatively on each totally nonnegative matrix $A$. We confirm this conjecture in the case that $λ$ is a two-column partition by providing a combinatorial interpretation for the value $Imm_{{\phi} ^λ} (A)$.

Soit $χ ^λ$ le caractère irréductible de $S_n$ qui correspond à la partition λ de l'entier n, ou de manière équivalente, la préimage de la fonction de Schur $s_λ$ par l'application caractéristique de Frobenius. Soit $\phi ^λ$ la fonction $S_n →ℂ$ qui est la préimage de la fonction symétrique monomiale m_λ . La valeur du caractère irréductible immanent $Imm_λ {(x)} = ∑_w ∈S_n χ ^λ (w) x_1,w_1 ⋯x_n,w_n$ est non négative pour chaque matrice totalement non négative. Nous donnons une interprétation combinatoire de la valeur $Imm_λ (A)$ lorsque $λ$ est une partition en équerre. Stembridge a conjecturé que la valeur de l'immanent monomial $Imm_{{\phi} ^λ} (x) = ∑_w ∈S_n φ ^λ (w) x_1,w_1 ⋯x_n,w_n$ de $\phi ^λ$ est elle aussi non négative pour chaque matrice totalement non négative. Nous confirmons cette conjecture quand λ satisfait $λ _1 ≤2$, et nous donnons une interprétation combinatoire de $Imm_{{\phi} ^λ} (A)$ dans ce cas.
Critical Groups of Simplicial Complexes
Authors: Duval Art M. , Klivans Caroline J. , Martin Jeremy L.
Published: August 2021

We generalize the theory of critical groups from graphs to simplicial complexes. Specifically, given a simplicial complex, we define a family of abelian groups in terms of combinatorial Laplacian operators, generalizing the construction of the critical group of a graph. We show how to realize these critical groups explicitly as cokernels of reduced Laplacians, and prove that they are finite, with orders given by weighted enumerators of simplicial spanning trees. We describe how the critical groups of a complex represent flow along its faces, and sketch another potential interpretation as analogues of Chow groups.

Nous généralisons la théorie des groupes critiques des graphes aux complexes simpliciaux. Plus précisément, pour un complexe simplicial, nous définissons une famille de groupes abéliens en termes d'opérateurs de Laplace combinatoires, qui généralise la construction du groupe critique d'un graphe. Nous montrons comment réaliser ces groupes critiques explicitement comme conoyaux des opérateurs de Laplace réduits combinatoires, et montrons qu'ils sont finis. Leurs ordres sont obtenus en comptant (avec des poids) des arbres simpliciaux couvrants. Nous décrivons comment les groupes critiques d'un complexe représentent le flux le long de ses faces, et esquissons une autre interprétation potentielle comme analogues des groupes de Chow.
Allowed patterns of β -shifts
Authors: Elizalde Sergi
Published: August 2021

For a real number $β >1$, we say that a permutation $π$ of length $n$ is allowed (or realized) by the $β$-shift if there is some $x∈[0,1]$ such that the relative order of the sequence $x,f(x),\ldots,f^n-1(x)$, where $f(x)$ is the fractional part of $βx$, is the same as that of the entries of $π$ . Widely studied from such diverse fields as number theory and automata theory, $β$-shifts are prototypical examples of one-dimensional chaotic dynamical systems. When $β$ is an integer, permutations realized by shifts have been recently characterized. In this paper we generalize some of the results to arbitrary $β$-shifts. We describe a method to compute, for any given permutation $π$ , the smallest $β$ such that $π$ is realized by the $β$-shift.

Pour un nombre réel $β >1$, on dit qu'une permutation $π$ de longueur $n$ est permise (ou réalisée) par $β$-shift s'il existe $x∈[0,1]$ tel que l'ordre relatif de la séquence $x,f(x),\ldots,f^n-1(x)$, où $f(x)$ est la partie fractionnaire de $βx$, soit le même que celui des entrées de $π$ . Largement étudiés dans des domaines aussi divers que la théorie des nombres et la théorie des automates, les $β$-shifts sont des prototypes de systèmes dynamiques chaotiques unidimensionnels. Quand $β$ est un nombre entier, les permutations réalisées par décalages ont été récemment caractérisées. Dans cet article, nous généralisons certains des résultats au cas de $β$-shifts arbitraires. Nous décrivons une méthode pour calculer, pour toute permutation donnée $π$ , le plus petit $β$ tel que $π$ soit réalisée par $β$-shift.
A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants (condensed version)
Authors: Haglund J.
Published: August 2021

A special case of Haiman's identity [Invent. Math. 149 (2002), pp. 371–407] for the character of the quotient ring of diagonal coinvariants under the diagonal action of the symmetric group yields a formula for the bigraded Hilbert series as a sum of rational functions in $q,t$. In this paper we show how a summation identity of Garsia and Zabrocki for Macdonald polynomial Pieri coefficients can be used to transform Haiman's formula for the Hilbert series into an explicit polynomial in $q,t$ with integer coefficients. We also provide an equivalent formula for the Hilbert series as the constant term in a multivariate Laurent series.

Un cas spécial de l'identité de Haiman [Invent. Math. \textbf149 (2002), pp. 371–407] pour le caractère de l'anneau quotient des coinvariants diagonaux sous l'action du groupe symétrique fournit une formule pour la série de Hilbert bigraduée comme somme de fonctions rationnelles en q,t. Dans cet article nous montrons comment une identité de sommation de Garsia et Zabrocki pour les coefficients de Pieri des polynômes de Macdonald peut être utilisée pour transformer la formule de Haiman pour la série de Hilbert en un polynôme explicite en q,t à coefficients entiers. Nous présentons également une formule équivalente pour la série de Hilbert comme terme constant d'une série de Laurent multivariée.
Combinatorics of k-shapes and Genocchi numbers
Authors: Hivert Florent , Mallet Olivier
Published: August 2021

In this paper we present a work in progress on a conjectural new combinatorial model for the Genocchi numbers. This new model called irreducible k-shapes has a strong algebraic background in the theory of symmetric functions and leads to seemingly new features on the theory of Genocchi numbers. In particular, the natural q-analogue coming from the degree of symmetric functions seems to be unknown so far.

Dans cet article, nous présentons un travail en cours sur un nouveau modèle combinatoire conjectural pour les nombres de Genocchi. Ce nouveau modèle est celui des k-formes irréductibles, qui repose sur de solides bases algébriques en lien avec la théorie des fonctions symétriques et qui conduit à des aspects apparemment nouveaux de la théorie des nombres de Genocchi. En particulier, le q-analogue naturel venant du degré des fonctions symétriques semble inconnu jusqu'ici.
Counting self-dual interval orders
Authors: Jelínek Vít
Published: August 2021

In this paper, we first derive an explicit formula for the generating function that counts unlabeled interval orders (a.k.a. (2+2)-free posets) with respect to several natural statistics, including their size, magnitude, and the number of minimal and maximal elements. In the second part of the paper, we derive a generating function for the number of self-dual unlabeled interval orders, with respect to the same statistics. Our method is based on a bijective correspondence between interval orders and upper-triangular matrices in which each row and column has a positive entry.

Dans cet article, on obtient une expression explicite pour la fonction génératrice du nombre des ensembles partiellement ordonnés (posets) qui évitent le motif (2+2). La fonction compte ces ensembles par rapport à plusieurs statistiques naturelles, incluant le nombre d'éléments, le nombre de niveaux, et le nombre d'éléments minimaux et maximaux. Dans la deuxième partie, on obtient une expression similaire pour la fonction génératrice des posets autoduaux évitant le motif (2+2). On obtient ces résultats à l'aide d'une bijection entre les posets évitant (2+2) et les matrices triangulaires supérieures dont chaque ligne et chaque colonne contient un élément positif.
Skew quantum Murnaghan-Nakayama rule
Authors: Konvalinka Matjaž
Published: August 2021

In this extended abstract, we extend recent results of Assaf and McNamara, the skew Pieri rule and the skew Murnaghan-Nakayama rule, to a more general identity, which gives an elegant expansion of the product of a skew Schur function with a quantum power sum function in terms of skew Schur functions. We give two proofs, one completely bijective in the spirit of Assaf-McNamara's original proof, and one via Lam-Lauve-Sotille's skew Littlewood-Richardson rule.

Dans cet article nous élargissons le cadre de résultats récents de Assaf et McNamara, la règle dissymétrique de Pieri et la règle dissymétrique de Murnaghan-Nakayama, pour obtenir une identité plus générale donnant un développement élégant du produit de la fonction de Schur dissymétrique par une somme de puissances quantiques, en termes de fonctions de Schur dissymétriques. Nous donnons deux démonstrations, la première suivant l'approche de Assaf-McNamara et la deuxième par le biais de la règle dissymétrique de Littlewood-Richardson obtenue par Lam-Lauve-Sotille.
Hierarchical Zonotopal Power Ideals
Authors: Lenz Matthias
Published: August 2021

Zonotopal algebra deals with ideals and vector spaces of polynomials that are related to several combinatorial and geometric structures defined by a finite sequence of vectors. Given such a sequence $X$, an integer $k \geq -1$ and an upper set in the lattice of flats of the matroid defined by $X$, we define and study the associated $\textit{hierarchical zonotopal power ideal}$. This ideal is generated by powers of linear forms. Its Hilbert series depends only on the matroid structure of $X$. It is related to various other matroid invariants, $\textit{e. g.}$ the shelling polynomial and the characteristic polynomial. This work unifies and generalizes results by Ardila-Postnikov on power ideals and by Holtz-Ron and Holtz-Ron-Xu on (hierarchical) zonotopal algebra. We also generalize a result on zonotopal Cox modules due to Sturmfels-Xu.

La théorie de l'algèbre "zonotopique'' s'occupe d'idéaux et d'espaces vectoriels de polynômes qui ont un rapport avec plusieurs structures combinatoires et géométriques définies par des suites finies de vecteurs. Étant donné une telle suite $X$, un nombre entier $k \geq -1$ et un ensemble supérieur dans le treillis des plans du matroïde défini par $X$, nous définissons et étudions l'$\textit{idéal hiérarchique zonotopique}$, engendré par des puissances de formes linéaires. Sa série de Hilbert dépend seulement de la structure matroïdale de $X$. Il existe des relations avec d'autres invariants de matroïdes, tels que le polynôme d'épluchage et le polynôme caractéristique. Ce travail unifie et généralise des résultats d'Ardila-Postnikov sur les idéaux de puissances et de Holtz-Ron et Holtz-Ron-Xu sur l'algèbre zonotopique (hiérarchique). Nous généralisons aussi un résultat sur les modules de Cox zonotopiques, dû à Sturmfels-Xu.
Special Cases of the Parking Functions Conjecture and Upper-Triangular Matrices
Authors: Levande Paul
Published: August 2021

We examine the $q=1$ and $t=0$ special cases of the parking functions conjecture. The parking functions conjecture states that the Hilbert series for the space of diagonal harmonics is equal to the bivariate generating function of $area$ and $dinv$ over the set of parking functions. Haglund recently proved that the Hilbert series for the space of diagonal harmonics is equal to a bivariate generating function over the set of Tesler matrices–upper-triangular matrices with every hook sum equal to one. We give a combinatorial interpretation of the Haglund generating function at $q=1$ and prove the corresponding case of the parking functions conjecture (first proven by Garsia and Haiman). We also discuss a possible proof of the $t = 0$ case consistent with this combinatorial interpretation. We conclude by briefly discussing possible refinements of the parking functions conjecture arising from this research and point of view. $\textbf{Note added in proof}$: We have since found such a proof of the $t = 0$ case and conjectured more detailed refinements. This research will most likely be presented in full in a forthcoming article.

On examine les cas spéciaux $q=1$ et $t=0$ de la conjecture des fonctions de stationnement. Cette conjecture déclare que la série de Hilbert pour l'espace des harmoniques diagonaux est égale à la fonction génératrice bivariée (paramètres $area$ et $dinv$) sur l'ensemble des fonctions de stationnement. Haglund a prouvé récemment que la série de Hilbert pour l'espace des harmoniques diagonaux est égale à une fonction génératrice bivariée sur l'ensemble des matrices de Tesler triangulaires supérieures dont la somme de chaque équerre vaut un. On donne une interprétation combinatoire de la fonction génératrice de Haglund pour $q=1$ et on prouve le cas correspondant de la conjecture dans le cas des fonctions de stationnement (prouvé d'abord par Garsia et Haiman). On discute aussi d'une preuve possible du cas $t=0$, cohérente avec cette interprétation combinatoire. On conclut en discutant brièvement les raffinements possibles de la conjecture des fonctions de stationnement de ce point de vue. $\textbf{Note ajoutée sur épreuve}$: j'ai trouvé depuis cet article une preuve du cas $t=0$ et conjecturé des raffinements possibles. Ces résultats seront probablement présentés dans un article ultérieur.
Adjacent transformations in permutations
Authors: Pierrot Adeline , Rossin Dominique , West Julian
Published: August 2021

We continue a study of the equivalence class induced on $S_n$ when one is permitted to replace a consecutive set of elements in a permutation with the same elements in a different order. For each possible set of allowed replacements, we characterise and/or enumerate the set of permutations reachable from the identity. In some cases we also count the number of equivalence classes.

Nous étudions dans cet article les classes d'équivalence sur les permutations obtenues en remplaçant un ensemble consécutif de valeurs par ces même valeurs mais dans un ordre différent. Nous étudions l'ensemble des remplacements possibles de longueur 3 et pour chacun d'entre eux caractérisons et énumérons les permutations de la classe de l'identité. Pour certains ensembles, nous calculons de même le nombre de classes d'équivalence.
Submaximal factorizations of a Coxeter element in complex reflection groups
Authors: Ripoll Vivien
Published: August 2021

When $W$ is a finite reflection group, the noncrossing partition lattice $NC(W)$ of type $W$ is a very rich combinatorial object, extending the notion of noncrossing partitions of an $n$-gon. A formula (for which the only known proofs are case-by-case) expresses the number of multichains of a given length in $NC(W)$ as a generalized Fuß-Catalan number, depending on the invariant degrees of $W$. We describe how to understand some specifications of this formula in a case-free way, using an interpretation of the chains of $NC(W)$ as fibers of a "Lyashko-Looijenga covering''. This covering is constructed from the geometry of the discriminant hypersurface of $W$. We deduce new enumeration formulas for certain factorizations of a Coxeter element of $W$.

Lorsque $W$ est un groupe de réflexion fini, le treillis $NC(W)$ des partitions non-croisées de type $W$ est un objet combinatoire très riche, qui généralise la notion de partitions non-croisées d'un $n$-gone. Une formule (seulement prouvée au cas par cas à l'heure actuelle) exprime le nombre de chaînes de longueur donnée dans $NC(W)$ sous la forme d'un nombre de Fuß-Catalan généralisé, qui dépend des degrés invariants de $W$. Nous décrivons une stratégie visant à comprendre certaines spécifications de cette formule de manière uniforme, en utilisant une interprétation des chaînes de $NC(W)$ comme fibres d'un "revêtement de Lyashko-Looijenga''. Ce revêtement est construit à partir de la géométrie de l'hypersurface du discriminant de $W$. Nous en déduisons de nouvelles formules de comptage pour certaines factorisations d'un élément de Coxeter de $W$.
Asymptotics of several-partition Hurwitz numbers
Authors: Sage Marc
Published: August 2021

We derive in this paper the asymptotics of several-partition Hurwitz numbers, relying on a theorem of Kazarian for the one-partition case and on an induction carried on by Zvonkine. Essentially, the asymptotics for several partitions is the same as the one-partition asymptotics obtained by concatenating the partitions.

Dans cet article, nous donnons l'asymptotique générale des nombres de Hurwitz à plusieurs partitions, s'appuyant sur un théorème de Kazarian pour le cas d'une partition et s'inspirant d'une récurrence menée par Zvonkine. En substance, l'asymptotique pour plusieurs partitions est la même que celle à une partition obtenue en concaténant les partitions.
NOCAS : A Nonlinear Cellular Automata Based Stream Cipher
Authors: Karmakar Sandip , Chowdhury Dipanwita Roy
Published: August 2021

LFSR and NFSR are the basic building blocks in almost all the state of the art stream ciphers like Trivium and Grain-128. However, a number of attacks are mounted on these type of ciphers. Cellular Automata (CA) has recently been chosen as a suitable structure for crypto-primitives. In this work, a stream cipher is presented based on hybrid CA. The stream cipher takes 128 bit key and 128 bit initialization vector (IV) as input. It is designed to produce $\mathrm{2^{128}}$ random keystream bits and initialization phase is made faster 4 times than that of Grain-128. We also analyze the cryptographic strength of this cipher. Finally, the proposed cipher is shown to be resistant against known existing attacks.
Selfsimilarity, Simulation and Spacetime Symmetries
Authors: Nesme Vincent , Theyssier Guillaume
Published: August 2021

We study intrinsic simulations between cellular automata and introduce a new necessary condition for a CA to simulate another one. Although expressed for general CA, this condition is targeted towards surjective CA and especially linear ones. Following the approach introduced by the first author in an earlier paper, we develop proof techniques to tell whether some linear CA can simulate another linear CA. Besides rigorous proofs, the necessary condition for the simulation to occur can be heuristically checked via simple observations of typical space-time diagrams generated from finite configurations. As an illustration, we give an example of linear reversible CA which cannot simulate the identity and which is 'time-asymmetric', i.e. which can neither simulate its own inverse, nor the mirror of its own inverse.
A New Binomial Recurrence Arising in a Graphical Compression Algorithm
Authors: Choi Yongwook , Knessl Charles , Szpankowski Wojciech
Published: August 2021

In a recently proposed graphical compression algorithm by Choi and Szpankowski (2009), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down to the left subtree (say with probability $p$) or the right subtree (with probability 1-$p$). A new node is created as long as there is at least one ball in that node. Furthermore, a nonnegative integer $d$ is given, and at level $d$ or greater one ball is removed from the leftmost node before the balls move down to the next level. These steps are repeated until all balls are removed (i.e., after $n+d$ steps). Observe that when $d=∞$ the above tree can be modeled as a $\textit{trie}$ that stores $n$ independent sequences generated by a memoryless source with parameter $p$. Therefore, we coin the name $(n,d)$-tries for the tree just described, and to which we often refer simply as $d$-tries. Parameters of such a tree (e.g., path length, depth, size) are described by an interesting two-dimensional recurrence (in terms of $n$ and $d$) that – to the best of our knowledge – was not analyzed before. We study it, and show how much parameters of such a $(n,d)$-trie differ from the corresponding parameters of regular tries. We use methods of analytic algorithmics, from Mellin transforms to analytic poissonization.
Biased Boltzmann samplers and generation of extended linear languages with shuffle
Authors: Darrasse Alexis , Panagiotou Konstantinos , Roussel Olivier , Soria Michele
Published: August 2021

This paper is devoted to the construction of Boltzmann samplers according to various distributions, and uses stochastic bias on the parameter of a Boltzmann sampler, to produce a sampler with a different distribution for the size of the output. As a significant application, we produce Boltzmann samplers for words defined by regular specifications containing shuffle operators and linear recursions. This sampler has linear complexity in the size of the output, where the complexity is measured in terms of real-arithmetic operations and evaluations of generating functions.
Adaptive compression against a countable alphabet
Authors: Bontemps Dominique , Boucheron Stephane , Gassiat Elisabeth
Published: August 2021

This paper sheds light on universal coding with respect to classes of memoryless sources over a countable alphabet defined by an envelope function with finite and non-decreasing hazard rate. We prove that the auto-censuring (AC) code introduced by Bontemps (2011) is adaptive with respect to the collection of such classes. The analysis builds on the tight characterization of universal redundancy rate in terms of metric entropy by Haussler and Opper (1997) and on a careful analysis of the performance of the AC-coding algorithm. The latter relies on non-asymptotic bounds for maxima of samples from discrete distributions with finite and non-decreasing hazard rate.
The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (Extended Abstract)
Authors: Bindjeme Patrick , fill james Allen
Published: August 2021

In a continuous-time setting, Fill (2012) proved, for a large class of probabilistic sources, that the number of symbol comparisons used by $\texttt{QuickSort}$, when centered by subtracting the mean and scaled by dividing by time, has a limiting distribution, but proved little about that limiting random variable $Y$—not even that it is nondegenerate. We establish the nondegeneracy of $Y$. The proof is perhaps surprisingly difficult.
The Stack-Size of Combinatorial Tries Revisited
Authors: Nebel Markus E.
Published: August 2021

In the present paper we consider a generalized class of extended binary trees in which leaves are distinguished in order to represent the location of a key within a trie of the same structure. We prove an exact asymptotic equivalent to the average stack-size of trees with α internal nodes and β leaves corresponding to keys; we assume that all trees with the same parameters α and β have the same probability. The assumption of that uniform model is motivated for example by the usage of tries for the compression of blockcodes. Furthermore, we will prove asymptotics for the r-th moments of the stack-size and we will show that a normalized stack-size possesses a theta distribution in the limit.
Multi-cluster complexes
Authors: Ceballos Cesar , Labbé Jean-Philippe , Stump Christian
Published: August 2021

We present a family of simplicial complexes called \emphmulti-cluster complexes. These complexes generalize the concept of cluster complexes, and extend the notion of multi-associahedra of types ${A}$ and ${B}$ to general finite Coxeter groups. We study combinatorial and geometric properties of these objects and, in particular, provide a simple combinatorial description of the compatibility relation among the set of almost positive roots in the cluster complex.

Nous présentons une famille de complexes simpliciaux appelés \emphcomplexes des multi-amas. Ces complexes généralisent le concept de complexes des amas et étendent la notion de multi-associaèdre de type ${A}$ et ${B}$ aux groupes de Coxeter finis. Nous étudions des propriétés combinatoires et géométriques de ces objets et, en particulier nous fournissons une description combinatoire simple de la relation de compatibilité sur l'ensemble des racines presque positives du complexe des amas.
Excedances in classical and affine Weyl groups
Authors: Mongelli Pietro
Published: August 2021

Based on the notion of colored and absolute excedances introduced by Bagno and Garber we give an analogue of the derangement polynomials. We obtain some basic properties of these polynomials. Moreover, we define an excedance statistic for the affine Weyl groups of type $\widetilde{B}_n, \widetilde {C}_n$ and $\widetilde {D}_n$ and determine the generating functions of their distributions. This paper is inspired by one of Clark and Ehrenborg (2011) in which the authors introduce the excedance statistic for the group of affine permutations and ask if this statistic can be defined for other affine groups.

Basée sur la notion des excédances colorés et absolu introduits par Bagno and Garber, nous donnons un analogue des polynômes des dérangements. Nous obtenons quelques propriétés de base de ces polynômes. En outre, nous définissons une excédance statistique pour le groupes de Weyl affines de type $\widetilde{B}_n, \widetilde {C}_n$ et $\widetilde {D}_n$ et nous déterminons les fonctions génératrices de leurs distributions. Cet article est inspirè d'un article de Clark et Ehrenborg (2011) dans lequel les auteurs introduisent les excedances pour le groupe des permutations affine et demander si cette statistique peut être éèfinie pour les autres groupes affines.
A polynomial realization of the Hopf algebra of uniform block permutations
Authors: Maurice Rémi
Published: August 2021

Poster session

We investigate the combinatorial Hopf algebra based on uniform block permutations and we realize this algebra in terms of noncommutative polynomials in inﬁnitely many bi-letters.
Constructing neighborly polytopes and oriented matroids
Authors: Padrol Arnau
Published: August 2021

A $d$-polytope $P$ is neighborly if every subset of $\lfloor\frac{d}{2}\rfloor $vertices is a face of $P$. In 1982, Shemer introduced a sewing construction that allows to add a vertex to a neighborly polytope in such a way as to obtain a new neighborly polytope. With this, he constructed superexponentially many different neighborly polytopes. The concept of neighborliness extends naturally to oriented matroids. Duals of neighborly oriented matroids also have a nice characterization: balanced oriented matroids. In this paper, we generalize Shemer's sewing construction to oriented matroids, providing a simpler proof. Moreover we provide a new technique that allows to construct balanced oriented matroids. In the dual setting, it constructs a neighborly oriented matroid whose contraction at a particular vertex is a prescribed neighborly oriented matroid. We compare the families of polytopes that can be constructed with both methods, and show that the new construction allows to construct many new polytopes.

Un $d$-polytope $P$ est $\textit{neighborly}$ si tout sous-ensemble de $\lfloor\frac{d}{2}\rfloor $ sommets forme une face de $P$. En 1982, Shemer a introduit une construction de couture qui permet de rajouter un sommet à un polytope $\textit{neighborly}$ et d'obtenir un nouveau polytope $\textit{neighborly}$. Cette construction lui permet de construire un nombre super-exponentiel de polytopes $\textit{neighborly}$ distincts. Le concept de $\textit{neighborliness}$ s'étend naturellement aux matroïdes orientés. Les duaux de matroïdes orientés $\textit{neighborly}$ ont de plus une belle caractérisation: ce sont les matroïdes orientés équilibrés. Dans cet article, nous généralisons la construction de couture de Shemer aux matroïdes orientés, ce qui en fournit une démonstration plus simple. Par ailleurs, nous proposons une nouvelle technique qui permet de construire matroïdes orientés équilibrés. Dans le cadre dual, on obtient un matroïde $\textit{neighborly}$ dont la contraction à un sommet distinguè est un matroïde $\textit{neighborly}$ prescrit. Nous comparons les familles de polytopes qui peuvent être construites avec ces deux méthodes, et montrons que la nouvelle construction permet de construire plusieurs nouveaux polytopes.
Les polynômes eul\IeC èriens stables de type B
Authors: Visontai Mirkó , Williams Nathan
Published: August 2021

We give a multivariate analog of the type B Eulerian polynomial introduced by Brenti. We prove that this multivariate polynomial is stable generalizing Brenti's result that every root of the type B Eulerian polynomial is real. Our proof combines a refinement of the descent statistic for signed permutations with the notion of real stability—a generalization of real-rootedness to polynomials in multiple variables. The key is that our refined multivariate Eulerian polynomials satisfy a recurrence given by a stability-preserving linear operator.

Nous prèsentons un raffinement multivariè d'un polynôme eulèrien de type B dèfini par Brenti. En prouvant que ce polynôme est stable nous gènèralisons un rèsultat de Brenti selon laquel chaque racine du polynôme eulèrien de type B est rèelle. Notre preuve combine un raffinement de la statistique des descentes pour les permutations signèes avec la stabilitè—une gènèralisation de la propriètè d'avoir uniquement des racines rèelles aux polynômes en plusieurs variables. La connexion est que nos polynômes eulèriens raffinès satisfont une rècurrence donnèe par un opèrateur linèaire qui prèserve la stabilitè.
The sandpile model, polyominoes, and a $q,t$-Narayana polynomial
Authors: Dukes Mark , Le Borgne Yvan
Published: August 2021

We give a polyomino characterisation of recurrent configurations of the sandpile model on the complete bipartite graph $K_{m,n}$ in which one designated vertex is the sink. We present a bijection from these recurrent configurations to decorated parallelogram polyominoes whose bounding box is a $m×n$ rectangle. Other combinatorial structures appear in special cases of this correspondence: for example bicomposition matrices (a matrix analogue of set partitions), and (2+2)-free posets. A canonical toppling process for recurrent configurations gives rise to a path within the associated parallelogram polyominoes. We define a collection of polynomials that we call $q,t$-Narayana polynomials, the generating functions of the bistatistic $(\mathsf{area ,parabounce} )$ on the set of parallelogram polyominoes, akin to Haglund's $(\mathsf{area ,hagbounce} )$ bistatistic on Dyck paths. In doing so, we have extended a bistatistic of Egge et al. to the set of parallelogram polyominoes. This is one answer to their question concerning extensions to other combinatorial objects. We conjecture the $q,t$-Narayana polynomials to be symmetric and discuss the proofs for numerous special cases. We also show a relationship between the $q,t$-Catalan polynomials and our bistatistic $(\mathsf{area ,parabounce}) $on a subset of parallelogram polyominoes.

Pour le modèle du tas de sable sur un graphe $K_m,n$ biparti complet, on donne une description des configurations rècurrentes à l'aide d'une bijection avec des polyominos parallèlogrammes dècorès de rectangle englobant $m×n$. D'autres classes combinatoires apparaissent comme des cas particuliers de cette construction: par exemple les matrices de bicomposition et les ordres partiels évitant le motif (2+2). Un processus d'éboulement canonique des configurations récurrentes se traduit par un chemin bondissant dans le polyomino parallèlogramme associè. Nous définissons une famille de polynômes, baptisée de $q,t$-Narayana, à travers la distribution d'une paire de statistique $(\mathsf{aire, poidscheminbondissant})$ sur les polyominos parallélogrammes similaire à celle de Haglund définissant les polynômes de $q,t$-Catalan sur les chemins de Dyck. Ainsi nous étendons une paire de statistique de Egge et d'autres à l'ensemble des polynominos parallélogrammes. Cela répond à l'une de leur question sur des généralistations à d'autres objets combinatoires. Nous conjecturons que les polynômes de $q,t$-Narayana sont symétriques et discutons des preuves de plusieurs cas particuliers. Nous montrons ègalement une relation avec les polynômes de $q,t$-Catalan en restreignant notre paire de statistique à un sous-ensemble des polyominos parallélogrammes.
Fluctuations of central measures on partitions
Authors: Mèliot Pierre-Loïc
Published: August 2021

We study the fluctuations of models of random partitions $(\mathbb{P}_n,ω )_n ∈\mathbb{N}$ stemming from the representation theory of the infinite symmetric group. Using the theory of polynomial functions on Young diagrams, we establish a central limit theorem for the values of the irreducible characters $χ ^λ$ of the symmetric groups, with $λ$ taken randomly according to the laws $\mathbb{P}_n,ω$ . This implies a central limit theorem for the rows and columns of the random partitions, and these ``geometric'' fluctuations of our models can be recovered by relating central measures on partitions, generalized riffle shuffles, and Brownian motions conditioned to stay in a Weyl chamber.

Nous étudions les fluctuations de modèles de partitions aléatoires $(\mathbb{P}_n,ω )_n ∈\mathbb{N}$ issus de la théorie des représentations du groupe symétrique infini. En utilisant la théorie des fonctions polynomiales sur les diagrammes de Young, nous établissons un théorème central limite pour les valeurs des caractères irréductibles $χ ^λ$ des groupes symétriques, avec $λ$ pris aléatoirement suivant les lois $\mathbb{P}_n,ω$ . Ceci implique un théorème central limite pour les lignes et les colonnes des partitions aléatoires, et ces fluctuations ``géométriques'' de nos modèles peuvent être retrouvées en reliant les mesures centrales sur les partitions, les battages généralisés de cartes, et les mouvements browniens conditionnés à rester dans une chambre de Weyl.
Moment graphs and KL-polynomials
Authors: Lanini Martina
Published: August 2021

Motivated by a result of Fiebig (2007), we categorify some properties of Kazhdan-Lusztig polynomials via sheaves on Bruhat moment graphs. In order to do this, we develop new techniques and apply them to the combinatorial data encoded in these moment graphs.

Motivés par un résultat de Fiebig (2007), nous catégorisons certaines propriétés des polynômes de Kazhdan-Lusztig en utilisant faisceaux sur les graphes moment de Bruhat. Pour faire ça, nous développons de nouvelles techniques et les appliquons ensuite aux données combinatoires encodées dans ces graphes moment.
Noncommutative symmetric functions with matrix parameters
Authors: Lascoux Alain , Novelli Jean-Christophe , Thibon Jean-Yves
Published: August 2021

We define new families of noncommutative symmetric functions and quasi-symmetric functions depending on two matrices of parameters, and more generally on parameters associated with paths in a binary tree. Appropriate specializations of both matrices then give back the two-vector families of Hivert, Lascoux, and Thibon and the noncommutative Macdonald functions of Bergeron and Zabrocki.

Nous définissons de nouvelles familles de fonctions symétriques non-commutatives et de fonctions quasi-symétriques, dépendant de deux matrices de paramètres, et plus généralement, de paramètres associés à des chemins dans un arbre binaire. Pour des spécialisations appropriées, on retrouve les familles à deux vecteurs de Hivert-Lascoux-Thibon et les fonctions de Macdonald non-commutatives de Bergeron-Zabrocki.
Multicolored isomorphic spanning trees in complete graphs
Authors: Constantine Gregory
Published: August 2021

Can a complete graph on an even number n (>4) of vertices be properly edge-colored with n-1 colors in such a way that the edges can be partitioned into edge disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n-1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two, or five times a power of two.
Hecke algebra and quantum chromatic symmetric functions
Authors: Shelton Brittany , Skandera Mark
Published: August 2021

We evaluate induced sign characters of $H_n(q)$ at certain elements of $H_n(q)$ and conjecture an interpretation for the resulting polynomials as generating functions for $P$-tableaux by a certain statistic. Our conjecture relates the quantum chromatic symmetric functions of Shareshian and Wachs to $H_n(q)$ characters.

Nous évaluons les caractères de signe induits de $H_n(q)$ à certains éléments de $H_n(q)$ et nous conjecturons une interprétation des polynômes résultants comme fonctions génératrices pour les tableaux-$P$ par une certaine statistique. Cette conjecture établit un lien entre les fonctions chromatiques symétriques de Shareshian et Wachs et les caractères de $H_n(q)$.
Sorting and preimages of pattern classes
Authors: Claesson Anders , Úlfarsson Henning
Published: August 2021

We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the long-standing problem of describing West-3-stack-sortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern.

On introduit un algorithme qui détermine quand un opérateur de tri (tels que le tri par une pile, ou le tri-bulle) produit un motif donnè en sortie. Cet algorithme fournit une nouvelle preuve de la caractérisation des permutations 2-triables au sens de West (c'est-à-dire des permutations qui sont triées complètement par deux passages dans une pile) par des motifs interdits. On résout aussi le problème longtemps ouvert de la caractérisation des permutations 3-triables au sens de West. Ceci demande de définir un nouveau type de motifs généralisés, appelè motif décoré.
On a Unimodality Conjecture in Matroid Theory
Authors: Dukes W. M. B.
Published: August 2021

A certain unimodal conjecture in matroid theory states the number of rank-r matroids on a set of size n is unimodal in r and attains its maximum at r=\lfloor n/2 \rfloor . We show that this conjecture holds up to r=3 by constructing a map from a class of rank-2 matroids into the class of loopless rank-3 matroids. Similar inequalities are proven for the number of non-isomorphic loopless matroids, loopless matroids and matroids.
Correlations for the Novak process
Authors: Nordenstam Eric , Young Benjamin
Published: August 2021

We study random lozenge tilings of a certain shape in the plane called the Novak half-hexagon, and compute the correlation functions for this process. This model was introduced by Nordenstam and Young (2011) and has many intriguing similarities with a more well-studied model, domino tilings of the Aztec diamond. The most difficult step in the present paper is to compute the inverse of the matrix whose (i,j)-entry is the binomial coefficient $C(A, B_j-i)$ for indeterminate variables $A$ and $B_1, \dots , B_n.$

Nous étudions des pavages aléatoires d'une region dans le plan par des losanges qui s'appelle le demi-hexagone de Novak et nous calculons les corrélations de ce processus. Ce modèle a été introduit par Nordenstam et Young (2011) et a plusieurs similarités des pavages aléatoires d'un diamant aztèque par des dominos. La partie la plus difficile de cet article est le calcul de l'inverse d'une matrice ou l’élément (i,j) est le coefficient binomial $C(B_j-i, A)$ pour des variables $A$ et $B_1, \dots , B_n$ indéterminés.
A generalization of the alcove model and its applications
Authors: Lenart Cristian , Lubovsky Arthur
Published: August 2021

The alcove model of the first author and Postnikov describes highest weight crystals of semisimple Lie algebras. We present a generalization, called the quantum alcove model, and conjecture that it uniformly describes tensor products of column shape Kirillov-Reshetikhin crystals, for all untwisted affine types. We prove the conjecture in types $A$ and $C$. We also present evidence for the fact that a related statistic computes the energy function.

Le modèle des alcôves du premier auteur et Postnikov décrit les cristaux de plus haut poids des algèbres de Lie semi-simples. Nous présentons une généralisation, appelée le modèle des alcôves quantique, et nous conjecturons qu’il décrit dans une manière uniforme les produits tensoriels des cristaux de Kirillov-Reshetikhin de type colonne, pour toutes les types affines symétriques. Nous prouvons la conjecture dans les types $A$ et $C$. Nous fournissons aussi des preuves qu’une statistique associée donne la fonction d’énergie.
Lifted generalized permutahedra and composition polynomials
Authors: Ardila Federico , Doker Jeffrey
Published: August 2021

We introduce a "lifting'' construction for generalized permutohedra, which turns an $n$-dimensional generalized permutahedron into an $(n+1)$-dimensional one. We prove that this construction gives rise to Stasheff's multiplihedron from homotopy theory, and to the more general "nestomultiplihedra,'' answering two questions of Devadoss and Forcey. We construct a subdivision of any lifted generalized permutahedron whose pieces are indexed by compositions. The volume of each piece is given by a polynomial whose combinatorial properties we investigate. We show how this "composition polynomial'' arises naturally in the polynomial interpolation of an exponential function. We prove that its coefficients are positive integers, and conjecture that they are unimodal.

Nous introduisons une construction de "lifting'' (redressement) pour permutaèdres généralisés, qui transforme un permutaèdre généralisé de dimension $n$ en un de dimension $n+1$. Nous démontrons que cette construction conduit au multiplièdre de Stasheff à partir de la théorie d'homotopie, et aux "nestomultiplièdres", ce qui répond à deux questions de Devadoss et Forcey. Nous construisons une subdivision de n'importe quel permutaèdre généralisé dont les pièces sont indexées par compositions. La volume de chaque pièce est donnée par un polynôme dont nous recherchons les propriétés combinatoires. Nous montrons comment ce "polynôme de composition'' surgit naturellement dans l'interpolation d'une fonction exponentielle. Nous démontrons que ses coefficients sont strictement positifs, et nous conjecturons qu'ils sont unimodaux.