bluuebunny/crossref_metadata_2025 huggingface dataset:
Formal Group Laws and Chromatic Symmetric Functions of Hypergraphs
Authors: Taylor Jair
Published: August 2021

If $f(x)$ is an invertible power series we may form the symmetric function $f(f^{-1}(x_1)+f^{-1}(x_2)+...)$ which is called a formal group law. We give a number of examples of power series $f(x)$ that are ordinary generating functions for combinatorial objects with a recursive structure, each of which is associated with a certain hypergraph. In each case, we show that the corresponding formal group law is the sum of the chromatic symmetric functions of these hypergraphs by finding a combinatorial interpretation for $f^{-1}(x)$. We conjecture that the chromatic symmetric functions arising in this way are Schur-positive.

Si $f(x)$ est une série entière inversible, nous pouvons former la fonction symétrique $f(f^{-1}(x_1)+f^{-1}(x_2)+...)$ que nous appelons une loi de groupe formel. Nous donnons plusieurs exemples de séries entières $f(x)$ qui sont séries génératrices ordinaires pour des objets combinatoires avec une structure récursive, chacune desquelles est associée à un certain hypergraphe. Dans chaque cas, nous donnons une interprétation combinatoire à $f^{-1}(x)$, ce qui nous permet de montrer que la loi de groupe formel correspondante est la somme des fonctions symétriques chromatiques de ces hypergraphes. Nous conjecturons que les fonctions symétriques chromatiques apparaissant de cette manière sont Schur-positives.
Object grammars and random generation
Authors: Dutour I. , Fedou Jean-Marc
Published: August 2021

This paper presents a new systematic approach for the uniform random generation of combinatorial objects. The method is based on the notion of object grammars which give recursive descriptions of objects and generalize context-freegrammars. The application of particular valuations to these grammars leads to enumeration and random generation of objects according to non algebraic parameters.
Combinatorial Hopf Algebras of Simplicial Complexes
Authors: Benedetti Carolina , Hallam Joshua , Machacek John
Published: August 2021

We consider a Hopf algebra of simplicial complexes and provide a cancellation-free formula for its antipode. We then obtain a family of combinatorial Hopf algebras by defining a family of characters on this Hopf algebra. The characters of these Hopf algebras give rise to symmetric functions that encode information about colorings of simplicial complexes and their $f$-vectors. We also use characters to give a generalization of Stanley’s $(-1)$-color theorem.

Nous considérons une algèbre de Hopf de complexes simpliciaux et fournissons une formule sans multiplicité pour son antipode. On obtient ensuite une famille d'algèbres de Hopf combinatoires en définissant une famille de caractères sur cette algèbre de Hopf. Les caractères de ces algèbres de Hopf donnent lieu à des fonctions symétriques qui encode de l’information sur les coloriages du complexe simplicial ainsi que son vecteur-$f$. Nousallons également utiliser des caractères pour donner une généralisation du théorème $(-1)$ de Stanley.
Fan realizations of type $A$ subword complexes and multi-associahedra of rank 3
Authors: Bergeron Nantel , Ceballos Cesar , Labbé Jean-Philippe
Published: August 2021

We present complete simplicial fan realizations of any spherical subword complex of type $A_n$ for $n\leq 3$. This provides complete simplicial fan realizations of simplicial multi-associahedra $\Delta_{2k+4,k}$, whose facets are in correspondence with $k$-triangulations of a convex $(2k+4)$-gon. This solves the first open case of the problem of finding fan realizations where polytopality is not known. The techniques presented in this paper work for all finite Coxeter groups and we hope that they will be useful to construct fans realizing subword complexes in general. In particular, we present fan realizations of two previously unknown cases of subword complexes of type $A_4$, namely the multi-associahedra $\Delta_{9,2}$ and $\Delta_{11,3}$.

Nous construisons des éventails simpliciaux complets ayant la combinatoire des complexes de sous-mots de type $A_n$ pour $n\leq 3$. Par conséquent, nous obtenons des constructions d’éventails des multi-associaèdres $\Delta_{2k+4,k}$, dont les facettes correspondent aux $k$-triangulations d’un $(2k+4)$-gone. Cette construction confirme l’existence d’éventails ayant la combinatoire du multi-associaèdres pour une famille dont la polytopalité n’est pas confirmée. Les techniques utilisées fonctionnent pour tous les groupes de Coxeter et nous espérons qu’elles seront utiles afin de construire des éventails réalisant les complexes de sous-mots en général. En particulier, nous présentons des éventails pour deux complexes de sous-mots de type $A_4$ dont l’existence était inconnue: les multi-associaèdres $\Delta_{9,2}$ et $\Delta_{11,3}$.
Sign variation, the Grassmannian, and total positivity
Authors: Karp Steven N.
Published: August 2021

The totally nonnegative Grassmannian is the set of $k$-dimensional subspaces $V$ of ℝ$n$ whose nonzero Plücker coordinates (i.e. $k × k$ minors of a $k × n$ matrix whose rows span $V$) all have the same sign. Total positivity has been much studied in the past two decades from an algebraic, combinatorial, and topological perspective, but first arose in the theory of oscillations in analysis. It was in the latter context that Gantmakher and Krein (1950) and Schoenberg and Whitney (1951) independently showed that a subspace $V$ is totally nonnegative iff every vector in $V$, when viewed as a sequence of $n$ numbers and ignoring any zeros, changes sign fewer than $k$ times. We generalize this result, showing that the vectors in $V$ change sign fewer than $l$ times iff certain sequences of the Plücker coordinates of some generic perturbation of $V$ change sign fewer than $l − k + 1$ times. We give an algorithm which constructs such a generic perturbation. Also, we determine the positroid cell of each totally nonnegative $V$ from sign patterns of vectors in $V$. These results generalize to oriented matroids.

La grassmannienne totalement non négative est l’ensemble des sous-espaces $V$ de ℝ$n$ de dimension $k$ dont coordonnées plückeriennes non nulles (mineurs de l’ordre $k$ d’une matrice $k × n$ dont les lignes engendrent $V$) ont toutes le même signe. La positivité totale a beaucoup été étudiée durant les deux dernières décennies d’une perspective algébrique, combinatoire, et topologique, mais a pris naissance dans la théorie analytique des oscillations. C’est dans ce contexte que Gantmakher et Krein (1950) et Schoenberg et Whitney (1951) ont indépendamment démontré qu’un sous-espace $V$ est totalement non négatif ssi chaque vecteur dans $V$, lorsque considéré comme une séquence de $n$ nombres et dont on ignore les zéros, change de signe moins de $k$ fois. Nous généralisons ce résultat, démontrant que les vecteurs dans $V$ changent de signe moins de $l$ fois ssi certaines séquences des coordonnées plückeriennes d’une perturbation générique de $V$ changent de signe moins de $l − k + 1$ fois. Un algorithme construisant une telle perturbation générique est obtenu. De plus, nous déterminons la cellule positroïde de chaque $V$ totalement non négatif à partir des données de signe des vecteurs dans $V$. Ces résultats sont valides pour les matroïdes orientés.
A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape
Authors: Burrill Sophie , Melczer Stephen , Mishna Marni
Published: August 2021

Tableau sequences of bounded height have been central to the analysis of $k$-noncrossing set partitions and matchings. We show here that families of sequences that end with a row shape are particularly compelling and lead to some interesting connections. First, we prove that hesitating tableaux of height at most two ending with a row shape are counted by Baxter numbers. This permits us to define three new Baxter classes which, remarkably, do not obviously possess the antipodal symmetry of other known Baxter classes. Oscillating tableau of height bounded by $k$ ending in a row are in bijection with Young tableaux of bounded height 2$k$. We discuss this recent result, and somegenerating function implications. Many of our proofs are analytic in nature, so there are intriguing combinatorial bijections to be found.

Les séquences de tableau de hauteur bornée sont au centre de l’analyse des partages et couplages. Nous montrons que les familles de séquences qui se terminent par une seule ligne sont particulièrement fascinantes. Tout d’abord, nous prouvons que les tableaux hésitants de hauteur au plus deux se terminant par une seule ligne sont dénombrés par les nombres de Baxter. Cela nous permet de définir trois nouvelles classes Baxter qui, remarquablement, ne possèdent évidemment pas la symétrie antipode des autres classes Baxter connus. Nous discutons le résultat récent qui dit que les tableaux oscillants de hauteur au plus $k$ se terminant dans une ligne sont en bijection avec les tableaux de Young de hauteur au plus 2$k$. Nos preuves sont analytiques, il y a donc des bijections combinatoiresintrigantes à trouver.
Semi-pointed partition posets
Authors: Delcroix-Oger Bérénice
Published: August 2021

We present here a family of posets which generalizes both partition and pointed partition posets. After a short description of these new posets, we show that they are Cohen-Macaulay, compute their Moebius numbers and their characteristic polynomials. The characteristic polynomials are obtained using a combinatorial interpretation of the incidence Hopf algebra associated to these posets.

Nous introduisons ici une famille de posets qui généralise à la fois les poset de partitions et les posets de partitions pointées. Après une description rapide de ces nouveaux posets, nous montrons qu’ils sont Cohen-Macaulay et nous calculons leurs nombres de Moebius et leurs polynômes caractéristiques. Ces derniers sont obtenus grâce à une interprétation combinatoire de l’algèbre de Hopf d’incidence associée à ces posets.
Tamari Lattices for Parabolic Quotients of the Symmetric Group
Authors: Mühle Henri , Williams Nathan
Published: August 2021

We present a generalization of the Tamari lattice to parabolic quotients of the symmetric group. More precisely, we generalize the notions of 231-avoiding permutations, noncrossing set partitions, and nonnesting set partitions to parabolic quotients, and show bijectively that these sets are equinumerous. Furthermore, the restriction of weak order on the parabolic quotient to the parabolic 231-avoiding permutations is a lattice quotient. Lastly, we suggest how to extend these constructions to all Coxeter groups.

Nous présentons une généralisation du treillis de Tamari aux quotients paraboliques du groupe symétrique. Plus précisément, nous généralisons les notions de permutations qui évitent le motif 231, les partitions non-croisées, et les partitions non-emboîtées aux quotients paraboliques, et nous montrons de façon bijective que ces ensembles sont équipotents. En restreignant l’ordre faible du quotient parabolique aux permutations paraboliques qui évitent le motif 231, on obtient un quotient de treillis d’ordre faible. Enfin, nous suggérons comment étendre ces constructions à tous les groupes de Coxeter.
How to get the weak order out of a digraph ?
Authors: Viard Francois
Published: August 2021

We construct a poset from a simple acyclic digraph together with a valuation on its vertices, and we compute the values of its Möbius function. We show that the weak order on Coxeter groups $A$$n-1$, $B$$n$, $Ã$$n$, and the flag weak order on the wreath product ℤ$r$ ≀ $S$$n$ introduced by Adin, Brenti and Roichman (2012), are special instances of our construction. We conclude by briefly explaining how to use our work to define quasi-symmetric functions, with a special emphasis on the $A$$n-1$ case, in which case we obtain the classical Stanley symmetric function.

On construit une famille d’ensembles ordonnés à partir d’un graphe orienté, simple et acyclique munit d’une valuation sur ses sommets, puis on calcule les valeurs de leur fonction de Möbius respective. On montre que l’ordre faible sur les groupes de Coxeter $A$$n-1$, $B$$n$, $Ã$$n$, ainsi qu’une variante de l’ordre faible sur les produits en couronne ℤ$r$ ≀ $S$$n$ introduit par Adin, Brenti et Roichman (2012), sont des cas particuliers de cette construction. On conclura en expliquant brièvement comment ce travail peut-être utilisé pour définir des fonction quasi-symétriques, en insistant sur l’exemple de l’ordre faible sur $A$$n-1$ où l’on obtient les séries de Stanley classiques.
The First-Order Theory of Ordering Constraints over Feature Trees
Authors: Müller Martin , Niehren Joachim , Treinen Ralf
Published: August 2021

The system FT< of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. We investigate the first-order theory of FT< and its fragments in detail, both over finite trees and over possibly infinite trees. We prove that the first-order theory of FT< is undecidable, in contrast to the first-order theory of FT which is well-known to be decidable. We show that the entailment problem of FT< with existential quantification is PSPACE-complete. So far, this problem has been shown decidable, coNP-hard in case of finite trees, PSPACE-hard in case of arbitrary trees, and cubic time when restricted to quantifier-free entailment judgments. To show PSPACE-completeness, we show that the entailment problem of FT< with existential quantification is equivalent to the inclusion problem of non-deterministic finite automata. Available at http://www.ps.uni-saarland.de/Publications/documents/FTSubTheory_98.pdf
The shifted plactic monoid (extended abstract)
Authors: Serrano Luis
Published: August 2021

We introduce a shifted analog of the plactic monoid of Lascoux and Schützenberger, the \emphshifted plactic monoid. It can be defined in two different ways: via the \emphshifted Knuth relations, or using Haiman's mixed insertion. Applications include: a new combinatorial derivation (and a new version of) the shifted Littlewood-Richardson Rule; similar results for the coefficients in the Schur expansion of a Schur P-function; a shifted counterpart of the Lascoux-Schützenberger theory of noncommutative Schur functions in plactic variables; a characterization of shifted tableau words; and more.
Refinements of the Littlewood-Richardson rule
Authors: Haglund J. , Luoto K. , Mason S. , van Willigenburg S.
Published: August 2021

We refine the classical Littlewood-Richardson rule in several different settings. We begin with a combinatorial rule for the product of a Demazure atom and a Schur function. Building on this, we also describe the product of a quasisymmetric Schur function and a Schur function as a positive sum of quasisymmetric Schur functions. Finally, we provide a combinatorial formula for the product of a Demazure character and a Schur function as a positive sum of Demazure characters. This last rule implies the classical Littlewood-Richardson rule for the multiplication of two Schur functions.

Nous décrivons trois nouvelles règles de Littlewood-Richardson, et chaque nouvelle règle partage la vieille règle de Littlewood-Richardson. La première règle multiplie un atome de Demazure et une fonction de Schur. La deuxième multiplie une fonction de quasisymmetric-Schur et une fonction de Schur. La troisième multiplie un caractère de Demazure et une fonction de Schur. Cette dernière règle est une description de la vieille règle de Littlewood-Richardson.
A new combinatorial identity for unicellular maps, via a direct bijective approach.
Authors: Chapuy Guillaume
Published: August 2021

We give a bijective operation that relates unicellular maps of given genus to unicellular maps of lower genus, with distinguished vertices. This gives a new combinatorial identity relating the number $\epsilon_g(n)$ of unicellular maps of size $n$ and genus $g$ to the numbers $\epsilon _j(n)$'s, for $j \lt g$. In particular for each $g$ this enables to compute the closed-form formula for $\epsilon_g(n)$ much more easily than with other known identities, like the Harer-Zagier formula. From the combinatorial point of view, we give an explanation to the fact that $\epsilon_g(n)=R_g(n) \mathrm{Cat}(n)$, where $\mathrm{Cat}(n$) is the $n$-th Catalan number and $R_g$ is a polynomial of degree $3g$, with explicit interpretation.

On décrit une opération bijective qui relie les cartes à une face de genre donné à des cartes à une face de genre inférieur, portant des sommets marqués. Cela conduit à une nouvelle identité combinatoire reliant le nombre $\epsilon_g(n)$ de cartes à une face de taille $n$ et genre $g$ aux nombres $\epsilon _j(n)$, pour $j \lt g$. En particulier, pour tout $g$, cela permet de calculer la formule close donnant $\epsilon_g(n)$ bien plus facilement qu'à l'aide des autres identités connues, comme la formule d'Harer-Zagier. Du point de vue combinatoire, nous donnons une explication au fait que $\epsilon _g(n)=R_g(n) \mathrm{Cat}(n)$, où $\mathrm{Cat}(n)$ est le $n$ième nombre de Catalan et $R_g$ est un polynôme de degré $3g$, à l'interprétation explicite.
Matrix Ansatz, lattice paths and rook placements
Authors: Corteel S. , Josuat-Vergès M. , Prellberg T. , Rubey M.
Published: August 2021

We give two combinatorial interpretations of the Matrix Ansatz of the PASEP in terms of lattice paths and rook placements. This gives two (mostly) combinatorial proofs of a new enumeration formula for the partition function of the PASEP. Besides other interpretations, this formula gives the generating function for permutations of a given size with respect to the number of ascents and occurrences of the pattern $13-2$, the generating function according to weak exceedances and crossings, and the $n^{\mathrm{th}}$ moment of certain $q$-Laguerre polynomials.

Nous donnons deux interprétations combinatoires du Matrix Ansatz du PASEP en termes de chemins et de placements de tours. Cela donne deux preuves (presque) combinatoires d'une nouvelle formule pour la fonction de partition du PASEP. Cette formule donne aussi par exemple la fonction génératrice des permutations de taille donnée par rapport au nombre de montées et d'occurrences du motif $13-2$, la fonction génératrice par rapport au nombre d'excédences faibles et de croisements, et le $n^{\mathrm{ième}}$ moment de certains polynômes de $q$-Laguerre.
On wiring and tiling diagrams related to bases of tropical Plücker functions
Authors: Danilov Vladimir I. , Karzanov Alexander V. , Koshevoy Gleb A.
Published: August 2021

We consider the class of bases $B$ of tropical Plücker functions on the Boolean $n$-cube such that $B$ can be obtained by a series of flips from the basis formed by the intervals of the ordered set of $n$ elements. We show that these bases are representable by special wiring diagrams and by certain arrangements generalizing rhombus tilings on a zonogon.
On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules
Authors: Tošić Predrag T.
Published: August 2021

We study how hard is to determine some fundamental properties of dynamics of certain types of network automata. We address the computational complexity of determining how many different possible dynamic evolutions can arise from some structurally very simple, deterministic and sparsely connected network automata. In this as well as our prior, related work, we try to push the limits on the underlying simplicity of two structural aspects of such network automata: (i) the uniform sparseness of their topologies, and (ii) severely restricted local behaviors of the individual agents (that is, the local update rules of the network nodes). In this endeavor, we prove that counting the Fixed Point (FP) configurations and the predecessor and ancestor configurations in two classes of network automata, called Sequential and Synchronous Dynamical Systems (SDSs and SyDSs, respectively), are computationally intractable problems. Moreover, this intractability is shown to hold when each node in such a network is required to update according to (i) a monotone Boolean function, (ii) a symmetric Boolean function, or even (iii) a simple threshold function that is both monotone and symmetric. Furthermore, the hardness of the exact enumeration of FPs and other types of configurations of interest remains to hold even in some severely restricted cases with respect to both the network topology and the diversity (or lack thereof) of individual node's local update rules. Namely, we show that the counting problems of interest remain hard even when the nodes of an SDS or SyDS use at most two different update rules from a given restricted class, and, additionally, when the network topologies are constrained so that each node has only $c = O(1)$ neighbors for small values of constant $c$. Our results also have considerable implications for other discrete dynamical system models studied in applied mathematics, physics, biology and computer science, such as Hopfield networks and spin glasses. In particular, one corollary of our results is that determining the memory capacity of sparse discrete Hopfield networks (viewed as associative memories) remains computationally intractable even when the interconnection and dependence structure among the nodes of a Hopfield network is severely restricted.
Avoiding maximal parabolic subgroups of S_k
Authors: Mansour Toufik , Vainshtein Alek
Published: August 2021

We find an explicit expression for the generating function of the number of permutations in S_n avoiding a subgroup of S_k generated by all but one simple transpositions. The generating function turns out to be rational, and its denominator is a rook polynomial for a rectangular board.
60/102 Null Boundary Cellular Automata based expander graphs
Authors: Cho Sung-Jin , Choi Un-Sook , Kim Han-Doo , Hwang Yoon-Hee , Kim Jin-Gyoung
Published: August 2021

Expander graphs are useful in the design and analysis of communication networks. Mukhopadhyay et al. introduced a method to generate a family of expander graphs based on nongroup two predecessor single attractor Cellular Automata(CA). In this paper we propose a method to generate a family of expander graphs based on 60/102 Null Boundary CA(NBCA) which is a group CA. The spectral gap generated by our method is maximal. Moreover, the spectral gap is larger than that of Mukhopadhyay et al.
Square root singularities of infinite systems of functional equations
Authors: Morgenbesser Johannes F.
Published: August 2021

Infinite systems of equations appear naturally in combinatorial counting problems. Formally, we consider functional equations of the form $\mathbf{y} (x)=F(x,\mathbf{y} (x))$, where $F(x,\mathbf{y} ):\mathbb{C} \times \ell^p \to \ell^p$ is a positive and nonlinear function, and analyze the behavior of the solution $\mathbf{y} (x)$ at the boundary of the domain of convergence. In contrast to the finite dimensional case different types of singularities are possible. We show that if the Jacobian operator of the function $F$ is compact, then the occurring singularities are of square root type, as it is in the finite dimensional setting. This leads to asymptotic expansions of the Taylor coefficients of $\mathbf{y} (x)$.
Random sampling of lattice paths with constraints, via transportation
Authors: Gerin Lucas
Published: August 2021

We build and analyze in this paper Markov chains for the random sampling of some one-dimensional lattice paths with constraints, for various constraints. These chains are easy to implement, and sample an "almost" uniform path of length $n$ in $n^{3+\epsilon}$ steps. This bound makes use of a certain $\textit{contraction property}$ of the Markov chain, and is proved with an approach inspired by optimal transport.
On the diameter of random planar graphs
Authors: Chapuy Guillaume , Fusy Eric , Gimenez Omer , Noy Marc
Published: August 2021

We show that the diameter $D(G_n)$ of a random (unembedded) labelled connected planar graph with $n$ vertices is asymptotically almost surely of order $n^{1/4}$, in the sense that there exists a constant $c>0$ such that $P(D(G_n) \in (n^{1/4-\epsilon} ,n^{1/4+\epsilon})) \geq 1-\exp (-n^{c\epsilon})$ for $\epsilon$ small enough and $n$ large enough $(n \geq n_0(\epsilon))$. We prove similar statements for rooted $2$-connected and $3$-connected embedded (maps) and unembedded planar graphs.
Finding hidden cliques in linear time
Authors: Feige Uriel , Ron Dorit
Published: August 2021

In the hidden clique problem, one needs to find the maximum clique in an $n$-vertex graph that has a clique of size $k$ but is otherwise random. An algorithm of Alon, Krivelevich and Sudakov that is based on spectral techniques is known to solve this problem (with high probability over the random choice of input graph) when $k \geq c \sqrt{n}$ for a sufficiently large constant $c$. In this manuscript we present a new algorithm for finding hidden cliques. It too provably works when $k > c \sqrt{n}$ for a sufficiently large constant $c$. However, our algorithm has the advantage of being much simpler (no use of spectral techniques), running faster (linear time), and experiments show that the leading constant $c$ is smaller than in the spectral approach. We also present linear time algorithms that experimentally find even smaller hidden cliques, though it remains open whether any of these algorithms finds hidden cliques of size $o(\sqrt{n})$.
Enumeration of inscribed polyominos
Authors: Goupil Alain , Cloutier Hugo , Nouboud Fathallah
Published: August 2021

We introduce a new family of polyominos that are inscribed in a rectangle of given size for which we establish a number of exact formulas and generating functions. In particular, we study polyominos inscribed in a rectangle with minimum area and minimum area plus one. These results are then used for the enumeration of lattice trees inscribed in a rectangle with minimum area plus one.

Nous introduisons une nouvelle famille de polyominos inscrits dans un rectangle de format donné pour lesquels des formules exactes et des séries génératrices sont présentées. Nous étudions en particulier les polyominos inscrits d'aire minimale et ceux d'aire minimale plus un. Ces résultats sont ensuite utilisés pour l'énumération de polyominos arbres inscrits dans un rectangle d'aire minimum plus un.
Counting unicellular maps on non-orientable surfaces
Authors: Bernardi Olivier , Chapuy Guillaume
Published: August 2021

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is a topological disk. In this paper we give a bijective operation that relates unicellular maps on a non-orientable surface to unicellular maps of a lower topological type, with distinguished vertices. From that we obtain a recurrence equation that leads to (new) explicit counting formulas for non-orientable precubic (all vertices of degree 1 or 3) unicellular maps of fixed topology. We also determine asymptotic formulas for the number of all unicellular maps of fixed topology, when the number of edges goes to infinity. Our strategy is inspired by recent results obtained for the orientable case [Chapuy, PTRF 2010], but significant novelties are introduced: in particular we construct an involution which, in some sense, ``averages'' the effects of non-orientability. \par

Une carte unicellulaire est le plongement d'un graphe connexe dans une surface, tel que le complémentaire du graphe est un disque topologique. On décrit une opération bijective qui relie les cartes unicellulaires sur une surface non-orientable aux cartes unicellulaires de type topologique inférieur, avec des sommets marqués. On en déduit une récurrence qui conduit à de (nouvelles) formules closes d'énumération pour les cartes unicellulaires précubiques (sommets de degré 1 ou 3) de topologie fixée. On obtient aussi des formules asymptotiques pour le nombre total de cartes unicellulaires de topologie fixée, quand le nombre d'arêtes tend vers l'infini. Notre stratégie est motivée par de récents résultats dans le cas orientable [Chapuy, PTRF, 2010], mais d'importantes nouveautés sont introduites: en particulier, on construit une involution qui, en un certain sens, "moyenne'' les effets de la non-orientabilité.
The spectrum of an asymmetric annihilation process
Authors: Ayyer Arvind , Strehl Volker
Published: August 2021

In recent work on nonequilibrium statistical physics, a certain Markovian exclusion model called an asymmetric annihilation process was studied by Ayyer and Mallick. In it they gave a precise conjecture for the eigenvalues (along with the multiplicities) of the transition matrix. They further conjectured that to each eigenvalue, there corresponds only one eigenvector. We prove the first of these conjectures by generalizing the original Markov matrix by introducing extra parameters, explicitly calculating its eigenvalues, and showing that the new matrix reduces to the original one by a suitable specialization. In addition, we outline a derivation of the partition function in the generalized model, which also reduces to the one obtained by Ayyer and Mallick in the original model.

Dans un travail récent sur la physique statistique hors équilibre, un certain modèle d'exclusion Markovien appelé "processus d'annihilation asymétrique'' a été étudié par Ayyer et Mallick. Dans ce document, ils ont donné une conjecture précise pour les valeurs propres (avec les multiplicités) de la matrice stochastique. Ils ont en outre supposé que, pour chaque valeur propre, correspond un seul vecteur propre. Nous prouvons la première de ces conjectures en généralisant la matrice originale de Markov par l'introduction de paramètres supplémentaires, calculant explicitement ses valeurs propres, et en montrant que la nouvelle matrice se réduit à l'originale par une spécialisation appropriée. En outre, nous présentons un calcul de la fonction de partition dans le modèle généralisé, ce qui réduit également à celle obtenue par Ayyer et Mallick dans le modèle original.
Meander Graphs
Authors: Heitsch Christine E. , Tetali Prasad
Published: August 2021

We consider a Markov chain Monte Carlo approach to the uniform sampling of meanders. Combinatorially, a meander $M = [A:B]$ is formed by two noncrossing perfect matchings, above $A$ and below $B$ the same endpoints, which form a single closed loop. We prove that meanders are connected under appropriate pairs of balanced local moves, one operating on $A$ and the other on $B$. We also prove that the subset of meanders with a fixed $B$ is connected under a suitable local move operating on an appropriately defined meandric triple in $A$. We provide diameter bounds under such moves, tight up to a (worst case) factor of two. The mixing times of the Markov chains remain open.

Nous considérons une approche de Monte Carlo par chaîne de Markov pour l'échantillonnage uniforme des méandres. Combinatoirement, un méandre $M = [A : B]$ est constitué par deux couplages (matchings) parfaits sans intersection $A$ et $B$, définis sur le même ensemble de points alignés, et qui forment une boucle fermée simple lorsqu'on dessine $A$ "vers le haut'' et $B$ "vers le bas''. Nous montrons que les méandres sont connectés sous l'action de paires appropriées de mouvements locaux équilibrés, l'un opérant sur $A$ et l'autre sur $B$. Nous montrons également que le sous-ensemble de méandres avec un $B$ fixe est connecté sous l'action de mouvements locaux définis sur des "triplets méandriques'' de $A$. Nous fournissons des bornes sur les diamètres pour de tels mouvements, exactes à un facteur 2 près (dans le pire des cas). Les temps de mélange des chaînes de Markov demeurent une question ouverte.
Bumping algorithm for set-valued shifted tableaux
Authors: Ikeda Takeshi , Naruse Hiroshi , Numata Yasuhide
Published: August 2021

We present an insertion algorithm of Robinson–Schensted type that applies to set-valued shifted Young tableaux. Our algorithm is a generalization of both set-valued non-shifted tableaux by Buch and non set-valued shifted tableaux by Worley and Sagan. As an application, we obtain a Pieri rule for a K-theoretic analogue of the Schur Q-functions.

Nous présentons un algorithme d'insertion de Robinson–Schensted qui s'applique aux tableaux décalés à valeurs sur des ensembles. Notre algorithme est une généralisation de l'algorithme de Buch pour les tableaux à valeurs sur des ensembles et de l'algorithme de Worley et Sagan pour les tableaux décalés. Comme application, nous obtenons une formule de Pieri pour un analogue en K-théorie des Q-functions de Schur.
Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and Tropical Oriented Matroids
Authors: Oh Suho , Yoo Hwanchul
Published: August 2021

Develin and Sturmfels showed that regular triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ can be thought of as tropical polytopes. Tropical oriented matroids were defined by Ardila and Develin, and were conjectured to be in bijection with all subdivisions of $\Delta_{n-1} \times \Delta_{d-1}$. In this paper, we show that any triangulation of $\Delta_{n-1} \times \Delta_{d-1}$ encodes a tropical oriented matroid. We also suggest a new class of combinatorial objects that may describe all subdivisions of a bigger class of polytopes.

Develin et Sturmfels ont montré que les triangulations de $\Delta_{n-1} \times \Delta_{d-1}$ peuvent être considérées comme des polytopes tropicaux. Les matroïdes orientés tropicaux ont été définis par Ardila et Develin, et ils ont été conjecturés être en bijection avec les subdivisions de $\Delta_{n-1} \times \Delta_{d-1}$. Dans cet article, nous montrons que toute triangulation de $\Delta_{n-1} \times \Delta_{d-1}$ encode un matroïde orienté tropical. De plus, nous proposons une nouvelle classe d'objets combinatoires qui peuvent décrire toutes les subdivisions d'une plus grande classe de polytopes.
A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks
Authors: Richard Adrien
Published: August 2021

We are interested in fixed points in Boolean networks, $\textit{i.e.}$ functions $f$ from $\{0,1\}^n$ to itself. We define the subnetworks of $f$ as the restrictions of $f$ to the hypercubes contained in $\{0,1\}^n$, and we exhibit a class $\mathcal{F}$ of Boolean networks, called even or odd self-dual networks, satisfying the following property: if a network $f$ has no subnetwork in $\mathcal{F}$, then it has a unique fixed point. We then discuss this "forbidden subnetworks theorem''. We show that it generalizes the following fixed point theorem of Shih and Dong: if, for every $x$ in $\{0,1\}^n$, there is no directed cycle in the directed graph whose the adjacency matrix is the discrete Jacobian matrix of $f$ evaluated at point $x$, then $f$ has a unique fixed point. We also show that $\mathcal{F}$ contains the class $\mathcal{F'}$ of networks whose the interaction graph is a directed cycle, but that the absence of subnetwork in $\mathcal{F'}$ does not imply the existence and the uniqueness of a fixed point.
Approximate Counting via the Poisson-Laplace-Mellin Method
Authors: Fuchs Michael , Lee Chung-Kuei , Prodinger Helmut
Published: August 2021

Approximate counting is an algorithm that provides a count of a huge number of objects within an error tolerance. The first detailed analysis of this algorithm was given by Flajolet. In this paper, we propose a new analysis via the Poisson-Laplace-Mellin approach, a method devised for analyzing shape parameters of digital search trees in a recent paper of Hwang et al. Our approach yields a different and more compact expression for the periodic function from the asymptotic expansion of the variance. We show directly that our expression coincides with the one obtained by Flajolet. Moreover, we apply our method to variations of approximate counting, too.
On the number of transversals in random trees
Authors: Gittenberger Bernhard , Kraus Veronika
Published: August 2021

We study transversals in random trees with n vertices asymptotically as n tends to infinity. Our investigation treats the average number of transversals of fixed size, the size of a random transversal as well as the probability that a random subset of the vertex set of a tree is a transversal for the class of simply generated trees and for Pólya trees. The last parameter was already studied by Devroye for simply generated trees. We offer an alternative proof based on generating functions and singularity analysis and extend the result to Pólya trees.
A Unified Framework to Compute over Tree Synchronized Grammars and Primal Grammars
Authors: Saubion Frédéric , Stéphan Igor
Published: August 2021

Tree languages are powerful tools for the representation and schematization of infinite sets of terms for various purposes (unification theory, verification and specification ...). In order to extend the regular tree language framework, more complex formalisms have been developed. In this paper, we focus on Tree Synchronized Grammars and Primal Grammars which introduce specific control structures to represent non regular sets of terms. We propose a common unified framework in order to achieve the membership test for these particular languages. Thanks to a proof system, we provide a full operational framework, that allows us to transform tree grammars into Prolog programs (as it already exists for word grammars with DCG) whose goal is to recognize terms of the corresponding language.
Mean field analysis for inhomogeneous bike sharing systems
Authors: Fricker Christine , Gast Nicolas , Mohamed Hanene
Published: August 2021

In the paper, bike sharing systems with stations having a finite capacity are studied as stochastic networks. The inhomogeneity is modeled by clusters. We use a mean field limit to compute the limiting stationary distribution of the number of bikes at the stations. This method is an alternative to analytical methods. It can be used even if a closed form expression for the stationary distribution is out of reach as illustrated on a variant. Both models are compared. A practical conclusion is that avoiding empty or full stations does not improve overall performance.
On the Number of 2-Protected Nodes in Tries and Suffix Trees
Authors: Gaither Jeffrey , Homma Yushi , Sellke Mark , Ward Mark Daniel
Published: August 2021

We use probabilistic and combinatorial tools on strings to discover the average number of 2-protected nodes in tries and in suffix trees. Our analysis covers both the uniform and non-uniform cases. For instance, in a uniform trie with $n$ leaves, the number of 2-protected nodes is approximately 0.803$n$, plus small first-order fluctuations. The 2-protected nodes are an emerging way to distinguish the interior of a tree from the fringe.
Explicit generating series for connection coefficients
Authors: Vassilieva Ekaterina A.
Published: August 2021

This paper is devoted to the explicit computation of generating series for the connection coefficients of two commutative subalgebras of the group algebra of the symmetric group, the class algebra and the double coset algebra. As shown by Hanlon, Stanley and Stembridge (1992), these series gives the spectral distribution of some random matrices that are of interest to statisticians. Morales and Vassilieva (2009, 2011) found explicit formulas for these generating series in terms of monomial symmetric functions by introducing a bijection between partitioned hypermaps on (locally) orientable surfaces and some decorated forests and trees. Thanks to purely algebraic means, we recover the formula for the class algebra and provide a new simpler formula for the double coset algebra. As a salient ingredient, we compute an explicit formulation for zonal polynomials indexed by partitions of type $[a,b,1^{n-a-b}]$.

Cet article est dédié au calcul explicite des séries génératrices des constantes de structure de deux sous-algèbres commutatives de l'algèbre de groupe du groupe symétrique, l'algèbre de classes et l'algèbre de double classe latérale. Tel que montrè par Hanlon, Stanley and Stembridge (1992), ces séries déterminent la distribution spectrale de certaines matrices aléatoires importantes en statistique. Morales et Vassilieva (2009, 2011) ont trouvè des formules explicites pour ces séries génératrices en termes des monômes symétriques en introduisant une bijection entre les hypercartes partitionnées sur des surfaces (localement) orientables et certains arbres et forêts décorées. Grâce à des moyens purement algébriques, nous retrouvons la formule pour l'algèbre de classe et déterminons une nouvelle formule plus simple pour l'algèbre de double classe latérale. En tant que point saillant de notre démonstration nous calculons une formulation explicite pour les polynômes zonaux indexés par des partitions de type $[a,b,1^{n-a-b}]$.
A simple model of trees for unicellular maps
Authors: Chapuy Guillaume , Feray Valentin , Fusy Eric
Published: August 2021

We consider unicellular maps, or polygon gluings, of fixed genus. In FPSAC '09 the first author gave a recursive bijection transforming unicellular maps into trees, explaining the presence of Catalan numbers in counting formulas for these objects. In this paper, we give another bijection that explicitly describes the ``recursive part'' of the first bijection. As a result we obtain a very simple description of unicellular maps as pairs made by a plane tree and a permutation-like structure. All the previously known formulas follow as an immediate corollary or easy exercise, thus giving a bijective proof for each of them, in a unified way. For some of these formulas, this is the first bijective proof, e.g. the Harer-Zagier recurrence formula, or the Lehman-Walsh/Goupil-Schaeffer formulas. Thanks to previous work of the second author this also leads us to a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group.

Nous considèrons des cartes orientèes à une face de genre fixé. à SFCA'09 le premier auteur a introduit une bijection rècursive envoyant une carte unicellulaire vers un arbre, ce qui permet d'obtenir des formules ènumèratives pour les cartes à une face (et en particulier la prèsence des nombres de Catalan). Dans l'article ici prèsent, et en nous appuyant sur la bijection ci-dessus, nous obtenons une incarnation très simple des cartes à une face comme des paires formèes d'un arbre plan et d'une permutation d'un certain type. Toutes les formules prècèdemment connues dècoulent aisèment de cette nouvelle incarnation, donnant des preuves bijectives dans un cadre unifié. Pour certaines de ces formules, telles que la rècurrence de Harer-Zagier ou les formules de Lehman-Walsh/Goupil-Schaeffer, nous obtenons la première preuve bijective connue. Par ailleurs, en combinant notre approche avec des travaux du second auteur, nous obtenons une nouvelle expression pour les polynômes de Stanley qui donnent certaines èvaluations des caractères du groupe symètrique.
On an algebraicity theorem of Kontsevich
Authors: Reutenauer Christophe , Robado Marco
Published: August 2021

We give in a particular case a combinatorial proof of a recent algebraicity result of Kontsevich; the proof uses generalized one-sided and two-sided Dyck words, or equivalently, excursions and bridges. We indicate a noncommutative version of these notions, which could lead to a full proof. We show also a relation with pointed planar maps.

Nous donnons, dans un cas particulier, une preuve combinatoire d'un rèsultat rècent d'algèbricitè de Kontsevich; la preuve utilise des mots de Dyck gènèralisès d'un cotè et deux cotès ou de façon èquivalente, excursions et ponts. Nous indiquons une version non-commutative de ces notions, qui pourrait conduire à une preuve complète. Nous montrons aussi une relation avec des cartes planaires pointèes.
The height of q-Binary Search Trees
Authors: Drmota Michael , Prodinger Helmut
Published: August 2021

q-binary search trees are obtained from words, equipped with a geometric distribution instead of permutations. The average and variance of the heighth computated, based on random words of length n, as well as a Gaussian limit law.
Bases for modules of differential operators
Authors: Nakashima Norihiro
Published: August 2021

It is well-known that the derivation modules of Coxeter arrangements are free. Holm began to study the freeness of modules of differential operators on hyperplane arrangements. In this paper, we study the cases of the Coxter arrangements of type A, B and D. In this case, we prove that the modules of differential operators of order 2 are free. We give examples of all the 3-dimensional classical Coxeter arrangements. Two keys for the proof are ``Cauchy–Sylvester's theorem on compound determinants'' and ``Saito–Holm's criterion''.

Il est connu que les modules de la dérivation d'arrangements de Coxeter sont libres. Holm a commencè à étudier les modules libres des opérateurs différentiels sur des compositions d'hyperplans. Dans cet article, nous étudions les cas des compositions de Coxter les types A, B et D. Dans ce cas, nous prouvons que les modules d’opérateurs différentiels d'ordre 2 sont libres. Nous donnons des exemples de toutes les compositions de Coxeter classiques de dimension 3. Les deux points clefs pour la preuve sont le théorème de Cauchy–Sylvester sur déterminants composés et le critère de Saito–Holm.
Generating trees for partitions and permutations with no k-nestings
Authors: Burrill Sophie , Elizalde Sergi , Mishna Marni , Yen Lily
Published: August 2021

We describe a generating tree approach to the enumeration and exhaustive generation of k-nonnesting set partitions and permutations. Unlike previous work in the literature using the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with k as a parameter.

Nous décrivons une approche, basée sur l'utilisation d'arbres de génération, pour énumération et la génération exhaustive de partitions et permutations sans k-emboîtement. Contrairement aux travaux antérieurs qui reposent sur un lien entre ces objets, tableaux de Young et familles de chemins dans des treillis, notre approche traite directement partitions et diagrammes de permutations. Nous fournissons des équations fonctionnelles explicites pour les séries génératrices, avec k en tant que paramètre.
Permutation Polytopes of Cyclic Groups
Authors: Baumeister Barbara , Haase Christian , Nill Benjamin , Paffenholz Andreas
Published: August 2021

We investigate the combinatorics and geometry of permutation polytopes associated to cyclic permutation groups, i.e., the convex hulls of cyclic groups of permutation matrices. In the situation that the generator of the group consists of at most two orbits, we can give a complete combinatorial description of the associated permutation polytope. In the case of three orbits the facet structure is already quite complex. For a large class of examples we show that there exist exponentially many facets.

Nous ètudions les propriètès combinatoires et gèomètriques des polytopes de permutations pour des groupes cycliques. C'est à dire, donnè un groupe cyclique de matrices de permutations, nous considèrons son enveloppe convexe. Si le gènèrateur du groupe possède un ou deux orbites il y a une dèscription simple du polytope. Par contre, le cas de trois (ou plus) orbites est beaucoup plus compliquè. Pour une classe ample d'examples nous construisons un nombre exponentiel de faces de co-dimension un.
Standard fillings to parking functions
Authors: Niese Elizabeth
Published: August 2021

The Hilbert series of the Garsia-Haiman module can be written as a generating function of standard fillings of Ferrers diagrams. It is conjectured by Haglund and Loehr that the Hilbert series of the diagonal harmonics can be written as a generating function of parking functions. In this paper we present a weight-preserving injection from standard fillings to parking functions for certain cases.

La série Hilbert du module Garsia-Haiman peut être écrite comme fonction génératrice de tableaux des diagrammes Ferrers. Haglund et Loehr conjecturent que la série Hilbert de l'harmonic diagonale peut être écrite comme fonction génératrice des fonctions parking. Dans cet essai nous présentons une injection des tableaux vers les fonctions parking pour certains cas.