bluuebunny/crossref_metadata_2025 huggingface dataset:
Asymptotic normality of recursive algorithms via martingale difference arrays
Authors: Schachinger Werner
Published: August 2021

We propose martingale central limit theorems as an tool to prove asymptotic normality of the costs of certain recursive algorithms which are subjected to random input data. The recursive algorithms that we have in mind are such that if input data of size N produce random costs L_N, then L_N=^D L_n+ L_N-n+R_N for N ≥ n_0≥ 2, where n follows a certain distribution P_N on the integers \0, \ldots ,N\ and L_k =^D L_k for k≥ 0. L_n, L_N-n and R_N are independent, conditional on n, and R_N are random variables, which may also depend on n, corresponding to the cost of splitting the input data of size N (into subsets of size n and N-n) and combining the results of the recursive calls to yield the overall result. We construct a martingale difference array with rows converging to Z_N:= [L_N - E L_N] / [√Var L_N]. Under certain compatibility assumptions on the sequence (P_N)_N≥ 0 we show that a pair of sufficient conditions (of Lyapunov type) for Z_N → ^DN(0,1) can be restated as a pair of conditions regarding asymptotic relations between three sequences. All these sequences satisfy the same type of linear equation, that is also the defining equation for the sequence (E L_N)_N≥ 0 and thus very likely a well studied object. In the case that the P_N are binomial distributions with the same parameter p, and for deterministic R_N, we demonstrate the power of this approach. We derive very general sufficient conditions in terms of the sequence (R_N)_N≥ 0 (and for the scale R_N=N^α a characterization of those α ) leading to asymptotic normality of Z_N.
Enumerating (2+2)-free posets by the number of minimal elements and other statistics
Authors: Kitaev Sergey , Remmel Jeffrey
Published: August 2021

A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: $P(t)=∑_n≥ 0 ∏_i=1^n ( 1-(1-t)^i)$. We extend this result by finding the generating function for (2+2)-free posets when four statistics are taken into account, one of which is the number of minimal elements in a poset. We also show that in a special case when only minimal elements are of interest, our rather involved generating function can be rewritten in the form $P(t,z)=∑_n,k ≥0 p_n,k t^n z^k = 1+ ∑_n ≥0\frac{zt}{(1-zt)^n+1}∏_i=1^n (1-(1-t)^i)$ where $p_n,k$ equals the number of (2+2)-free posets of size $n$ with $k$ minimal elements.

Un poset sera dit (2+2)-libre s'il ne contient aucun sous-poset isomorphe à 2+2, l'union disjointe de deux chaînes à deux éléments. Dans un article récent, Bousquet-Mélou et al. ont trouvé, à l'aide de "suites de montées'', la fonction génératrice des nombres de posets (2+2)-libres: c'est $P(t)=∑_n≥ 0 ∏_i=1^n ( 1-(1-t)^i)$. Nous étendons ce résultat en trouvant la fonction génératrice des posets (\textrm2+2)-libres rendant compte de quatre statistiques, dont le nombre d'éléments minimaux du poset. Nous montrons aussi que lorsqu'on ne s'intéresse qu'au nombre d'éléments minimaux, notre fonction génératrice assez compliquée peut être simplifiée en$P(t,z)=∑_n,k ≥0 p_n,k t^n z^k = 1+ ∑_n ≥0\frac{zt}{(1-zt)^n+1}∏_i=1^n (1-(1-t)^i)$, où $p_n,k$ est le nombre de posets (2+2)-libres de taille $n$ avec $k$ éléments minimaux.
Linear coefficients of Kerov's polynomials: bijective proof and refinement of Zagier's result
Authors: Féray Valentin , Vassilieva Ekaterina A.
Published: August 2021

We look at the number of permutations $\beta$ of $[N]$ with $m$ cycles such that $(1 2 \ldots N) \beta^{-1}$ is a long cycle. These numbers appear as coefficients of linear monomials in Kerov's and Stanley's character polynomials. D. Zagier, using algebraic methods, found an unexpected connection with Stirling numbers of size $N+1$. We present the first combinatorial proof of his result, introducing a new bijection between partitioned maps and thorn trees. Moreover, we obtain a finer result, which takes the type of the permutations into account.

Nous étudions le nombre de permutations $\beta$ de $[N]$ avec $m$ cycles telles que $(1 2 \ldots N) \beta^{-1}$ a un seul cycle. Ces nombres apparaissent en tant que coefficients des monômes linéaires des polynômes de Kerov et de Stanley. À l'aide de méthodes algébriques, D. Zagier a trouvé une connexion inattendue avec les nombres de Stirling de taille $N+1$. Nous présentons ici la première preuve combinatoire de son résultat, en introduisant une nouvelle bijection entre des cartes partitionnées et des arbres épineux. De plus, nous obtenons un résultat plus fin, prenant en compte le type des permutations.
Extended Abstract for Enumerating Pattern Avoidance for Affine Permutations
Authors: Crites Andrew
Published: August 2021

In this paper we study pattern avoidance for affine permutations. In particular, we show that for a given pattern $p$, there are only finitely many affine permutations in $\widetilde{S}_n$ that avoid $p$ if and only if $p$ avoids the pattern $321$. We then count the number of affine permutations that avoid a given pattern $p$ for each $p$ in $S_3$, as well as give some conjectures for the patterns in $S_4$. This paper is just an outline; the full version will appear elsewhere.

Dans cet œuvre, on étudie comment les permutations affines évitent les motifs. Spécifiquement, on peut dire que pour le motif $p$, il existe un nombre limité de permutations affines dans $\widetilde{S}_n$ qui évite $p$ si et seulement si $p$ évite le motif $321$. Après, on compte le nombre de permutations affines qui évitent le motif $p$ pour chaque $p$ de $S_3$. Puis, on donne des conjectures pour les motifs de $S_4$. Ceci n'est qu'un aperçu; la version complète apparaîtra ailleurs.
The Hodge Structure of the Coloring Complex of a Hypergraph (Extended Abstract)
Authors: Rundell Sarah C , Long Jane H
Published: August 2021

Let $G$ be a simple graph with $n$ vertices. The coloring complex$ Δ (G)$ was defined by Steingrímsson, and the homology of $Δ (G)$ was shown to be nonzero only in dimension $n-3$ by Jonsson. Hanlon recently showed that the Eulerian idempotents provide a decomposition of the homology group $H_{n-3}(Δ (G))$ where the dimension of the $j^th$ component in the decomposition, $H_{n-3}^{(j)}(Δ (G))$, equals the absolute value of the coefficient of $λ ^j$ in the chromatic polynomial of $G, _{\mathcal{χg}}(λ )$. Let $H$ be a hypergraph with $n$ vertices. In this paper, we define the coloring complex of a hypergraph, $Δ (H)$, and show that the coefficient of $λ ^j$ in $χ _H(λ )$ gives the Euler Characteristic of the $j^{th}$ Hodge subcomplex of the Hodge decomposition of $Δ (H)$. We also examine conditions on a hypergraph, $H$, for which its Hodge subcomplexes are Cohen-Macaulay, and thus where the absolute value of the coefficient of $λ ^j$ in $χ _H(λ )$ equals the dimension of the $j^{th}$ Hodge piece of the Hodge decomposition of $Δ (H)$.

Soit $G$ un graphe simple à n sommets. Le complexe de coloriage $Δ (G)$ a été défini par Steingrímsson et Jonsson a prouvé que l'homologie de $Δ (G)$ est non nulle seulement en dimension $n-3$. Hanlon a récemment prouvé que les idempotents eulériens fournissent une décomposition du groupe d'homologie $H_{n-3}(Δ (G))$ où la dimension de la $j^e$ composante dans la décomposition de $H_{n-3}^{(j)}(Δ (G))$ est égale à la valeur absolue du coefficient de $λ ^j$ dans le polynôme chromatique de $G, _{\mathcal{χg}}(λ )$ . Soit H un hypergraphe à $n$ sommets. Dans ce texte, nous définissons le complexe de coloration d'un hypergraphe $Δ (H)$ et nous prouvons que le coefficient de $λ ^j$ dans $χ _H(λ )$ donne la caractéristique d'Euler du $j^e$ sous-complexe de Hodge dans la décomposition de Hodge de Δ (H). Nous examinons également des conditions sur un hypergraphe H pour lesquelles les sous-complexes de Hodge sont Cohen-Macaulay. Ainsi la valeur absolue du coefficient de $λ ^j$ in $χ _H(λ )$ est égale à la dimension du $j^e$sous-complexe de Hodge dans la décomposition de Hodge de $Δ (H)$.
Schubert complexes and degeneracy loci
Authors: Sam Steven V
Published: August 2021

The classical Thom―Porteous formula expresses the homology class of the degeneracy locus of a generic map between two vector bundles as an alternating sum of Schur polynomials. A proof of this formula was given by Pragacz by expressing this alternating sum as the Euler characteristic of a Schur complex, which gives an explanation for the signs. Fulton later generalized this formula to the situation of flags of vector bundles by using alternating sums of Schubert polynomials. Building on the Schubert functors of Kraśkiewicz and Pragacz, we introduce Schubert complexes and show that Fulton's alternating sum can be realized as the Euler characteristic of this complex, thereby providing a conceptual proof for why an alternating sum appears. \par

La formule classique de Thom―Porteous exprime la classe d'homologie du locus de la dégénérescence d'une fonction générique entre deux fibrés vectoriels comme une somme alternée des polynômes de Schur. Un preuve de cette formule a été donnée par Pragacz en exprimant ce alternant somme comme la caractéristique d'Euler d'un complexe de Schur, ce qui donne une explication pour les signes. Fulton puis généralisée cette formule à la situation des drapeaux de fibrés vectoriels à l'aide alternant des sommes de polynômes de Schubert. S'appuyant sur le Schubert foncteurs de Kraśkiewicz et Pragacz, nous introduisons les complexes de Schubert et montrent que la somme alternée de Fulton peuvent être réalisées en tant que Euler caractéristique de ce complexe, fournissant ainsi une preuve conceptuelle pour lesquelles une somme alternée appara\^ıt.
Counting RNA pseudoknotted structures (extended abstract)
Authors: Saule Cédric , Regnier Mireille , Steyaert Jean-Marc , Denise Alain
Published: August 2021

In 2004, Condon and coauthors gave a hierarchical classification of exact RNA structure prediction algorithms according to the generality of structure classes that they handle. We complete this classification by adding two recent prediction algorithms. More importantly, we precisely quantify the hierarchy by giving closed or asymptotic formulas for the theoretical number of structures of given size n in all the classes but one. This allows to assess the tradeoff between the expressiveness and the computational complexity of RNA structure prediction algorithms. \par

En 2004, Condon et ses coauteurs ont défini une classification des algorithmes exacts de prédiction de structure d'ARN, selon le degré de généralité des classes de structures qu'ils sont capables de prédire. Nous complétons cette classification en y ajoutant deux algorithmes récents. Chose plus importante, nous quantifions la hiérarchie des algorithmes, en donnant des formules closes ou asymptotiques pour le nombre théorique de structures de taille donnée n dans chacune des classes, sauf une. Ceci fournit un moyen d'évaluer, pour chaque algorithme, le compromis entre son degré de généralité et sa complexité.
On the diagonal ideal of $(\mathbb{C}^2)^n$ and $q,t$-Catalan numbers
Authors: Lee Kyungyong , Li Li
Published: August 2021

Let $I_n$ be the (big) diagonal ideal of $(\mathbb{C}^2)^n$. Haiman proved that the $q,t$-Catalan number is the Hilbert series of the graded vector space $M_n=\bigoplus_{d_1,d_2}(M_n)_{d_1,d_2}$ spanned by a minimal set of generators for $I_n$. We give simple upper bounds on $\textrm{dim} (M_n)_{d_1, d_2}$ in terms of partition numbers, and find all bi-degrees $(d_1,d_2)$ such that $\textrm{dim} (M_n)_{d_1, d_2}$ achieve the upper bounds. For such bi-degrees, we also find explicit bases for $(M_n)_{d_1, d_2}$.

Soit $I_n$ l'idéal de la (grande) diagonale de $(\mathbb{C}^2)^n$. Haiman a démontré que le $q,t$-nombre de Catalan est la série de Hilbert de l'espace vectoriel gradué $M_n=\bigoplus_{d_1,d_2}(M_n)_{d_1,d_2}$ engendré par un ensemble minimal de générateurs de $I_n$. Nous obtenons des bornes supérieures simples pour $\textrm{dim} (M_n)_{d_1, d_2}$ en termes de nombres de partitions, ainsi que tous les bi-degrés $(d_1, d_2)$ pour lesquels ces bornes supérieures sont atteintes. Pour ces bi-degrés, nous trouvons aussi des bases explicites de $(M_n)_{d_1, d_2}$.
A note on representations of the finite Heisenberg group and sums of greatest common divisors
Authors: Grassberger Johannes , Hörmann Günther
Published: August 2021

We review an elementary approach to the construction of all irreducible representations of the finite Heisenberg group. Determining the number of inequivalent classes of irreducible representations by different methods leads to an identity of sums involving greatest common divisors. We show how this identity can be generalized and derive an explicit formula for the sums.
Nonzero coefficients in restrictions and tensor products of supercharacters of $U_n(q)$ (extended abstract)
Authors: Lewis Stephen , Thiem Nathaniel
Published: August 2021

The standard supercharacter theory of the finite unipotent upper-triangular matrices $U_n(q)$ gives rise to a beautiful combinatorics based on set partitions. As with the representation theory of the symmetric group, embeddings of $U_m(q) \subseteq U_n(q)$ for $m \leq n$ lead to branching rules. Diaconis and Isaacs established that the restriction of a supercharacter of $U_n(q)$ is a nonnegative integer linear combination of supercharacters of $U_m(q)$ (in fact, it is polynomial in $q$). In a first step towards understanding the combinatorics of coefficients in the branching rules of the supercharacters of $U_n(q)$, this paper characterizes when a given coefficient is nonzero in the restriction of a supercharacter and the tensor product of two supercharacters. These conditions are given uniformly in terms of complete matchings in bipartite graphs.

La théorie standard des supercaractères des matrices triangulaires supérieures unipotentes finies $U_n(q)$ donne lieu à une merveilleuse combinatoire basée sur les partitions d'ensembles. Comme avec la théorie des représentations du groupe symétrique, Les plongements $U_m(q) \subseteq U_n(q)$ pour $m \leq n$ mènent aux règles de branchement. Diaconis et Isaacs ont montré que la restriction d'un supercaractère de $U_n(q)$ est une combinaison linéaire des supercaractères de $U_m(q)$ avec des coefficients entiers non négatifs (en fait, elle est polynomiale en $q$). Dans une première étape vers la compréhension de la combinatoire des coefficients dans les règles de branchement des supercaractères de $U_n(q)$, ce texte caractérise les coefficients non nuls dans la restriction d'un supercaractère et dans le produit des tenseurs de deux supercaractères. Ces conditions sont données uniformément en termes des couplages complets dans des graphes bipartis.
Generalized Ehrhart polynomials
Authors: Chen Sheng , Li Nan , Sam Steven V
Published: August 2021

Let $P$ be a polytope with rational vertices. A classical theorem of Ehrhart states that the number of lattice points in the dilations $P(n) = nP$ is a quasi-polynomial in $n$. We generalize this theorem by allowing the vertices of $P(n)$ to be arbitrary rational functions in $n$. In this case we prove that the number of lattice points in $P(n)$ is a quasi-polynomial for $n$ sufficiently large. Our work was motivated by a conjecture of Ehrhart on the number of solutions to parametrized linear Diophantine equations whose coefficients are polynomials in $n$, and we explain how these two problems are related.

Soit $P$ un polytope avec sommets rationelles. Un théorème classique des Ehrhart déclare que le nombre de points du réseau dans les dilatations $P(n) = nP$ est un quasi-polynôme en $n$. Nous généralisons ce théorème en permettant à des sommets de $P(n)$ comme arbitraire fonctions rationnelles en $n$. Dans ce cas, nous prouvons que le nombre de points du réseau en $P(n)$ est une quasi-polynôme pour $n$ assez grand. Notre travail a été motivée par une conjecture d'Ehrhart sur le nombre de solutions à linéaire paramétrée Diophantine équations dont les coefficients sont des polyômes en $n$, et nous expliquer comment ces deux problèmes sont liés.
The expansion of Hall-Littlewood functions in the dual Grothendieck polynomial basis
Authors: Bandlow Jason , Morse Jennifer
Published: August 2021

A combinatorial expansion of the Hall-Littlewood functions into the Schur basis of symmetric functions was first given by Lascoux and Schützenberger, with their discovery of the charge statistic. A combinatorial expansion of stable Grassmannian Grothendieck polynomials into monomials was first given by Buch, using set-valued tableaux. The dual basis of the stable Grothendieck polynomials was given a combinatorial expansion into monomials by Lam and Pylyavskyy using reverse plane partitions. We generalize charge to set-valued tableaux and use all of these combinatorial ideas to give a nice expansion of Hall-Littlewood polynomials into the dual Grothendieck basis. \par

En associant une charge à un tableau, une formule combinatoire donnant le développement des polynômes de Hall-Littlewood en termes des fonctions de Schur a été obtenue par Lascoux et Schützenberger. Une formule combinatoire donnant le développement des polynômes de Grothendieck Grassmanniens stables en termes des fonctions monomiales a quant à elle été obtenue par Buch à l'aide de tableaux à valeurs sur des ensembles. Finalement, une formule faisant intervenir des partitions planaires inverses a été obtenue par Lam et Pylyavskyy pour donner le développement de la base duale aux polynômes de Grothendieck stables en termes de monômes. Nous généralisons le concept de charge aux tableaux à valeurs sur des ensembles et, en nous servant de toutes ces notions combinatoires, nous obtenons une formule élégante donnant le développement des polynômes de Hall-Littlewood en termes de la base de Grothendieck duale.
Viewing counting polynomials as Hilbert functions via Ehrhart theory
Authors: Breuer Felix , Dall Aaron
Published: August 2021

Steingrímsson (2001) showed that the chromatic polynomial of a graph is the Hilbert function of a relative Stanley-Reisner ideal. We approach this result from the point of view of Ehrhart theory and give a sufficient criterion for when the Ehrhart polynomial of a given relative polytopal complex is a Hilbert function in Steingrímsson's sense. We use this result to establish that the modular and integral flow and tension polynomials of a graph are Hilbert functions.

Steingrímsson (2001) a montré que le polynôme chromatique d'un graphe est la fonction de Hilbert d'un idéal relatif de Stanley-Reisner. Nous abordons ce résultat du point de vue de la théorie d'Ehrhart et donnons un critère suffisant pour que le polynôme d'Ehrhart d'un complexe polytopal relatif donné soit une fonction de Hilbert au sens de Steingrímsson. Nous utilisons ce résultat pour établir que les polynômes de flux et de tension modulaires et intégraux d'un graphe sont des fonctions de Hilbert.
A preorder-free construction of the Kazhdan-Lusztig representations of Hecke algebras $H_n(q)$ of symmetric groups
Authors: Buehrle Charles , Skandera Mark
Published: August 2021

We use a quantum analog of the polynomial ring $\mathbb{Z}[x_{1,1},\ldots, x_{n,n}]$ to modify the Kazhdan-Lusztig construction of irreducible $H_n(q)$-modules. This modified construction produces exactly the same matrices as the original construction in [$\textit{Invent. Math.}$ $\textbf{53}$ (1979)], but does not employ the Kazhdan-Lusztig preorders. Our main result is dependent on new vanishing results for immanants in the quantum polynomial ring.

Nous utilisons un analogue quantique de l'anneau $\mathbb{Z}[x_{1,1},\ldots,x_{n,n}]$ pour modifier la construction Kazhdan-Lusztig des modules-$H_n(q)$ irréductibles. Cette construction modifiée produit exactement les mêmes matrices que la construction originale dans [$\textit{Invent. Math.}$ $\textbf{53}$ (1979)], mais sans employer les préordres de Kazhdan-Lusztig. Notre résultat principal dépend de nouveaux résultats de disparition pour des immanants dans l'anneau polynôme de quantique.
The Homology of the Real Complement of a $k$-parabolic Subspace Arrangement
Authors: Severs Christopher , White Jacob A.
Published: August 2021

The $k$-parabolic subspace arrangement, introduced by Barcelo, Severs and White, is a generalization of the well known $k$-equal arrangements of type-$A$ and type-$B$. In this paper we use the discrete Morse theory of Forman to study the homology of the complements of $k$-parabolic subspace arrangements. In doing so, we recover some known results of Björner et al. and provide a combinatorial interpretation of the Betti numbers for any $k$-parabolic subspace arrangement. The paper provides results for any $k$-parabolic subspace arrangement, however we also include an extended example of our methods applied to the $k$-equal arrangements of type-$A$ and type-$B$. In these cases, we obtain new formulas for the Betti numbers.

L'arrangement $k$-parabolique, introduit par Barcelo, Severs et White, est une généralisation des arrangements, $k$-éguax de type $A$ et de type $B$. Dans cet article, nous utilisons la théorie de Morse discrète proposée par Forman pour étudier l'homologie des compléments d'arrangements $k$-paraboliques. Ce faisant, nous retrouvons les résultats connus de Bjorner et al. mais aussi nous fournissons une interprétation combinatoire des nombres de Betti pour des arrangements $k$-paraboliques. Ce papier fournit alors des résultats pour n'importe quel arrangement $k$-parabolique, cependant nous y présentons un exemple étendu de nos méthodes appliquées aux arrangements $k$-éguax de type $A$ et de type $B$. Pour ce cas, on obtient de nouvelles formules pour les nombres de Betti.
Compositions and samples of geometric random variables with constrained multiplicities
Authors: Archibald Margaret , Knopfmacher Arnold , Mansour Toufik
Published: August 2021

We investigate the probability that a random composition (ordered partition) of the positive integer $n$ has no parts occurring exactly $j$ times, where $j$ belongs to a specified finite $\textit{`forbidden set'}$ $A$ of multiplicities. This probability is also studied in the related case of samples $\Gamma =(\Gamma_1,\Gamma_2,\ldots, \Gamma_n)$ of independent, identically distributed random variables with a geometric distribution.

Nous examinons la probabilité qu'une composition faite au hasard (une partition ordonnée) du nombre entier positif $n$ n'a pas de parties qui arrivent exactement $j$ fois, où $j$ appartient à une série interdite, finie et spécifiée $A$ de multiplicités. Cette probabilité est aussi étudiée dans le cas des suites $\Gamma =(\Gamma_1,\Gamma_2,\ldots,\Gamma_n)$ de variables aléatoires identiquement distribuées et indépendantes avec une distribution géométrique.
Powers of the Vandermonde determinant, Schur functions, and the dimension game
Authors: Ballantine Cristina
Published: August 2021

Since every even power of the Vandermonde determinant is a symmetric polynomial, we want to understand its decomposition in terms of the basis of Schur functions. We investigate several combinatorial properties of the coefficients in the decomposition. In particular, I will give a recursive approach for computing the coefficient of the Schur function $s_μ$ in the decomposition of an even power of the Vandermonde determinant in $n+1$ variables in terms of the coefficient of the Schur function $s_λ$ in the decomposition of the same even power of the Vandermonde determinant in $n$ variables if the Young diagram of $μ$ is obtained from the Young diagram of $λ$ by adding a tetris type shape to the top or to the left.

Comme toute puissance paire du déterminant de Vandermonde est un polynôme symétrique, nous voulons comprendre sa décomposition dans la base des fonctions de Schur. Nous allons étudier plusieurs propriétés combinatoires des coefficients de la décomposition. En particulier, nous allons donner une approche récursive pour le calcul du coefficient de la fonction de Schur $s_μ$ dans la décomposition d'une puissance paire du déterminant de Vandermonde en $n+1$ variables, en fonction du coefficient de la fonction de Schur $s_λ$ dans la décomposition de la même puissance paire du déterminant de Vandermonde en $n$ variables, lorsque le diagramme de Young de $μ$ est obtenu à partir du diagramme de Young de $λ$ par l'addition d'une forme de type tetris vers le haut ou vers la gauche.
On the enumeration of column-convex permutominoes
Authors: Beaton Nicholas R. , Disanto Filippo , Guttmann Anthony J. , Rinaldi Simone
Published: August 2021

We study the enumeration of \emphcolumn-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations. We provide a direct recursive construction for the column-convex permutominoes of a given size, based on the application of the ECO method and generating trees, which leads to a functional equation. Then we obtain some upper and lower bounds for the number of column-convex permutominoes, and conjecture its asymptotic behavior using numerical analysis.

Nous étudions l'énumeration des \emphpermutominos verticalement convexes, c.à.d. les polyominos verticalement convexes définis par un couple de permutations. Nous donnons une construction recursive directe pour ces permutominos de taille fixée, basée sur une application de la méthode ECO et les arbres de génération, qui nous amène à une équat ion fonctionelle. Ensuite nous obtenons des bornes superieures et inférieures pour le nombre de ces permutominos convexes et nous conjecturons leur comportement asymptotique à l'aide d'analyses numériques.
Primitive orthogonal idempotents for R-trivial monoids
Authors: Berg Chris , Bergeron Nantel , Bhargava Sandeep , Saliola Franco
Published: August 2021

We construct a recursive formula for a complete system of primitive orthogonal idempotents for any R-trivial monoid. This uses the newly proved equivalence between the notions of R-trivial monoid and weakly ordered monoid.

Nous construisons une formule récursive pour un système complet d'idempotents orthogonaux primitifs pour tout monoïde R-trivial. Nous employons une nouvelle équivalence entre les notions de monoïde R-trivial et de monoïde faiblement ordonné.
Arc Spaces and Rogers-Ramanujan Identities
Authors: Bruschek Clemens , Mourtada Hussein , Schepers Jan
Published: August 2021

Arc spaces have been introduced in algebraic geometry as a tool to study singularities but they show strong connections with combinatorics as well. Exploiting these relations we obtain a new approach to the classical Rogers-Ramanujan Identities. The linking object is the Hilbert-Poincaré series of the arc space over a point of the base variety. In the case of the double point this is precisely the generating series for the integer partitions without equal or consecutive parts.

Les espaces des arcs ont été introduit pour étudier les singularités, mais ils ont aussi un lien fort avec la combinatoire. Ce lien permet une nouvelle approche vers les identités de Rogers-Ramanujan. L'objet permettant cette approche est la série de Hilbert-Poincaré de l'algèbre des arcs centrés en un point de la variété de base. Dans le cas où cette variété est le point double, cette série est la série génératrice des partitions d'un nombre entier sans parties égales ou consécutives.
Dual combinatorics of zonal polynomials
Authors: Féray Valentin , Sniady Piotr
Published: August 2021

In this paper we establish a new combinatorial formula for zonal polynomials in terms of power-sums. The proof relies on the sign-reversing involution principle. We deduce from it formulas for zonal characters, which are defined as suitably normalized coefficients in the expansion of zonal polynomials in terms of power-sum symmetric functions. These formulas are analogs of recent developments on irreducible character values of symmetric groups. The existence of such formulas could have been predicted from the work of M. Lassalle who formulated two positivity conjectures for Jack characters, which we prove in the special case of zonal polynomials.

Dans cet article, nous établissons une nouvelle formule combinatoire pour les polynômes zonaux en fonction des fonctions puissance. La preuve utilise le principe de l'involution changeant les signes. Nous en déduisons des formules pour les caractères zonaux, qui sont définis comme les coefficients des polynômes zonaux écrits sur la base des fonctions puissance, normalisés de manière appropriée. Ces formules sont des analogues de développements récents sur les caractères du groupe symétrique. L'existence de telles formules aurait pu être prédite à partir des travaux de M. Lassalle, qui a proposé deux conjectures de positivité sur les caractères de Jack, que nous prouvons dans le cas particulier des polynômes zonaux.
The pentagram map and Y-patterns
Authors: Glick Max
Published: August 2021

The pentagram map, introduced by R. Schwartz, is defined by the following construction: given a polygon as input, draw all of its ``shortest'' diagonals, and output the smaller polygon which they cut out. We employ the machinery of cluster algebras to obtain explicit formulas for the iterates of the pentagram map.

L'application pentagramme de R. Schwartz est définie par la construction suivante: on trace les diagonales ``les plus courtes'' d'un polygone donné en entrée et on retourne en sortie le plus petit polygone que ces diagonales découpent. Nous employons la machinerie des algèbres ``clusters'' pour obtenir des formules explicites pour les itérations de l'application pentagramme.
Cyclic sieving phenomenon in non-crossing connected graphs
Authors: Guo Alan
Published: August 2021

A non-crossing connected graph is a connected graph on vertices arranged in a circle such that its edges do not cross. The count for such graphs can be made naturally into a q-binomial generating function. We prove that this generating function exhibits the cyclic sieving phenomenon, as conjectured by S.-P. Eu.

Un graphe connexe dont les sommets sont disposés sur un cercle est sans croisement si ses arêtes ne se croisent pas. Nous démontrons une conjecture de S.-P. Eu affirmant que la fonction génératrice q-binomiale dénombrant de tels graphes exhibe le phénomène du crible cyclique.
Closed paths whose steps are roots of unity
Authors: Labelle Gilbert , Lacasse Annie
Published: August 2021

We give explicit formulas for the number $U_n(N)$ of closed polygonal paths of length $N$ (starting from the origin) whose steps are $n^{\textrm{th}}$ roots of unity, as well as asymptotic expressions for these numbers when $N \rightarrow \infty$. We also prove that the sequences $(U_n(N))_{N \geq 0}$ are $P$-recursive for each fixed $n \geq 1$ and leave open the problem of determining the values of $N$ for which the $\textit{dual}$ sequences $(U_n(N))_{n \geq 1}$ are $P$-recursive.

Nous donnons des formules explicites pour le nombre $U_n(N)$ de chemins polygonaux fermés de longueur $N$ (débutant à l'origine) dont les pas sont des racines $n$-ièmes de l'unité, ainsi que des expressions asymptotiques pour ces nombres lorsque $N \rightarrow \infty$. Nous démontrons aussi que les suites $(U_n(N))_{N \geq 0}$ sont $P$-récursives pour chaque $n \geq 1$ fixé et laissons ouvert le problème de déterminer les valeurs de $N$ pour lesquelles les suites $\textit{duales}$ $(U_n(N))_{n \geq 1}$ sont $P$-récursives.
Recognizing the P_4-structure of claw-free graphs and a larger graph class
Authors: Babel Luitpold , Brandstädt Andreas , Le Van Bang
Published: August 2021

The P_4-structure of a graph G is a hypergraph \textbfH on the same vertex set such that four vertices form a hyperedge in \textbfH whenever they induce a P_4 in G. We present a constructive algorithm which tests in polynomial time whether a given 4-uniform hypergraph is the P_4-structure of a claw-free graph and of (banner,chair,dart)-free graphs. The algorithm relies on new structural results for (banner,chair,dart)-free graphs which are based on the concept of p-connectedness. As a byproduct, we obtain a polynomial time criterion for perfectness for a large class of graphs properly containing claw-free graphs.
The brick polytope of a sorting network
Authors: Pilaud Vincent , Santos Francisco
Published: August 2021

The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud and Pocchiola in their study of pseudoline arrangements with contacts supported by a given network. In this paper, we construct the "brick polytope'' of a network, obtained as the convex hull of the "brick vectors'' associated to each pseudoline arrangement supported by the network. We characterize its vertices, describe its faces, and decompose it as a Minkowski sum of simpler polytopes. Our brick polytopes include Hohlweg and Lange's many realizations of the associahedron, which arise as brick polytopes of certain well-chosen networks.

L'associaèdre est un polytope dont le graphe est le graphe des flips sur les triangulations d'un polygone convexe. Les pseudotriangulations et les multitriangulations généralisent les triangulations dans deux directions différentes, qui ont été unifiées par Pilaud et Pocchiola au travers de leur étude des arrangements de pseudodroites avec contacts couvrant un support donné. Nous construisons ici le "polytope de briques'' d'un support, obtenu comme l'enveloppe convexe des "vecteurs de briques'' associés à chaque arrangement de pseudodroites couvrant ce support. Nous caractérisons les sommets de ce polytope, décrivons ses faces et le décomposons en somme de Minkowski de polytopes élémentaires. Notre construction contient toutes les réalisations de l'associaèdre d'Hohlweg et Lange, qui apparaissent comme polytopes de briques de certains supports bien choisis.
Cyclic sieving for two families of non-crossing graphs
Authors: Poznanović Svetlana
Published: August 2021

We prove the cyclic sieving phenomenon for non-crossing forests and non-crossing graphs. More precisely, the cyclic group acts on these graphs naturally by rotation and we show that the orbit structure of this action is encoded by certain polynomials. Our results confirm two conjectures of Alan Guo.

Nous prouvons le phénomène de crible cyclique pour les forêts et les graphes sans croisement. Plus précisément, le groupe cyclique agit sur ces graphes naturellement par rotation et nous montrons que la structure d'orbite de cette action est codée par certains polynômes. Nos résultats confirment deux conjectures de Alan Guo.
Lyndon factorization of generalized words of Thue
Authors: Černý Anton
Published: August 2021

The i-th symbol of the well-known infinite word of Thue on the alphabet \ 0,1\ can be characterized as the parity of the number of occurrences of the digit 1 in the binary notation of i. Generalized words of Thue are based on counting the parity of occurrences of an arbitrary word w∈\ 0,1\^+-0^* in the binary notation of i. We provide here the standard Lyndon factorization of some subclasses of this class of infinite words.
3x+1 Minus the +
Authors: Monks Kenneth G.
Published: August 2021

We use Conway's \emphFractran language to derive a function R:\textbfZ^+ → \textbfZ^+ of the form R(n) = r_in if n ≡ i \bmod d where d is a positive integer, 0 ≤ i < d and r_0,r_1, ... r_d-1 are rational numbers, such that the famous 3x+1 conjecture holds if and only if the R-orbit of 2^n contains 2 for all positive integers n. We then show that the R-orbit of an arbitrary positive integer is a constant multiple of an orbit that contains a power of 2. Finally we apply our main result to show that any cycle \ x_0, ... ,x_m-1 \ of positive integers for the 3x+1 function must satisfy \par ∑ _i∈ \textbfE \lfloor x_i/2 \rfloor = ∑ _i∈ \textbfO \lfloor x_i/2 \rfloor +k. \par where \textbfO=\ i : x_i is odd \ , \textbfE=\ i : x_i is even \ , and k=|\textbfO|. \par The method used illustrates a general mechanism for deriving mathematical results about the iterative dynamics of arbitrary integer functions from \emphFractran algorithms.
Product decomposition for surjective 2-block NCCA
Authors: García-Ramos Felipe
Published: August 2021

In this paper we define products of one-dimensional Number Conserving Cellular Automata (NCCA) and show that surjective NCCA with 2 blocks (i.e radius 1/2) can always be represented as products of shifts and identites. In particular, this shows that surjective 2-block NCCA are injective.
Orbits of the Bernoulli measure in single-transition asynchronous cellular automata
Authors: Fukś Henryk , Skelton Andrew
Published: August 2021

We study iterations of the Bernoulli measure under nearest-neighbour asynchronous binary cellular automata (CA) with a single transition. For these CA, we show that a coarse-level description of the orbit of the Bernoulli measure can be obtained, that is, one can explicitly compute measures of short cylinder sets after arbitrary number of iterations of the CA. In particular, we give expressions for probabilities of ones for all three minimal single-transition rules, as well as expressions for probabilities of blocks of length 3 for some of them. These expressions can be interpreted as "response curves'', that is, curves describing the dependence of the final density of ones on the initial density of ones.
Bifurcations in Boolean Networks
Authors: Kuhlman Chris , Mortveit Henning , Murrugarra David , Kumar Anil
Published: August 2021

This paper characterizes the attractor structure of synchronous and asynchronous Boolean networks induced by bi-threshold functions. Bi-threshold functions are generalizations of standard threshold functions and have separate threshold values for the transitions $0 \rightarrow $1 (up-threshold) and $1 \rightarrow 0$ (down-threshold). We show that synchronous bi-threshold systems may, just like standard threshold systems, only have fixed points and 2-cycles as attractors. Asynchronous bi-threshold systems (fixed permutation update sequence), on the other hand, undergo a bifurcation. When the difference $\Delta$ of the down- and up-threshold is less than 2 they only have fixed points as limit sets. However, for $\Delta \geq 2$ they may have long periodic orbits. The limiting case of $\Delta = 2$ is identified using a potential function argument. Finally, we present a series of results on the dynamics of bi-threshold systems for families of graphs.
Asymptotic behavior of some statistics in Ewens random permutations
Authors: Feray Valentin
Published: August 2021

The purpose of this article is to present a general method to find limiting laws for some renormalized statistics on random permutations. The model considered here is Ewens sampling model, which generalizes uniform random permutations. We describe the asymptotic behavior of a large family of statistics, including the number of occurrences of any given dashed pattern. Our approach is based on the method of moments and relies on the following intuition: two events involving the images of different integers are almost independent.
Enumeration and Random Generation of Concurrent Computations
Authors: Bodini Olivier , Genitrini Antoine , Peschanski Frédéric
Published: August 2021

In this paper, we study the shuffle operator on concurrent processes (represented as trees) using analytic combinatorics tools. As a first result, we show that the mean width of shuffle trees is exponentially smaller than the worst case upper-bound. We also study the expected size (in total number of nodes) of shuffle trees. We notice, rather unexpectedly, that only a small ratio of all nodes do not belong to the last two levels. We also provide a precise characterization of what ``exponential growth'' means in the case of the shuffle on trees. Two practical outcomes of our quantitative study are presented: (1) a linear-time algorithm to compute the probability of a concurrent run prefix, and (2) an efficient algorithm for uniform random generation of concurrent runs.
Some exact asymptotics in the counting of walks in the quarter plane
Authors: Fayolle Guy , Raschel Kilian
Published: August 2021

Enumeration of planar lattice walks is a classical topic in combinatorics, at the cross-roads of several domains (e.g., probability, statistical physics, computer science). The aim of this paper is to propose a new approach to obtain some exact asymptotics for walks confined to the quarter plane.
Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)
Authors: Bindjeme Patrick , fill james Allen
Published: August 2021

Using a recursive approach, we obtain a simple exact expression for the $L^2$-distance from the limit in the classical limit theorem of Régnier (1989) for the number of key comparisons required by $\texttt{QuickSort}$. A previous study by Fill and Janson (2002) using a similar approach found that the $d_2$-distance is of order between $n^{-1} \log{n}$ and $n^{-1/2}$, and another by Neininger and Ruschendorf (2002) found that the Zolotarev $\zeta _3$-distance is of exact order $n^{-1} \log{n}$. Our expression reveals that the $L^2$-distance is asymptotically equivalent to $(2 n^{-1} \ln{n})^{1/2}$.
Combinatorial Hopf algebra of supercharacters of type D
Authors: Benedetti Carolina
Published: August 2021

We provide a Hopf algebra structure on the supercharacter theory for the unipotent upper triangular group of type {D} over a finite field. Also, we make further comments with respect to types {B} and {C}. Type {A} was explored by M. Aguiar et. al (2010), thus this extended abstract is a contribution to understand combinatorially the supercharacter theory of the other classical Lie types.

Dotamos con una estructura de álgebra de Hopf la teoría de supercaracteres del grupo de matrices unipotentes triangulares superiores de tipo{D} sobre un cuerpo finito. Ademas, discutimos brevemente los tipos {B} y {C}. El tipo A fue explorado por M. Aguiar et al (2010), por lo tanto este resumen extendido es una contribución para entender combinatoriamente la teoría de supercaracteres de los otros tipos de Lie clásicos.

Nous construisons une structure d'algèbre de Hopf sur la thérie des supercharactères du groupe de matrices unipotentes triangulaires supéieures de type {D}. Nous donnons aussi quelques commentaires à l'égard des types {B} et {C} . Le type {A} a été explorée par M. Aguiar et al. (2010), donc ce résumé étendu est une contribution à la théorie combinatoire des supercharactères pour les autres types de Lie classiques. \par
Tropical Oriented Matroids
Authors: Horn Silke
Published: August 2021

Tropical oriented matroids were defined by Ardila and Develin in 2007. They are a tropical analogue of classical oriented matroids in the sense that they encode the properties of the types of points in an arrangement of tropical hyperplanes – in much the same way as the covectors of (classical) oriented matroids describe the types in arrangements of linear hyperplanes. Not every oriented matroid can be realised by an arrangement of linear hyperplanes though. The famous Topological Representation Theorem by Folkman and Lawrence, however, states that every oriented matroid can be represented as an arrangement of $\textit{pseudo}$hyperplanes. Ardila and Develin proved that tropical oriented matroids can be represented as mixed subdivisions of dilated simplices. In this paper I prove that this correspondence is a bijection. Moreover, I present a tropical analogue for the Topological Representation Theorem.

La notion de matroïde orientè tropical a été introduite par Ardila et Develin en 2007. Ils sont un analogue des matroïdes orientés classiques dans le sens où ils codent les propriétés des types de points dans un arrangement d'hyperplans tropicaux – d'une manière très similaire à celle dont les covecteurs des matroïdes orientés (classiques) décrivent les types de points dans les arrangements d'hyperplans linéaires. Tous les matroïdes orientés ne peuvent pas être représentés par un arrangement d'hyperplans linéaires. Cependant le célèbre théorème de représentation topologique de Folkman et Lawrence affirme que tout matroïde orientè peut être représenté par un arrangement de $\textit{pseudo}$-hyperplans. Ardila et Develin ont prouvè que les matroïdes orientés tropicaux peuvent être représentés par des sous-divisions mixtes de simplexes dilatés. Je prouve dans cet article que cette correspondance est une bijection. Je présente en outre, un analogue tropical du théorème de représentation topologique.
Coherent fans in the space of flows in framed graphs
Authors: Danilov Vladimir I. , Karzanov Alexander V. , Koshevoy Gleb A.
Published: August 2021

Let $G=(V,E)$ be a finite acyclic directed graph. Being motivated by a study of certain aspects of cluster algebras, we are interested in a class of triangulations of the cone of non-negative flows in $G, \mathcal F_+(G)$. To construct a triangulation, we fix a raming at each inner vertex $v$ of $G$, which consists of two linear orders: one on the set of incoming edges, and the other on the set of outgoing edges of $v$. A digraph $G$ endowed with a framing at each inner vertex is called $framed$. Given a framing on $G$, we define a reflexive and symmetric binary relation on the set of extreme rays of $\mathcal F_+ (G)$. We prove that that the complex of cliques formed by this binary relation is a pure simplicial complex, and that the cones spanned by cliques constitute a unimodular simplicial regular fan $Σ (G)$ covering the entire $\mathcal F_+(G)$.

Soit $G=(V,E)$ un graphe orientè, fini et acyclique. Nous nous intéressons, en lien avec l’étude de certains aspects des algèbres amassées, à une classe de triangulations du cône des flots positifs de $G, \mathcal F_+(G)$. Pour construire une triangulation, nous ajoutons une structure en chaque sommet interne $v$ de $G$, constituée de deux ordres totaux : l'un sur l'ensemble des arcs entrants, l'autre sur l'ensemble des arcs sortants de $v$. On dit alors que $G$ est structurè. On définit ensuite une relation binaire réflexive et symétrique sur l'ensemble des rayons extrêmes de $\mathcal F_+ (G)$. Nous démontrons que le complexe des cliques formè par cette relation binaire est un complexe simplicial pur, et que le cône engendré par les cliques forme un éventail régulier simplicial unimodulaire $Σ (G)$ qui couvre complètement $\mathcal F_+(G)$.
EL-Shellability of Generalized Noncrossing Partitions
Authors: Mühle Henri
Published: August 2021

In this article we prove that the poset of m-divisible noncrossing partitions is EL-shellable for every well-generated complex reflection group. This was an open problem for type G(d,d,n) and for the exceptional types, for which a proof is given case-by-case.

Dans cet article nous prouvons que l'ensemble ordonnè des partitions non-croisées m-divisibles est EL-èpluchable (``EL-shellable'') pour tout groupe de réflexions complexe bien engendrè. Il s'agissait d'un problème ouvert pour le type G(d,d,n) et pour les types exceptionnels, pour lesquels nous donnons une preuve au cas par cas.
Minimal transitive factorizations of a permutation of type (p,q)
Authors: Kim Jang Soo , Seo Seunghyun , Shin Heesung
Published: August 2021

We give a combinatorial proof of Goulden and Jackson's formula for the number of minimal transitive factorizations of a permutation when the permutation has two cycles. We use the recent result of Goulden, Nica, and Oancea on the number of maximal chains of annular noncrossing partitions of type B.

Nous donnons une preuve combinatoire de formule de Goulden et Jackson pour le nombre de factorisations transitives minimales d'une permutation lorsque la permutation a deux cycles. Nous utilisons le rèsultat rècent de Goulden, Nica, et Oancea sur le nombre de chaî nes maximales des partitions non-croisèes annulaires de type B.