bluuebunny/crossref_metadata_2025 huggingface dataset:
Classes of graphs with restricted interval models
Authors: Proskurowski Andrzej , Telle Jan Arne
Published: August 2021

We introduce q-proper interval graphs as interval graphs with interval models in which no interval is properly contained in more than q other intervals, and also provide a forbidden induced subgraph characterization of this class of graphs. We initiate a graph-theoretic study of subgraphs of q-proper interval graphs with maximum clique size k+1 and give an equivalent characterization of these graphs by restricted path-decomposition. By allowing the parameter q to vary from 0 to k, we obtain a nested hierarchy of graph families, from graphs of bandwidth at most k to graphs of pathwidth at most k. Allowing both parameters to vary, we have an infinite lattice of graph classes ordered by containment.
Accelerated series for universal constants, by the WZ method
Authors: Wilf Herbert S.
Published: August 2021

In this paper, the author presents a method, based on WZ theory, for finding rapidly converging series for universal constants. This method is analogous but different from Amdeberhan and Zeilberger's method.
Polytypic Functions Over Nested Datatypes
Authors: Hinze Ralf
Published: August 2021

The theory and practice of polytypic programming is intimately connected with the initial algebra semantics of datatypes. This is both a blessing and a curse. It is a blessing because the underlying theory is beautiful and well developed. It is a curse because the initial algebra semantics is restricted to so-called regular datatypes. Recent work by R. Bird and L. Meertens [3] on the semantics of non-regular or nested datatypes suggests that an extension to general datatypes is not entirely straightforward. Here we propose an alternative that extends polytypism to arbitrary datatypes, including nested datatypes and mutually recursive datatypes. The central idea is to use rational trees over a suitable set of functor symbols as type arguments for polytypic functions. Besides covering a wider range of types the approach is also simpler and technically less involving than previous ones. We present several examples of polytypic functions, among others polytypic reduction and polytypic equality. The presentation assumes some background in functional and in polytypic programming. A basic knowledge of monads is required for some of the examples.
Hopf algebras and the logarithm of the S-transform in free probability ― Extended abstract
Authors: Mastnak Mitja , Nica Alexandru
Published: August 2021

This document is an extended abstract of the paper `Hopf algebras and the logarithm of the S-transform in free probability' in which we introduce a Hopf algebraic approach to the study of the operation $\boxtimes$ (free multiplicative convolution) from free probability.
Triangulations of root polytopes and reduced forms (Extended abstract)
Authors: Mészáros Karola
Published: August 2021

The type $A_n$ root polytope $\mathcal{P}(A_n^+)$ is the convex hull in $\mathbb{R}^{n+1}$ of the origin and the points $e_i-e_j$ for $1 \leq i < j \leq n+1$. Given a tree $T$ on vertex set $[n+1]$, the associated root polytope $\mathcal{P}(T)$ is the intersection of $\mathcal{P}(A_n^+)$ with the cone generated by the vectors $e_i-e_j$, where $(i, j) \in E(T)$, $i < j$. The reduced forms of a certain monomial $m[T]$ in commuting variables $x_{ij}$ under the reduction $x_{ij} x_{jk} \to x_{ik} x_{ij} + x_{jk} x_{ik} + \beta x_{ik}$, can be interpreted as triangulations of $\mathcal{P}(T)$. If we allow variables $x_{ij}$ and$x_{kl}$ to commute only when $i, j, k, l$ are distinct, then the reduced form of $m[T]$ is unique and yields a canonical triangulation of $\mathcal{P}(T)$ in which each simplex corresponds to a noncrossing alternating forest.

Le polytope des racines $\mathcal{P}(A_n^+)$ de type $A_n$ est l'enveloppe convexe dans $\mathbb{R}^{n+1}$ de l'origine et des points $e_i-e_j$ pour $1 \leq i < j \leq n+1$. Étant donné un arbre $T$ sur l'ensemble des sommets $[n+1]$, le polytope des racines associé, $\mathcal{P}(T)$, est l'intersection de $\mathcal{P}(A_n^+)$ avec le cône engendré par les vecteurs $e_i-e_j$, où $(i, j) \in E(T)$, $i < j$. Les formes réduites d'un certain monôme $m[T]$ en les variables commutatives $x_{ij}$ sous la reduction $x_{ij} x_{jk} \to x_{ik} x_{ij} + x_{jk} x_{ik} + \beta x_{ik}$ peuvent être interprétées comme des triangulations de $\mathcal{P}(T)$. Si on impose la restriction que les variables $x_{ij}$ et $x_{kl}$ commutent seulement lorsque les indices $i, j, k, l$ sont distincts, alors la forme réduite de $m[T]$ est unique et produit une triangulation canonique de $\mathcal{P}(T)$ dans laquelle chaque simplexe correspond à une forêt alternée non croisée.
Another bijection between $2$-triangulations and pairs of non-crossing Dyck paths
Authors: Nicolás Carlos M.
Published: August 2021

A $k$-triangulation of the $n$-gon is a maximal set of diagonals of the $n$-gon containing no subset of $k+1$ mutually crossing diagonals. The number of $k$-triangulations of the $n$-gon, determined by Jakob Jonsson, is equal to a $k \times k$ Hankel determinant of Catalan numbers. This determinant is also equal to the number of $k$ non-crossing Dyck paths of semi-length $n-2k$. This brings up the problem of finding a combinatorial bijection between these two sets. In FPSAC 2007, Elizalde presented such a bijection for the case $k=2$. We construct another bijection for this case that is stronger and simpler that Elizalde's. The bijection preserves two sets of parameters, degrees and generalized returns. As a corollary, we generalize Jonsson's formula for $k=2$ by counting the number of $2$-triangulations of the $n$-gon with a given degree at a fixed vertex.

Une $k$-triangulation du $n$-gon est un ensemble maximal de diagonales du $n$-gon ne contenant pas de sous-ensemble de $k+1$ diagonales mutuellement croisant. Le nombre de $k$-triangulations du $n$-gon, déterminé par Jakob Jonsson, est égal à un déterminant de Hankel $k \times k$ de nombres de Catalan. Ce déterminant est aussi égal au nombre de $k$ chemins de Dyck de largo $n-2k$ que ne pas se croiser. Cela porte le problème de trouver une bijection de type combinatoire entre ces deux ensembles. À la FPSAC 2007, Elizalde a présenté une telle bijection pour le cas $k = 2$. Nous construisons une autre bijection pour ce cas qui est plus forte et plus simple que de l'Elizalde. La bijection conserve deux ensembles de paramètres, les degré et les retours généralisée. De ce, nous généralisons la formule de Jonsson pour $k = 2$ en comptant le nombre de $2$-triangulations du $n$-gon avec un degré à un vertex fixe.
A bijection between noncrossing and nonnesting partitions of types A and B
Authors: Mamede Ricardo
Published: August 2021

The total number of noncrossing partitions of type $\Psi$ is the $n$th Catalan number $\frac{1}{ n+1} \binom{2n}{n}$ when $\Psi =A_{n-1}$, and the binomial coefficient $\binom{2n}{n}$ when $\Psi =B_n$, and these numbers coincide with the correspondent number of nonnesting partitions. For type $A$, there are several bijective proofs of this equality; in particular, the intuitive map, which locally converts each crossing to a nesting, is one of them. In this paper we present a bijection between nonnesting and noncrossing partitions of types $A$ and $B$ that generalizes the type $A$ bijection that locally converts each crossing to a nesting.

Le nombre total des partitions non-croisées du type $\Psi$ est le $n$-ème nombre de Catalan $\frac{1}{ n+1} \binom{2n}{n}$ si $\Psi =A_{n-1}$, et le coefficient binomial $\binom{2n}{n}$ si $\Psi =B_n$, et ces nombres son coïncidents avec le nombre correspondant des partitions non-emboîtées. Pour le type $A$, il y a plusieurs preuves bijectives de cette égalité; en particulier, la intuitive fonction, qui convertit localement chaque croisée en une emboîtée, c'est un d'entre eux. Dans ce papier nous présentons une bijection entre partitions non-croisées et non-emboîtées des types $A$ et $B$ qui généralise la bijection du type $A$ qui localement convertit chaque croisée en une emboîtée.
Macdonald polynomials at $t=q^k$
Authors: Luque Jean-Gabriel
Published: August 2021

We investigate the homogeneous symmetric Macdonald polynomials $P_{\lambda} (\mathbb{X} ;q,t)$ for the specialization $t=q^k$. We show an identity relying the polynomials $P_{\lambda} (\mathbb{X} ;q,q^k)$ and $P_{\lambda} (\frac{1-q}{1-q^k}\mathbb{X} ;q,q^k)$. As a consequence, we describe an operator whose eigenvalues characterize the polynomials $P_{\lambda} (\mathbb{X} ;q,q^k)$.

Nous nous intéressons aux propriétés des polynômes de Macdonald symétriques $P_{\lambda} (\mathbb{X} ;q,t)$ pour la spécialisation $t=q^k$. En particulier nous montrons une égalité reliant les polynômes $P_{\lambda} (\mathbb{X} ;q,q^k)$ et $P_{\lambda} (\frac{1-q}{1-q^k}\mathbb{X} ;q,q^k)$. Nous en déduisons la description d'un opérateur dont les valeurs propres caractérisent les polynômes $P_{\lambda} (\mathbb{X} ;q,q^k)$.
Linear time recognition of P4-indifference graphs
Authors: Habib Michel , Paul Christophe , Viennot Laurent
Published: August 2021

A graph is a P4-indifference graph if it admits an ordering < on its vertices such that every chordless path with vertices a, b, c, d and edges ab, bc, cd has a
Geometry and complexity of O'Hara's algorithm
Authors: Konvalinka Matjaž , Pak Igor
Published: August 2021

In this paper we analyze O'Hara's partition bijection. We present three type of results. First, we see that O'Hara's bijection can be viewed geometrically as a certain scissor congruence type result. Second, we present a number of new complexity bounds, proving that O'Hara's bijection is efficient in most cases and mildly exponential in general. Finally, we see that for identities with finite support, the map of the O'Hara's bijection can be computed in polynomial time, i.e. much more efficiently than by O'Hara's construction.
Combinatorial Formulas for Macdonald and Hall-Littlewood Polynomials
Authors: Lenart Cristian
Published: August 2021

A breakthrough in the theory of (type $A$) Macdonald polynomials is due to Haglund, Haiman and Loehr, who exhibited a combinatorial formula for these polynomials in terms of fillings of Young diagrams. Recently, Ram and Yip gave a formula for the Macdonald polynomials of arbitrary type in terms of the corresponding affine Weyl group. In this paper, we show that a Haglund-Haiman-Loehr type formula follows naturally from the more general Ram-Yip formula, via compression. Then we extend this approach to the Hall-Littlewood polynomials of type $C$, which are specializations of the corresponding Macdonald polynomials at $q=0$. We note that no analog of the Haglund-Haiman-Loehr formula exists beyond type $A$, so our work is a first step towards finding such a formula.
Bounds of asymptotic occurrence rates of some patterns in binary words related to integer-valued logistic maps
Authors: Nuida Koji
Published: August 2021

In this article, we investigate the asymptotic occurrence rates of specific subwords in any infinite binary word. We prove that the asymptotic occurrence rate for the subwords is upper- and lower-bounded in the same way for every infinite binary word, in terms of the asymptotic occurrence rate of the zeros. We also show that both of the bounds are best-possible by constructing, for each bound, a concrete infinite binary word such that the bound is reached. Moreover, we apply the result to analyses of recently-proposed pseudorandom number generators that are based on integer-valued variants of logistic maps.

Dans cet article, nous étudions les fréquences asymptotiques d’occurrence de suites spécifiques dans tout mot binaire infini. Nous prouvons que la fréquence asymptotique d’occurrence pour ces suites est borné supérieurement et inférieurement de la même façon pour chaque mot binaire infini, en termes des fréquences asymptotiques d’occurrence de zéros. Nous montrons aussi que les deux limites sont les meilleures possibles en construisant concrètement, pour chaque limite, un mot binaire infini tel que la borne est atteinte à la limite. De plus, nous appliquons ce résultat à des analyses de générateurs de nombres pseudo-aléatoires proposés récemment qui sont basés sur des variantes des fonctions logistiques à valeurs entières.
Branching rules in the ring of superclass functions of unipotent upper-triangular matrices
Authors: Thiem Nathaniel
Published: August 2021

It is becoming increasingly clear that the supercharacter theory of the finite group of unipotent upper-triangular matrices has a rich combinatorial structure built on set-partitions that is analogous to the partition combinatorics of the classical representation theory of the symmetric group. This paper begins by exploring a connection to the ring of symmetric functions in non-commuting variables that mirrors the symmetric group's relationship with the ring of symmetric functions. It then also investigates some of the representation theoretic structure constants arising from the restriction, tensor products and superinduction of supercharacters.
Unification of Higher-order Patterns modulo Simple Syntactic Equational Theories
Authors: Boudet Alexandre
Published: August 2021

We present an algorithm for unification of higher-order patterns modulo simple syntactic equational theories as defined by Kirchner [14]. The algorithm by Miller [17] for pattern unification, refined by Nipkow [18] is first modified in order to behave as a first-order unification algorithm. Then the mutation rule for syntactic theories of Kirchner [13,14] is adapted to pattern E-unification. If the syntactic algorithm for a theory E terminates in the first-order case, then our algorithm will also terminate for pattern E-unification. The result is a DAG-solved form plus some equations of the form λ øverlinex.F(øverlinex) = λ øverlinex. F(øverlinex^π ) where øverlinex^π is a permutation of øverlinex When all function symbols are decomposable these latter equations can be discarded, otherwise the compatibility of such equations with the solved form remains open.
Noncrossing partitions and the shard intersection order
Authors: Reading Nathan
Published: August 2021

We define a new lattice structure (W,\preceq ) on the elements of a finite Coxeter group W. This lattice, called the \emphshard intersection order, is weaker than the weak order and has the noncrossing partition lattice \NC (W) as a sublattice. The new construction of \NC (W) yields a new proof that \NC (W) is a lattice. The shard intersection order is graded and its rank generating function is the W-Eulerian polynomial. Many order-theoretic properties of (W,\preceq ), like Möbius number, number of maximal chains, etc., are exactly analogous to the corresponding properties of \NC (W). There is a natural dimension-preserving bijection between simplices in the order complex of (W,\preceq ) (i.e. chains in (W,\preceq )) and simplices in a certain pulling triangulation of the W-permutohedron. Restricting the bijection to the order complex of \NC (W) yields a bijection to simplices in a pulling triangulation of the W-associahedron. The lattice (W,\preceq ) is defined indirectly via the polyhedral geometry of the reflecting hyperplanes of W\!. Indeed, most of the results of the paper are proven in the more general setting of simplicial hyperplane arrangements.
A permutations representation that knows what "Eulerian" means
Authors: Mantaci Roberto , Rakotondrajao Fanja
Published: August 2021

Eulerian numbers (and ''Alternate Eulerian numbers'') are often interpreted as distributions of statistics defined over the Symmetric group. The main purpose of this paper is to define a way to represent permutations that provides some other combinatorial interpretations of these numbers. This representation uses a one-to-one correspondence between permutations and the so-called \emphsubexceedant functions.
k-Parabolic Subspace Arrangements
Authors: Severs Christopher , White Jacob
Published: August 2021

In this paper, we study k-parabolic arrangements, a generalization of the k-equal arrangement for any finite real reflection group. When k=2, these arrangements correspond to the well-studied Coxeter arrangements. Brieskorn (1971) showed that the fundamental group of the complement of the type W Coxeter arrangement (over $\mathbb{C}$) is isomorphic to the pure Artin group of type W. Khovanov (1996) gave an algebraic description for the fundamental group of the complement of the 3-equal arrangement (over $\mathbb{R}$). We generalize Khovanov's result to obtain an algebraic description of the fundamental group of the complement of the 3-parabolic arrangement for arbitrary finite reflection group. Our description is a real analogue to Brieskorn's description.

Nous généralisons les arrangements k-égaux à tous les groupes de réflexions finis réels. Les arrangements ainsi obtenus sont dits k-paraboliques. Dans le cas où k = 2 nous retrouvons les arrangements de Coxeter qui sont bien connus. En 1971, Brieskorn démontra que le groupe fondamental associé au complément (complexe) de l'arrangement de Coxeter de type W est en fait isomorphe au groupe pure d'Artin de type W . En 1996, Khovanov donne une description algébrique du groupe fondamental du complément (réel) de l'arrangement 3-égaux. Nous généralisons le résultat de Khovanov et obtenons une description algébrique du groupe fondamental de l'espace complément d'un arrangement k-parabolique pour tous les groupes de réflexions finis et réels. Il se trouve que notre description est l'analogue réel de la description de Brieskorn.
A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests
Authors: Shin Heesung , Zeng Jiang
Published: August 2021

For a fixed sequence of $n$ positive integers $(a,\bar{b}) := (a, b, b,\ldots, b)$, an $(a,\bar{b})$-parking function of length $n$ is a sequence $(p_1, p_2, \ldots, p_n)$ of positive integers whose nondecreasing rearrangement $q_1 \leq q_2 \leq \cdots \leq q_n$ satisfies $q_i \leq a+(i-1)b$ for any $i=1,\ldots, n$. A $(a,\bar{b})$-forest on $n$-set is a rooted vertex-colored forests on $n$-set whose roots are colored with the colors $0, 1, \ldots, a-1$ and the other vertices are colored with the colors $0, 1, \ldots, b-1$. In this paper, we construct a bijection between $(bc,\bar{b})$-parking functions of length $n$ and $(bc,\bar{b})$-forests on $n$-set with some interesting properties. As applications, we obtain a generalization of Gessel and Seo's result about $(c,\bar{1})$-parking functions [Ira M. Gessel and Seunghyun Seo, Electron. J. Combin. $\textbf{11}$(2)R27, 2004] and a refinement of Yan's identity [Catherine H. Yan, Adv. Appl. Math. $\textbf{27}$(2―3):641―670, 2001] between an inversion enumerator for $(bc,\bar{b})$-forests and a complement enumerator for $(bc,\bar{b})$-parking functions.

Soit $(a,\bar{b}) := (a, b, b,\ldots, b)$ une suite d'entiers positifs. Une $(a,\bar{b})$-fonction de parking est une suite $(p_1, p_2, \ldots, p_n)$ d'entiers positives telle que son réarrangement non décroissant $q_1 \leq q_2 \leq \cdots \leq q_n$ satisfait $q_i \leq a+(i-1)b$ pour tout $i=1,\ldots, n$. Une $(a,\bar{b})$-forêt enracinée sur un $n$-ensemble est une forêt enracinée dont les racines sont colorées avec les couleurs $0, 1, \ldots, a-1$ et les autres sommets sont colorés avec les couleurs $0, 1, \ldots, b-1$. Dans cet article, on construit une bijection entre $(bc,\bar{b})$-fonctions de parking et $(bc,\bar{b})$-forêts avec des des propriétés intéressantes. Comme applications, on obtient une généralisation d'un résultat de Gessel-Seo sur $(c,\bar{1})$-fonctions de parking [Ira M. Gessel and Seunghyun Seo, Electron. J. Combin. $\textbf{11}$(2)R27, 2004] et une extension de l'identité de Yan [Catherine H. Yan, Adv. Appl. Math. $\textbf{27}$(2―3):641―670, 2001] entre l'énumérateur d'inversion de $(bc,\bar{b})$-forêts et l'énumérateur complémentaire de $(bc,\bar{b})$-fonctions de parking.
Enumeration of the distinct shuffles of permutations
Authors: Smith Barnes Camillia
Published: August 2021

A shuffle of two words is a word obtained by concatenating the two original words in either order and then sliding any letters from the second word back past letters of the first word, in such a way that the letters of each original word remain spelled out in their original relative order. Examples of shuffles of the words $1234$ and $5678$ are, for instance, $15236784$ and $51236748$. In this paper, we enumerate the distinct shuffles of two permutations of any two lengths, where the permutations are written as words in the letters $1,2,3,\ldots ,m$ and $1,2,3,\ldots ,n$, respectively.
Shortest path poset of finite Coxeter groups
Authors: Blanco Saúl A.
Published: August 2021

We define a poset using the shortest paths in the Bruhat graph of a finite Coxeter group $W$ from the identity to the longest word in $W, w_0$. We show that this poset is the union of Boolean posets of rank absolute length of $w_0$; that is, any shortest path labeled by reflections $t_1,\ldots,t_m$ is fully commutative. This allows us to give a combinatorial interpretation to the lowest-degree terms in the complete $\textbf{cd}$-index of $W$.

Nous définissons un poset en utilisant le plus court chemin entre l'identité et le plus long mot de $W, w_0$, dans le graph de Bruhat du groupe finie Coxeter, $W$. Nous prouvons que ce poset est l'union de posets Boolean du même rang que la longueur absolute de $w_0$; ça signifie que tous les plus courts chemins, étiquetés par réflexions $t_1,\ldots, t_m$ sont totalement commutatives. Ça nous permet de donner une interprétation combinatoire aux termes avec le moindre grade dans le $\textbf{cd}$-index complet de $W$.
Enumeration of alternating sign matrices of even size (quasi)-invariant under a quarter-turn rotation
Authors: Aval Jean-Christophe , Duchon Philippe
Published: August 2021

The aim of this work is to enumerate alternating sign matrices (ASM) that are quasi-invariant under a quarter-turn. The enumeration formula (conjectured by Duchon) involves, as a product of three terms, the number of unrestrited ASm's and the number of half-turn symmetric ASM's.

L'objet de ce travail est d'énumérer les matrices à signes alternants (ASM) quasi-invariantes par rotation d'un quart-de-tour. La formule d'énumération, conjecturée par Duchon, fait apparaître trois facteurs, comprenant le nombre d'ASM quelconques et le nombre d'ASM invariantes par demi-tour.
Growth function for a class of monoids
Authors: Albenque Marie , Nadeau Philippe
Published: August 2021

In this article we study a class of monoids that includes Garside monoids, and give a simple combinatorial proof of a formula for the formal sum of all elements of the monoid. This leads to a formula for the growth function of the monoid in the homogeneous case, and can also be lifted to a resolution of the monoid algebra. These results are then applied to known monoids related to Coxeter systems: we give the growth function of the Artin-Tits monoids, and do the same for the dual braid monoids. In this last case we show that the monoid algebras of the dual braid monoids of type A and B are Koszul algebras.

Nous étudions une classe de monoïdes incluant les monoïdes de Garside, et donnons une preuve combinatoire simple d'une formule pour la somme formelle de leurs éléments. Cela mène à une formule pour la fonction de croissance du monoïde dans le cas homogène, et peut être aussi relevé en une résolution de l'algèbre de monoïdes. Ces résultats sont ensuite appliqués aux monoïdes liés aux systèmes de Coxeter : nous donnons la fonction de croissance des monoïdes d'Artin-Tits ainsi que des monoïdes duaux ; pour ces derniers nous montrons que leur algèbre de monoïde en types A et B est une algèbre de Koszul.
Permutations avoiding an increasing number of length-increasing forbidden subsequences
Authors: Barcucci Elena , Del Lungo Alberto , Pergola Elisa , Pinzani Renzo
Published: August 2021

A permutation π is said to be τ -avoiding if it does not contain any subsequence having all the same pairwise comparisons as τ . This paper concerns the characterization and enumeration of permutations which avoid a set F^j of subsequences increasing both in number and in length at the same time. Let F^j be the set of subsequences of the form σ (j+1)(j+2), σ being any permutation on \1,...,j\. For j=1 the only subsequence in F^1 is 123 and the 123-avoiding permutations are enumerated by the Catalan numbers; for j=2 the subsequences in F^2 are 1234 2134 and the (1234,2134)avoiding permutations are enumerated by the Schröder numbers; for each other value of j greater than 2 the subsequences in F^j are j! and their length is (j+2) the permutations avoiding these j! subsequences are enumerated by a number sequence \a_n\ such that C_n ≤ a_n ≤ n!, C_n being the nth Catalan number. For each j we determine the generating function of permutations avoiding the subsequences in F^j according to the length, to the number of left minima and of non-inversions.
Quasipolynomial formulas for the Kronecker coefficients indexed by two two―row shapes (extended abstract)
Authors: Briand Emmanuel , Orellana Rosa , Rosas Mercedes
Published: August 2021

We show that the Kronecker coefficients indexed by two two―row shapes are given by quadratic quasipolynomial formulas whose domains are the maximal cells of a fan. Simple calculations provide explicitly the quasipolynomial formulas and a description of the associated fan. These new formulas are obtained from analogous formulas for the corresponding reduced Kronecker coefficients and a formula recovering the Kronecker coefficients from the reduced Kronecker coefficients. As an application, we characterize all the Kronecker coefficients indexed by two two-row shapes that are equal to zero. This allowed us to disprove a conjecture of Mulmuley about the behavior of the stretching functions attached to the Kronecker coefficients.

Nous démontrons que les coefficients de Kronecker indexés par deux partitions de longueur au plus 2 sont donnés par des formules quasipolynomiales quadratiques dont les domaines de validité sont les cellules maximales d'un éventail. Des calculs simples nous donnent une description explicite des formules quasipolynomiales et de l'éventail associé. Ces nouvelles formulas sont obtenues de formules analogues pour les coefficients de Kronecker réduits correspondants et au moyen d'une formule reconstruisant les coefficients de Kronecker à partir des coefficients de Kronecker réduits. Une application est la caractérisation exacte de tous les coefficients de Kronecker non―nuls indexés par deux partitions de longueur au plus deux. Ceci nous a permis de réfuter une conjecture de Mulmuley au sujet des fonctions de dilatations associées aux coefficients de Kronecker.
Ordered Vertex Partitioning
Authors: Mcconnell Ross M. , Spinrad Jeremy P.
Published: August 2021

A transitive orientation of a graph is an orientation of the edges that produces a transitive digraph. The modular decomposition of a graph is a canonical representation of all of its modules. Finding a transitive orientation and finding the modular decomposition are in some sense dual problems. In this paper, we describe a simple O(n + m \log n) algorithm that uses this duality to find both a transitive orientation and the modular decomposition. Though the running time is not optimal, this algorithm is much simpler than any previous algorithms that are not Ω (n^2). The best known time bounds for the problems are O(n+m) but they involve sophisticated techniques.
New Hopf Structures on Binary Trees
Authors: Forcey Stefan , Lauve Aaron , Sottile Frank
Published: August 2021

The multiplihedra $\mathcal{M}_{\bullet} = (\mathcal{M}_n)_{n \geq 1}$ form a family of polytopes originating in the study of higher categories and homotopy theory. While the multiplihedra may be unfamiliar to the algebraic combinatorics community, it is nestled between two families of polytopes that certainly are not: the permutahedra $\mathfrak{S}_{\bullet}$ and associahedra $\mathcal{Y}_{\bullet}$. The maps $\mathfrak{S}_{\bullet} \twoheadrightarrow \mathcal{M}_{\bullet} \twoheadrightarrow \mathcal{Y}_{\bullet}$ reveal several new Hopf structures on tree-like objects nestled between the Hopf algebras $\mathfrak{S}Sym$ and $\mathcal{Y}Sym$. We begin their study here, showing that $\mathcal{M}Sym$ is a module over $\mathfrak{S}Sym$ and a Hopf module over $\mathcal{Y}Sym$. An elegant description of the coinvariants for $\mathcal{M}Sym$ over $\mathcal{Y}Sym$ is uncovered via a change of basis-using Möbius inversion in posets built on the $1$-skeleta of $\mathcal{M}_{\bullet}$. Our analysis uses the notion of an $\textit{interval retract}$ that should be of independent interest in poset combinatorics. It also reveals new families of polytopes, and even a new factorization of a known projection from the associahedra to hypercubes.

Les multiplièdres $\mathcal{M}_{\bullet} = (\mathcal{M}_n)_{n \geq 1}$ forment une famille de polytopes en provenant de l'étude des catégories supérieures et de la théorie de l'homotopie. Tandis que les multiplihèdres sont peu connus dans la communauté de la combinatoire algébrique, ils sont nichés entre deux familles des polytopes qui sont bien connus: les permutahèdres $\mathfrak{S}_{\bullet}$ et les associahèdres $\mathcal{Y}_{\bullet}$. Les morphismes $\mathfrak{S}_{\bullet} \twoheadrightarrow \mathcal{M}_{\bullet} \twoheadrightarrow \mathcal{Y}_{\bullet}$ dévoilent plusieurs nouvelles structures de Hopf sur les arbres binaires entre les algèbres de Hopf $\mathfrak{S}Sym$ et $\mathcal{Y}Sym$. Nous commençons son étude ici, en démontrant que $\mathcal{M}Sym$ est un module sur $\mathfrak{S}Sym$ et un module de Hopf sur $\mathcal{Y}Sym$. Une description élégante des coinvariants de $\mathcal{M}Sym$ sur $\mathcal{Y}Sym$ est trouvée par moyen d'une change de base―en utilisant une inversion de Möbius dans certains posets construits sur le $1$-squelette de $\mathcal{M}_{\bullet}$. Notre analyse utilise la notion d'$\textit{interval retract}$, qui devrait être intéressante par soi-même dans la théorie des ensembles partiellement ordonnés. Notre analyse donne lieu également à des nouvelles familles des polytopes, et même une nouvelle factorisation d'une projection connue des associahèdres aux hypercubes.
Perfectness of Kirillov―Reshetikhin crystals for nonexceptional types
Authors: Fourier Ghislain , Okado Masato , Schilling Anne
Published: August 2021

For nonexceptional types, we prove a conjecture of Hatayama et al. about the prefectness of Kirillov―Reshetikhin crystals.

Pour les types non-exceptionnels, on démontre une conjecture de Hatayama et al. concernant la perfection des cristaux de Kirillov―Reshetikhin.
Improved inclusion-exclusion identities via closure operators
Authors: Dohmen Klaus
Published: August 2021

Let (A_v)_v ∈ V be a finite family of sets. We establish an improved inclusion-exclusion identity for each closure operator on the power set of V having the unique base property. The result generalizes three improvements of the inclusion-exclusion principle as well as Whitney's broken circuit theorem on the chromatic polynomial of a graph.
Characters of symmetric groups in terms of free cumulants and Frobenius coordinates
Authors: Dolega Maciej , Féray Valentin , Sniady Piotr
Published: August 2021

Free cumulants are nice and useful functionals of the shape of a Young diagram, in particular they give the asymptotics of normalized characters of symmetric groups $\mathfrak{S}(n)$ in the limit $n \to \infty$. We give an explicit combinatorial formula for normalized characters of the symmetric groups in terms of free cumulants. We also express characters in terms of Frobenius coordinates. Our formulas involve counting certain factorizations of a given permutation. The main tool are Stanley polynomials which give values of characters on multirectangular Young diagrams.

Les cumulants libres sont des fonctions agréables et utiles sur l'ensemble des diagrammes de Young, en particulier, ils donnent le comportement asymptotiques des caractères normalisés du groupe symétrique $\mathfrak{S}(n)$ dans la limite $n \to \infty$. Nous donnons une formule combinatoire explicite pour les caractères normalisés du groupe symétrique en fonction des cumulants libres. Nous exprimons également les caractères en fonction des coordonnées de Frobenius. Nos formules font intervenir le nombre de certaines factorisations d'une permutation donnée. L'outil principal est la famille de polynômes de Stanley donnant les valeurs des caractères sur les diagrammes de Young multirectangulaires.
The Size of One-Way Cellular Automata
Authors: Kutrib Martin , Lefèvre Jonas , Malcher Andreas
Published: August 2021

We investigate the descriptional complexity of basic operations on real-time one-way cellular automata with an unbounded as well well as a fixed number of cells. The size of the automata is measured by their number of states. Most of the bounds shown are tight in the order of magnitude, that is, the sizes resulting from the effective constructions given are optimal with respect to worst case complexity. Conversely, these bounds also show the maximal savings of size that can be achieved when a given minimal real-time OCA is decomposed into smaller ones with respect to a given operation. From this point of view the natural problem of whether a decomposition can algorithmically be solved is studied. It turns out that all decomposition problems considered are algorithmically unsolvable. Therefore, a very restricted cellular model is studied in the second part of the paper, namely, real-time one-way cellular automata with a fixed number of cells. These devices are known to capture the regular languages and, thus, all the problems being undecidable for general one-way cellular automata become decidable. It is shown that these decision problems are $\textsf{NLOGSPACE}$-complete and thus share the attractive computational complexity of deterministic finite automata. Furthermore, the state complexity of basic operations for these devices is studied and upper and lower bounds are given.
The fractal structure of cellular automata on abelian groups
Authors: Gütschow Johannes , Nesme Vincent , Werner Reinhard F.
Published: August 2021

It is a well-known fact that the spacetime diagrams of some cellular automata have a fractal structure: for instance Pascal's triangle modulo $2$ generates a Sierpinski triangle. Explaining the fractal structure of the spacetime diagrams of cellular automata is a much explored topic, but virtually all of the results revolve around a special class of automata, whose main features include irreversibility, an alphabet with a ring structure and a rule respecting this structure, and a property known as being (weakly) $p$-Fermat. The class of automata that we study in this article fulfills none of these properties. Their cell structure is weaker and they are far from being $p$-Fermat, even weakly. However, they do produce fractal spacetime diagrams, and we will explain why and how. These automata emerge naturally from the field of quantum cellular automata, as they include the classical equivalent of the Clifford quantum cellular automata, which have been studied by the quantum community for several reasons. They are a basic building block of a universal model of quantum computation, and they can be used to generate highly entangled states, which are a primary resource for measurement-based models of quantum computing.
Probabilistic initial value problem for cellular automaton rule 172
Authors: Fuks Henryk
Published: August 2021

We present a method of solving of the probabilistic initial value problem for cellular automata (CA) using CA rule 172 as an example. For a disordered initial condition on an infinite lattice, we derive exact expressions for the density of ones at arbitrary time step. In order to do this, we analyze topological structure of preimage trees of finite strings of length 3. Level sets of these trees can be enumerated directly using classical combinatorial methods, yielding expressions for the number of $n$-step preimages of all strings of length 3, and, subsequently, probabilities of occurrence of these strings in a configuration obtained from the initial one after $n$ iterations of rule 172. The density of ones can be expressed in terms of Fibonacci numbers, while expressions for probabilities of other strings involve Lucas numbers. Applicability of this method to other CA rules is briefly discussed.
Phase transitions in Proof Theory
Authors: Gordeev Lev , Weiermann Andreas
Published: August 2021

Using standard methods of analytic combinatorics we elaborate critical points (thresholds) of phase transitions from provability to unprovability of arithmetical well-partial-ordering assertions in several familiar theories occurring in the reverse mathematics program.
On unary nodes in tries
Authors: Wagner Stephan
Published: August 2021

The difference between ordinary tries and Patricia tries lies in the fact that all unary nodes are removed in the latter. Their average number is thus easily determined from earlier results on the size of tries/Patricia tries. In a well-known contention resolution algorithm, whose probabilistic model is essentially equivalent to tries, unary nodes correspond to repetitions, i.e., steps in the algorithm that do not resolve anything at all. In this paper, we take an individual's view on such repetitions: we consider the distribution of the number of repetitions a certain contender encounters in the course of the algorithm―-which is equivalent to the number of unary nodes on the path from the root to a random string in a trie. We encounter an example of a sequence of distributions that does not actually converge to a limit distribution, but rather oscillates around a (discrete) limit distribution.
Ordered increasing $k$-trees: Introduction and analysis of a preferential attachment network model
Authors: Panholzer Alois , Seitz Georg
Published: August 2021

We introduce a random graph model based on $k$-trees, which can be generated by applying a probabilistic preferential attachment rule, but which also has a simple combinatorial description. We carry out a precise distributional analysis of important parameters for the network model such as the degree, the local clustering coefficient and the number of descendants of the nodes and root-to-node distances. We do not only obtain results for random nodes, but in particular we also get a precise description of the behaviour of parameters for the $j$-th inserted node in a random $k$-tree of size $n$, where $j=j(n)$ might grow with $n$. The approach presented is not restricted to this specific $k$-tree model, but can also be applied to other evolving $k$-tree models.
Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort (Extended Abstract)
Authors: fill james Allen
Published: August 2021

Most previous studies of the sorting algorithm $\mathtt{QuickSort}$ have used the number of key comparisons as a measure of the cost of executing the algorithm. Here we suppose that the $n$ independent and identically distributed (iid) keys are each represented as a sequence of symbols from a probabilistic source and that $\mathtt{QuickSort}$ operates on individual symbols, and we measure the execution cost as the number of symbol comparisons. Assuming only a mild "tameness'' condition on the source, we show that there is a limiting distribution for the number of symbol comparisons after normalization: first centering by the mean and then dividing by $n$. Additionally, under a condition that grows more restrictive as $p$ increases, we have convergence of moments of orders $p$ and smaller. In particular, we have convergence in distribution and convergence of moments of every order whenever the source is memoryless, i.e., whenever each key is generated as an infinite string of iid symbols. This is somewhat surprising: Even for the classical model that each key is an iid string of unbiased ("fair'') bits, the mean exhibits periodic fluctuations of order $n$.
Word equations in a uniquely divisible group
Authors: Hillar Christopher J. , Levine Lionel , Rhea Darren
Published: August 2021

We study equations in groups $G$ with unique $m$-th roots for each positive integer $m$. A word equation in two letters is an expression of the form$ w(X,A) = B$, where $w$ is a finite word in the alphabet ${X,A}$. We think of $A,B ∈G$ as fixed coefficients, and $X ∈G$ as the unknown. Certain word equations, such as $XAXAX=B$, have solutions in terms of radicals: $X = A^-1/2(A^1/2BA^1/2)^1/3A^-1/2$, while others such as $X^2 A X = B$ do not. We obtain the first known infinite families of word equations not solvable by radicals, and conjecture a complete classification. To a word w we associate a polynomial $P_w ∈ℤ[x,y]$ in two commuting variables, which factors whenever $w$ is a composition of smaller words. We prove that if $P_w(x^2,y^2)$ has an absolutely irreducible factor in $ℤ[x,y]$, then the equation $w(X,A)=B$ is not solvable in terms of radicals.

Nous étudions des équations dans les groupes $G$ avec les $m$-th racines uniques pour chaque nombre entier positif m. Une équation de mot dans deux lettres est une expression de la forme $w(X, A) = B$, où $w$ est un mot fini dans l'alphabet ${X, A}$. Nous pensons $A, B ∈G$ en tant que coefficients fixes, et $X ∈G$ en tant que inconnu. Certaines équations de mot, telles que $XAXAX=B$, ont des solutions en termes de radicaux: $X = A^-1/2(A^1/2BA^1/2)^1/3A^-1/2$, alors que d'autres tel que $X^2 A X = B$ ne font pas. Nous obtenons les familles infinies d'abord connues des équations de mot non solubles par des radicaux, et conjecturons une classification complété. Á un mot $w$ nous associons un polynôme $P_w ∈ℤ[x, y]$ dans deux variables de permutation, qui factorise toutes les fois que $w$ est une composition de plus petits mots. Nous montrons que si $P_w(x^2, y^2)$ a un facteur absolument irréductible dans $ℤ[x, y]$, alors l'équation $w(X, A)=B$ n'est pas soluble en termes de radicaux.
Chain enumeration of k-divisible noncrossing partitions of classical types
Authors: Kim Jang Soo
Published: August 2021

We give combinatorial proofs of the formulas for the number of multichains in the $k-divisible$ noncrossing partitions of classical types with certain conditions on the rank and the block size due to Krattenthaler and Müller. We also prove Armstrong's conjecture on the zeta polynomial of the poset of k-divisible noncrossing partitions of type A invariant under the 180° rotation in the cyclic representation.

Nous donnons une preuve combinatoire de la formule pour le nombre de multichaînes dans les partitions $k-divisibles$ non-croisées de type classique avec certaines conditions sur le rang et la taille du bloc due à Krattenthaler et Müller. Nous prouvons aussi la conjecture d'Amstrong sur le polynôme zeta du poset des partitions k-divisibles non-croisées de type A invariantes par la rotation de 180° dans la représentation cyclique.
The Frobenius Complex
Authors: Clark Eric , Ehrenborg Richard
Published: August 2021

Motivated by the classical Frobenius problem, we introduce the Frobenius poset on the integers $\mathbb{Z}$, that is, for a sub-semigroup $\Lambda$ of the non-negative integers $(\mathbb{N},+)$, we define the order by $n \leq_{\Lambda} m$ if $m-n \in \Lambda$. When $\Lambda$ is generated by two relatively prime integers $a$ and $b$, we show that the order complex of an interval in the Frobenius poset is either contractible or homotopy equivalent to a sphere. We also show that when $\Lambda$ is generated by the integers $\{a,a+d,a+2d,\ldots,a+(a-1)d\}$, the order complex is homotopy equivalent to a wedge of spheres.

Motivé par le problème de Frobenius classique, nous introduisons l'ensemble partiellement ordonné de Frobenius sur les entiers $\mathbb{Z}$, c.à.d. que pour un sous-semigroupe $\Lambda$ de les entiers non-négatifs $(\mathbb{N},+)$ nous définissons l'ordre par $n \leq_{\Lambda} m$ si $m-n \in \Lambda$. Quand le $\Lambda$ est engendré par deux nombres $a$ et $b$, relativement premiers entre eux, nous montrons que le complexe des chaînes d'un intervalle quelconque dans l'ensemble partiellement ordonné de Frobenius est soit contractible soit homotopiquement équivalent à une sphère. Nous montrons aussi que dans le cas où $\Lambda$ est engendré par les entiers $\{a,a+d,a+2d,\ldots,a+(a-1)d\}$, le complexe des chaînes a le type de homotopie d'un bouquet de sphères.
$n!$ matchings, $n!$ posets (extended abstract)
Authors: Claesson Anders , Linusson Svante
Published: August 2021

We show that there are $n!$ matchings on $2n$ points without, so called, left (neighbor) nestings. We also define a set of naturally labelled $(2+2)$-free posets, and show that there are $n!$ such posets on $n$ elements. Our work was inspired by Bousquet-Mélou, Claesson, Dukes and Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884―909]. They gave bijections between four classes of combinatorial objects: matchings with no neighbor nestings (due to Stoimenow), unlabelled $(2+2)$-free posets, permutations avoiding a specific pattern, and so called ascent sequences. We believe that certain statistics on our matchings and posets could generalize the work of Bousquet-Mélou et al. and we make a conjecture to that effect. We also identify natural subsets of matchings and posets that are equinumerous to the class of unlabeled $(2+2)$-free posets. We give bijections that show the equivalence of (neighbor) restrictions on nesting arcs with (neighbor) restrictions on crossing arcs. These bijections are thought to be of independent interest. One of the bijections maps via certain upper-triangular integer matrices that have recently been studied by Dukes and Parviainen [Electron. J. Combin. 17 (2010) #R53].

Nous montrons qu'il y a $n!$ couplages sur $2n$ points sans emboîtement (de voisins) à gauche. Nous définissons aussi un ensemble d'EPO (ensembles partiellement ordonnés) sans motif $(2+2)$ naturellement étiquetés, et montrons qu'il y a $n!$ tels EPO sur $n$ éléments. Notre travail a été inspiré par Bousquet-Mélou, Claesson, Dukes et Kitaev [J. Combin. Theory Ser. A. 117 (2010) 884―909]. Ces auteurs donnent des bijections entre quatre classes d'objets combinatoires: couplages sans emboîtement de voisins (dû à Stoimenow), EPO sans motif $(2+2)$ non étiquetés, permutations évitant un certain motif, et des objets appelés suites à montées. Nous pensons que certaines statistiques sur nos couplages et nos EPO pourraient généraliser le travail de Bousquet-Mélou et al. et nous proposons une conjecture à ce sujet. Nous identifions aussi des sous-ensembles naturels de couplages et d'EPO qui sont énumérés par la même séquence que la classe des EPO sans motif $(2+2)$ non étiquetés. Nous donnons des bijections qui démontrent l'équivalence entre les restrictions sur les emboîtements (d'arcs voisins) et les restrictions sur les croisements (d'arcs voisins). Nous pensons que ces bijections présentent un intérêt propre. L'une de ces bijections passe par certaines matrices triangulaires supérieures à coefficients entiers qui ont été récemment étudiées par Dukes et Parviainen [Electron. J. Combin. 17 (2010) #R53].