Sign variation, the Grassmannian, and total positivity

Karp, Steven N..
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 […]

Dyck path triangulations and extendability (extended abstract)

Ceballos, Cesar ; Padrol, Arnau ; Sarmiento, Camilo.
We introduce the Dyck path triangulation of the cartesian product of two simplices $\Delta_{n-1}\times\Delta_{n-1}$. The maximal simplices of this triangulation are given by Dyck paths, and its construction naturally generalizes to produce triangulations of $\Delta_{r\ n-1}\times\Delta_{n-1}$ using […]

Dual filtered graphs

Patrias, Rebecca ; Pylyavskyy, Pavlo.
We define a $K$ -theoretic analogue of Fomin’s dual graded graphs, which we call dual filtered graphs. The key formula in the definition is $DU - UD = D + I$. Our major examples are $K$ -theoretic analogues of Young’s lattice, the binary tree, and the graph determined by the Poirier-Reutenauer […]

Formal Group Laws and Chromatic Symmetric Functions of Hypergraphs

Taylor, Jair.
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 […]

Pieri rules for Schur functions in superspace

Jones, Miles Eli ; Lapointe, Luc.
The Schur functions in superspace $s_\Lambda$ and $øverline{s}_\Lambda$ are the limits $q=t= 0$ and $q=t=\infty$ respectively of the Macdonald polynomials in superspace. We present the elementary properties of the bases $s_\Lambda$ and $øverline{s}_\Lambda$ (which happen to be essentially dual) […]

A Nekrasov-Okounkov type formula for affine $\widetilde{C}$

Pétréolle, Mathias.
In 2008, Han rediscovered an expansion of powers of Dedekind $\eta$ function due to Nekrasov and Okounkov by using Macdonald's identity in type $\widetilde{A}$. In this paper, we obtain new combinatorial expansions of powers of $\eta$, in terms of partition hook lengths, by using Macdonald's […]

Type C parking functions and a zeta map

Sulzgruber, Robin ; Thiel, Marko.
We introduce type $C$ parking functions, encoded as vertically labelled lattice paths and endowed with a statistic dinv'. We define a bijection from type $C$ parking functions to regions of the Shi arrangement of type $C$, encoded as diagonally labelled ballot paths and endowed with a natural […]

Bijections of dominant regions in the $m$-Shi arrangements of type $A$, $B$ and $C$

Kallipoliti, Myrto ; Tzanaki, Eleni.
In the present paper, the relation between the dominant regions in the $m$-Shi arrangement of types $B_n/C_n$, and those of the $m$-Shi arrangement of type $A_{n-1}$ is investigated. More precisely, it is shown explicitly how the sets $R^m(B_n)$ and $R^m(C_n)$, of dominant regions of the $m$-Shi […]

Rigged configurations of type $D_4^{(3)}$ and the filling map

Scrimshaw, Travis.
We give a statistic preserving bijection from rigged configurations to a tensor product of Kirillov–Reshetikhin crystals $øtimes_{i=1}^{N}B^{1,s_i}$ in type $D_4^{(3)}$ by using virtualization into type $D_4^{(1)}$. We consider a special case of this bijection with $B=B^{1,s}$, and we obtain the […]

Stability properties of Plethysm: new approach with combinatorial proofs (Extended abstract)

Colmenarejo, Laura.
Plethysm coefficients are important structural constants in the theory of symmetric functions and in the representations theory of symmetric groups and general linear groups. In 1950, Foulkes observed stability properties: some sequences of plethysm coefficients are eventually constants. Such […]

The Real-rootedness of Eulerian Polynomials via the Hermite–Biehler Theorem

Yang, Arthur L.B. ; Zhang, Philip B..
Based on the Hermite–Biehler theorem, we simultaneously prove the real-rootedness of Eulerian polynomials of type $D$ and the real-rootedness of affine Eulerian polynomials of type $B$, which were first obtained by Savage and Visontai by using the theory of $s$-Eulerian polynomials. We also confirm […]

Pieri rule for the affine flag variety

Lee, Seung Jin.
We prove the affine Pieri rule for the cohomology of the affine flag variety conjectured by Lam, Lapointe, Morse and Shimozono. We study the cap operator on the affine nilHecke ring that is motivated by Kostant and Kumar’s work on the equivariant cohomology of the affine flag variety. We show […]

A representation-theoretic proof of the branching rule for Macdonald polynomials

Sun, Yi.
We give a new representation-theoretic proof of the branching rule for Macdonald polynomials using the Etingof-Kirillov Jr. expression for Macdonald polynomials as traces of intertwiners of $U_q(gl_n)$. In the Gelfand-Tsetlin basis, we show that diagonal matrix elements of such intertwiners are […]

Universal geometric coefficients for the four-punctured sphere (Extended Abstract)

Barnard, Emily ; Meehan, Emily ; Polster, Shira ; Reading, Nathan.
We construct universal geometric coefficients for the cluster algebra associated to the four-punctured sphere and obtain, as a by-product, the $g$ -vectors of cluster variables. We also construct the rational part of the mutation fan. These constructions rely on a classification of the allowable […]

$Y$ -meshes and generalized pentagram maps

Glick, Max ; Pylyavskyy, Pavlo.
We introduce a rich family of generalizations of the pentagram map sharing the property that each generates an infinite configuration of points and lines with four points on each line. These systems all have a description as $Y$ -mutations in a cluster algebra and hence establish new connections […]

A categorification of the chromatic symmetric polynomial

Sazdanović, Radmila ; Yip, Martha.
The Stanley chromatic polynomial of a graph $G$ is a symmetric function generalization of the chromatic polynomial, and has interesting combinatorial properties. We apply the ideas of Khovanov homology to construct a homology $H$*($G$) of graded $S_n$-modules, whose graded Frobenius […]

A lattice on decreasing trees : the metasylvester lattice

Pons, Viviane.
We introduce a new combinatorial structure: the metasylvester lattice on decreasing trees. It appears in the context of the $m$-Tamari lattices and other related $m$-generalizations. The metasylvester congruence has been recently introduced by Novelli and Thibon. We show that it defines a sublattice […]

Coxeter-biCatalan combinatorics

Barnard, Emily ; Reading, Nathan.
We consider several counting problems related to Coxeter-Catalan combinatorics and conjecture that the problems all have the same answer, which we call the $W$ -biCatalan number. We prove the conjecture in many cases.

Equivariant Giambelli formula for the symplectic Grassmannians — Pfaffian Sum Formula

Ikeda, Takeshi ; Matsumura, Tomoo.
We prove an explicit closed formula, written as a sum of Pfaffians, which describes each equivariant Schubert class for the Grassmannian of isotropic subspaces in a symplectic vector space

Atomic Bases and $T$-path Formula for Cluster Algebras of Type $D$

Gunawan, Emily ; Musiker, Gregg.
We extend a $T$-path expansion formula for arcs on an unpunctured surface to the case of arcs on a once-punctured polygon and use this formula to give a combinatorial proof that cluster monomials form the atomic basis of a cluster algebra of type $D$.

Stability of Kronecker coefficients via discrete tomography (Extended abstract)

Vallejo, Ernesto.
In this paper we give a sufficient condition for a general stability of Kronecker coefficients, which we call additive stability. Its main ingredient is the property of a matrix of being additive. This notion seems to be an important one: it appears in Discrete Tomography as a sufficient condition […]

Cyclic Sieving and Plethysm Coefficients

Rush, David B.
A combinatorial expression for the coefficient of the Schur function $s_{\lambda}$ in the expansion of the plethysm $p_{n/d}^d \circ s_{\mu}$ is given for all $d$ dividing $n$ for the cases in which $n=2$ or $\lambda$ is rectangular. In these cases, the coefficient $\langle p_{n/d}^d \circ s_{\mu}, […]

Combinatorics of symplectic invariant tensors

Rubey, Martin ; Westbury, Bruce W..
An important problem from invariant theory is to describe the subspace of a tensor power of a representation invariant under the action of the group. According to Weyl's classic, the first main (later: 'fundamental') theorem of invariant theory states that all invariants are expressible in terms of […]

Combinatorial proofs of freeness of some P-algebras

Vong, Vincent.
We present new combinatorial methods for solving algebraic problems such as computing the Hilbert series of a free $P$-algebra over one generator, or proving the freeness of a $P$-algebra. In particular, we apply these methods to the cases of dendriform algebras, quadrialgebras and tridendriform […]

A uniform realization of the combinatorial $R$-matrix

Lenart, Cristian ; Lubovsky, Arthur.
Kirillov-Reshetikhin (KR) crystals are colored directed graphs encoding the structure of certain finite-dimensional representations of affine Lie algebras. A tensor product of column shape KR crystals has recently been realized in a uniform way, for all untwisted affine types, in terms […]

The $(m, n)$-rational $q, t$-Catalan polynomials for $m=3$ and their $q, t$-symmetry

Kaliszewski, Ryan ; Li, Huilan.
We introduce a new statistic, skip, on rational $(3,n)$-Dyck paths and define a marked rank word for each path when $n$ is not a multiple of 3. If a triple of valid statistics (area; skip; dinv) are given, we have an algorithm to construct the marked rank word corresponding to the triple. By […]

Four Variations on Graded Posets

Zhang, Yan X.
We explore the enumeration of some natural classes of graded posets, including $(2 + 2)$-avoiding graded posets, $(3 + 1)$-avoiding graded posets, $(2 + 2)$- and $(3 + 1)$-avoiding graded posets, and the set of all graded posets. As part of this story, we discuss a situation when we can switch […]

Statistics on Lattice Walks and q-Lassalle Numbers

Tevlin, Lenny.
This paper contains two results. First, I propose a $q$-generalization of a certain sequence of positive integers, related to Catalan numbers, introduced by Zeilberger, see Lassalle (2010). These $q$-integers are palindromic polynomials in $q$ with positive integer coefficients. The positivity […]

The freeness of Ish arrangements

Abe, Takuro ; Suyama, Daisuke ; Tsujie, Shuhei.
The Ish arrangement was introduced by Armstrong to give a new interpretation of the $q; t$-Catalan numbers of Garsia and Haiman. Armstrong and Rhoades showed that there are some striking similarities between the Shi arrangement and the Ish arrangement and posed some problems. One of them is whether […]

Walks in the Quarter Plane with Multiple Steps

Kauers, Manuel ; Yatchak, Rika.
We extend the classification of nearest neighbour walks in the quarter plane to models in which multiplicities are attached to each direction in the step set. Our study leads to a small number of infinite families that completely characterize all the models whose associated group is D4, D6, or D8. […]

The number of directed $k$-convex polyominoes

Boussicault, Adrien ; Rinaldi, Simone ; Socci, Samanta.
We present a new method to obtain the generating functions for directed convex polyominoes according to several different statistics including: width, height, size of last column/row and number of corners. This method can be used to study different families of directed convex polyominoes: symmetric […]

Cohomology classes of rank varieties and a counterexample to a conjecture of Liu

Pawlowski, Brendan.
To each finite subset of a discrete grid $\mathbb{N}×\mathbb{N}$ (a diagram), one can associate a subvariety of a complex Grassmannian (a diagram variety), and a representation of a symmetric group (a Specht module). Liu has conjectured that the cohomology class of a diagram variety is represented […]

Some combinatorial identities involving noncommuting variables

Schlosser, Michael ; Yoo, Meesue.
We derive combinatorial identities for variables satisfying specific sets of commutation relations. The identities thus obtained extend corresponding ones for $q$-commuting variables $x$ and $y$ satisfying $yx=qxy$. In particular, we obtain weight-dependent binomial theorems, functional equations […]

Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras

Pang, C. Y. Amy.
Recently, Diaconis, Ram and I created Markov chains out of the coproduct-then-product operator on combinatorial Hopf algebras. These chains model the breaking and recombining of combinatorial objects. Our motivating example was the riffle-shuffling of a deck of cards, for which this Hopf algebra […]

Bridge Graphs and Deodhar Parametrizations for Positroid Varieties

Karpman, Rachel.
A parametrization of a positroid variety $\Pi$ of dimension $d$ is a regular map $(\mathbb{C}^{\times})^{d} \rightarrow \Pi$ which is birational onto a dense subset of $\Pi$. There are several remarkable combinatorial constructions which yield parametrizations of positroid varieties. We […]

Generalized Tesler matrices, virtual Hilbert series, and Macdonald polynomial operators

Wilson, Andrew Timothy.
We generalize previous definitions of Tesler matrices to allow negative matrix entries and non-positive hook sums. Our main result is an algebraic interpretation of a certain weighted sum over these matrices. Our interpretation uses virtual Hilbert series, a new class of symmetric function […]

Affine charge and the $k$-bounded Pieri rule

Morse, Jennifer ; Schilling, Anne.
We provide a new description of the Pieri rule of the homology of the affine Grassmannian and an affineanalogue of the charge statistics in terms of bounded partitions. This makes it possible to extend the formulation ofthe Kostka–Foulkes polynomials in terms of solvable lattice models by […]

Subwords and Plane Partitions

Hamaker, Zachary ; Williams, Nathan.
Using the powerful machinery available for reduced words of type $B$, we demonstrate a bijection between centrally symmetric $k$-triangulations of a $2(n + k)$-gon and plane partitions of height at most $k$ in a square of size $n$. This bijection can be viewed as the type $B$ analogue of a bijection […]

Genomic Tableaux and Combinatorial $K$-Theory

Pechenik, Oliver ; Yong, Alexander.
We introduce genomic tableaux, with applications to Schubert calculus. We report a combinatorial rule for structure coefficients in the torus-equivariant $K$-theory of Grassmannians for the basis of Schubert structure sheaves. This rule is positive in the sense of [Anderson-Griffeth-Miller ’11]. We […]

Alignments, crossings, cycles, inversions, and weak Bruhat order in permutation tableaux of type $B$

Cho, Soojin ; Park, Kyoungsuk.
Alignments, crossings and inversions of signed permutations are realized in the corresponding permutation tableaux of type $B$, and the cycles of signed permutations are understood in the corresponding bare tableaux of type $B$. We find the relation between the number of alignments, crossings and […]

A combinatorial model for exceptional sequences in type A

Garver, Alexander ; Matherne, Jacob P..
Exceptional sequences are certain ordered sequences of quiver representations. We use noncrossing edge-labeled trees in a disk with boundary vertices (expanding on T. Araya’s work) to classify exceptional sequences of representations of $Q$, the linearly ordered quiver with $n$ vertices. We also […]

Fan realizations of type $A$ subword complexes and multi-associahedra of rank 3

Bergeron, Nantel ; Ceballos, Cesar ; Labbé, Jean-Philippe.
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. […]

Invariance properties for coefficients of symmetric functions

Briand, Emmanuel ; Orellana, Rosa ; Rosas, Mercedes.
We show that several of the main structural constants for symmetric functions (Littlewood-Richardsoncoefficients, Kronecker coefficients, plethysm coefficients, and the Kostka–Foulkes polynomials) share invarianceproperties related to the operations of taking complements with respect to rectangles […]

Scaling Limits of Random Graphs from Subcritical Classes: Extended abstract

Panagiotou, Konstantinos ; Stufler, Benedikt ; Weller, Kerstin.
We study the uniform random graph $\mathsf{C}_n$ with $n$ vertices drawn from a subcritical class of connected graphs. Our main result is that the rescaled graph $\mathsf{C}_n / \sqrt{n}$ converges to the Brownian Continuum Random Tree $\mathcal{T}_{\mathsf{e}}$ multiplied by a constant scaling […]

Upper bounds on the growth rates of hard squares and related models via corner transfer matrices

Chan, Yao-Ban.
We study the growth rate of the hard squares lattice gas, equivalent to the number of independent sets on the square lattice, and two related models — non-attacking kings and read-write isolated memory. We use an assortment of techniques from combinatorics, statistical mechanics and linear algebra […]

Triangular fully packed loop configurations of excess 2

Beil, Sabine.
Triangular fully packed loop configurations (TFPLs) came up in the study of fully packed loop configurations on a square (FPLs) corresponding to link patterns with a large number of nested arches. To a TFPL is assigned a triple $(u,v;w)$ of $01$-words encoding its boundary conditions. A necessary […]

Mixed volumes of hypersimplices

Liu, Gaku.
In this extended abstract we consider mixed volumes of combinations of hypersimplices. These numbers, called mixed Eulerian numbers, were first considered by A. Postnikov and were shown to satisfy many properties related to Eulerian numbers, Catalan numbers, binomial coefficients, etc. We give a […]

On non-conjugate Coxeter elements in well-generated reflection groups

Reiner, Victor ; Ripoll, Vivien ; Stump, Christian.
Given an irreducible well-generated complex reflection group $W$ with Coxeter number $h$, we call a Coxeter element any regular element (in the sense of Springer) of order $h$ in $W$; this is a slight extension of the most common notion of Coxeter element. We show that the class of these Coxeter […]

Depth in Coxeter groups of type $B$

Bagno, Eli ; Biagioli, Riccardo ; Novick, Mordechai.
The depth statistic was defined for every Coxeter group in terms of factorizations of its elements into product of reflections. Essentially, the depth gives the minimal path cost in the Bruaht graph, where the edges have prescribed weights. We present an algorithm for calculating the depth of a […]

A Categorification of One-Variable Polynomials

Khovanov, Mikhail ; Sazdanovic, Radmila.
We develop a diagrammatic categorification of the polynomial ring $\mathbb{Z} [x]$, based on a geometrically-defined graded algebra and show how to lift various operations on polynomials to the categorified setting. Our categorification satisfies a version of the Bernstein-Gelfand-Gelfand […]

Arrangements Of Minors In The Positive Grassmannian And a Triangulation of The Hypersimplex

Farber, Miriam ; Mandelshtam, Yelena.
The structure of zero and nonzero minors in the Grassmannian leads to rich combinatorics of matroids. In this paper, we investigate an even richer structure of possible equalities and inequalities between the minors in the positive Grassmannian. It was previously shown that arrangements of equal […]

The Bruhat order on conjugation-invariant sets of involutions in the symmetric group

Hansson, Mikael.
Let $I_n$ be the set of involutions in the symmetric group $S_n$, and for $A \subseteq \{0,1,\ldots,n\}$, let \[ F_n^A=\{\sigma \in I_n \mid \text{$\sigma$ has $a$ fixed points for some $a \in A$}\}. \] We give a complete characterisation of the sets $A$ for which $F_n^A$, with the order induced by […]

Generalized Polarization Modules (extended abstract)

Blandin, Héctor.
This work enrols the research line of M. Haiman on the Operator Theorem (the old operator conjecture). This theorem states that the smallest $\mathfrak{S}_n$-module closed under taking partial derivatives and closed under the action of polarization operators that contains the Vandermonde determinant […]

Enumeration of minimal acyclic automata via generalized parking functions

Priez, Jean-Baptiste.
We give an exact enumerative formula for the minimal acyclic deterministic finite automata. This formula is obtained from a bijection between a family of generalized parking functions and the transitions functions of acyclic automata.

Tableaux combinatorics for two-species PASEP probabilities

Mandelshtam, Olya.
The goal of this paper is to provide a combinatorial expression for the steady state probabilities of the twospecies PASEP. In this model, there are two species of particles, one “heavy” and one “light”, on a one-dimensional finite lattice with open boundaries. Both particles can hop into adjacent […]

Weighted Tree-Numbers of Matroid Complexes

Kook, Woong ; Lee, Kang-Ju.
We give a new formula for the weighted high-dimensional tree-numbers of matroid complexes. This formula is derived from our result that the spectra of the weighted combinatorial Laplacians of matroid complexes consist of polynomials in the weights. In the formula, Crapo’s $\beta$-invariant appears […]

Lattice structure of Grassmann-Tamari orders

McConville, Thomas.
The Tamari order is a central object in algebraic combinatorics and many other areas. Defined as the transitive closure of an associativity law, the Tamari order possesses a surprisingly rich structure: it is a congruence-uniform lattice. In this work, we consider a larger class of posets, the […]

Kraśkiewicz-Pragacz modules and some positivity properties of Schubert polynomials

Watanabe, Masaki.
We use the modules introduced by Kraśkiewicz and Pragacz (1987, 2004) to show some positivity propertiesof Schubert polynomials. We give a new proof to the classical fact that the product of two Schubert polynomialsis Schubert-positive, and also show a new result that the plethystic composition of a […]

On Schubert calculus in elliptic cohomology

Lenart, Cristian ; Zainoulline, Kirill.
An important combinatorial result in equivariant cohomology and $K$-theory Schubert calculus is represented by the formulas of Billey and Graham-Willems for the localization of Schubert classes at torus fixed points. These formulas work uniformly in all Lie types, and are based on the concept of a […]

Lozenge tilings with free boundary

Panova, Greta.
We study tilings with lozenges of a domain with free boundary conditions on one side. These correspondto boxed symmetric plane partitions. We show that the positions of the horizontal lozenges near the left flatboundary, in the limit, have the same joint distribution as the eigenvalues from a […]

Some generalized juggling processes (extended abstract)

Ayyer, Arvind ; Bouttier, Jérémie ; Linusson, Svante ; Nunzi, François.
We consider generalizations of juggling Markov chains introduced by Ayyer, Bouttier, Corteel and Nunzi. We first study multispecies generalizations of all the finite models therein, namely the MJMC, the add-drop and the annihilation models. We then consider the case of several jugglers exchanging […]

A bijection for rooted maps on general surfaces (extended abstract)

Chapuy, Guillaume ; Dołęga, Maciej.
We extend the Marcus-Schaeffer bijection between orientable rooted bipartite quadrangulations (equivalently: rooted maps) and orientable labeled one-face maps to the case of all surfaces, orientable or non-orientable. This general construction requires new ideas and is more delicate than the special […]

Tamari Lattices for Parabolic Quotients of the Symmetric Group

Mühle, Henri ; Williams, Nathan.
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 […]

Semi-pointed partition posets

Delcroix-Oger, Bérénice.
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 […]

A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape

Burrill, Sophie ; Melczer, Stephen ; Mishna, Marni.
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 […]

Diameters and geodesic properties of generalizations of the associahedron

Ceballos, C. ; Manneville, T. ; Pilaud, V. ; Pournin, L..
The $n$-dimensional associahedron is a polytope whose vertices correspond to triangulations of a convex $(n + 3)$-gon and whose edges are flips between them. It was recently shown that the diameter of this polytope is $2n - 4$ as soon as $n > 9$. We study the diameters of the graphs of relevant […]

A generalisation of two partition theorems of Andrews

Dousse, Jehanne.
In 1968 and 1969, Andrews proved two partition theorems of the Rogers-Ramanujan type which generalise Schur’s celebrated partition identity (1926). Andrews’ two generalisations of Schur’s theorem went on to become two of the most influential results in the theory of partitions, finding applications […]

Factoring peak polynomials

Billey, Sara ; Fahrbach, Matthew ; Talmage, Alan.
Given a permutation $\pi=\pi_1\pi_2\cdots \pi_n \in S_n$, we say an index $i$ is a peak if $\pi_{i-1} < \pi_i > \pi_{i+1}$. Let $P(\pi)$ denote the set of peaks of $\pi$. Given any set $S$ of positive integers, define ${P_S(n)=\{\pi\in S_n:P(\pi)=S\}}$. Billey-Burdzy-Sagan showed that for all fixed […]

Maximal increasing sequences in fillings of almost-moon polyominoes

Poznanović, Svetlana ; Yan, Catherine H..
It was proved by Rubey that the number of fillings with zeros and ones of a given moon polyomino thatdo not contain a northeast chain of a fixed size depends only on the set of column lengths of the polyomino. Rubey’sproof uses an adaption of jeu de taquin and promotion for arbitrary fillings of […]

The frequency of pattern occurrence in random walks

Elizalde, Sergi ; Martinez, Megan.
In the past decade, the use of ordinal patterns in the analysis of time series and dynamical systems has become an important tool. Ordinal patterns (otherwise known as a permutation patterns) are found in time series by taking $n$ data points at evenly-spaced time intervals and mapping them to a […]

The polytope of Tesler matrices

Mészáros, Karola ; Morales, Alejandro H. ; Rhoades, Brendon.
We introduce the Tesler polytope $Tes_n(a)$, whose integer points are the Tesler matrices of size n with hook sums $a_1,a_2,...,a_n in Z_{\geq 0}$. We show that $Tes_n(a)$ is a flow polytope and therefore the number of Tesler matrices is counted by the type $A_n$ Kostant partition function evaluated […]

Generalised cluster algebras and $q$-characters at roots of unity

Gleitz, Anne-Sophie.
Shapiro and Chekhov (2011) have introduced the notion of generalised cluster algebra; we focus on an example in type $C_n$. On the other hand, Chari and Pressley (1997), as well as Frenkel and Mukhin (2002), have studied the restricted integral form $U^{\mathtt{res}}_ε […]

Bruhat interval polytopes

Tsukerman, Emmanuel ; Williams, Lauren.
Let $u$ and $v$ be permutations on $n$ letters, with $u$ ≤ $v$ in Bruhat order. A Bruhat interval polytope $Q_{u,v}$ is the convex hull of all permutation vectors $z=(z(1),z(2),...,z(n))$ with $u$ ≤ $z$ ≤ $v$. Note that when $u=e$ and $v=w_0$ are the shortest and longest elements of […]

Enumeration and structure of inhomogeneous graphs

De Panafieu, Élie.
We analyze a general model of weighted graphs, introduced by de Panafieu and Ravelomanana (2014) and similar to the inhomogeneous graph model of Söderberg (2002). We investigate the sum of the weights of those graphs and their structure. Those results allow us to give a new proof in a more general […]

Negative $q$-Stirling numbers

Cai, Yue ; Readdy, Margaret.
The notion of the negative $q$-binomial was recently introduced by Fu, Reiner, Stanton and Thiem. Mirroring the negative $q$-binomial, we show the classical $q$ -Stirling numbers of the second kind can be expressed as a pair of statistics on a subset of restricted growth words. The resulting […]

Non-commutative Frobenius characteristic of generalized parking functions : Application to enumeration

Priez, Jean-Baptiste ; Virmaux, Aladin.
We give a recursive definition of generalized parking functions that allows them to be viewed as a species. From there we compute a non-commutative characteristic of the generalized parking function module and deduce some enumeration formulas of structures and isomorphism types. We give as well an […]

Ehrhart Positivity for Generalized Permutohedra

Castillo, Federico ; Liu, Fu.
There are few general results about the coefficients of Ehrhart polynomials. We present a conjecture about their positivity for a certain family of polytopes known as generalized permutohedra. We have verified the conjecture for small dimensions combining perturbation methods with a […]

Enumerating some symmetry classes of rhombus tilings of holey hexagons

Gilmore, Tomack.
This extended abstract presents some recent (exact and asymptotic) enumerative results concerning rhombustilings of hexagons that have had symmetrically distributed inward pointing triangles of side length 2 removedfrom their interiors. These results form part of a larger article that is currently […]

Generating functions of bipartite maps on orientable surfaces (extended abstract)

Chapuy, Guillaume ; Fang, Wenjie.
We compute, for each genus $g$ ≥ 0, the generating function $L$$g$ ≡ $L$$g$($t$;$p$1,$p$2,...) of (labelled) bipartite maps on the orientable surface of genus $g$, with control on all face degrees. We exhibit an explicit change of variables such […]

Matching Ensembles (Extended Abstract)

Oh, Suho ; Yoo, Hwanchul.
We introduce an axiom system for a collection of matchings that describes the triangulation of product of simplices.

How to get the weak order out of a digraph ?

Viard, Francois.
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 […]

An extension of Tamari lattices

Préville-Ratelle, Louis-François ; Viennot, Xavier.
For any finite path $v$ on the square lattice consisting of north and east unit steps, we construct a poset Tam$(v)$ that consists of all the paths lying weakly above $v$ with the same endpoints as $v$. For particular choices of $v$, we recover the traditional Tamari lattice and the $m$-Tamari […]

The Cambrian Hopf Algebra

Chatel, G. ; Pilaud, V..
Cambrian trees are oriented and labeled trees which fulfill local conditions around each node generalizing the conditions for classical binary search trees. Based on the bijective correspondence between signed permutations and leveled Cambrian trees, we define the Cambrian Hopf algebra generalizing […]

Combinatorial Hopf Algebras of Simplicial Complexes

Benedetti, Carolina ; Hallam, Joshua ; Machacek, John.
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 […]

On bijections between monotone rooted trees and the comb basis

Liu, Fu.
Let $A$ be an $n$-element set. Let $\mathscr{L} ie_2(A)$ be the multilinear part of the free Lie algebra on $A$ with a pair of compatible Lie brackets, and $\mathscr{L} ie_2(A, i)$ the subspace of $\mathscr{L} ie_2(A)$ generated by all the monomials in $\mathscr{L} ie_2(A)$ with $i$ brackets of one […]

A bijection between irreducible k-shapes and surjective pistols of height $k-1$

Bigeni, Ange.
This paper constructs a bijection between irreducible $k$-shapes and surjective pistols of height $k-1$, which carries the "free $k$-sites" to the fixed points of surjective pistols. The bijection confirms a conjecture of Hivert and Mallet (FPSAC 2011) that the number of irreducible $k$-shape is […]

Graph Orientations and Linear Extensions.

Iriarte, Benjamin.
Given an underlying undirected simple graph, we consider the set of all acyclic orientations of its edges. Each of these orientations induces a partial order on the vertices of our graph, and therefore we can count the number of linear extensions of these posets. We want to know which choice of […]

A factorization formula for power series

Birmajer, Daniel ; Gil, Juan B. ; Weiner, Michael D..
Given an odd prime p, we give an explicit factorization over the ring of formal power series with integer coefficients for certain reducible polynomials whose constant term is of the form $p^w$ with $w>1$. Our formulas are given in terms of partial Bell polynomials and rely on the inversion formula […]

Interval positroid varieties and a deformation of the ring of symmetric functions

Knutson, Allen ; Lederer, Mathias.
Define the interval rank $r_[i,j] : Gr_k(\mathbb C^n) →\mathbb{N}$ of a k-plane V as the dimension of the orthogonal projection $π _[i,j](V)$ of V to the $(j-i+1)$-dimensional subspace that uses the coordinates $i,i+1,\ldots,j$. By measuring all these ranks, we define the interval rank […]

Bucshbaum simplicial posets

Browder, Jonathan ; Klee, Steven.
The family of Buchsbaum simplicial posets generalizes the family of simplicial cell manifolds. The $h'-$vector of a simplicial complex or simplicial poset encodes the combinatorial and topological data of its face numbers and the reduced Betti numbers of its geometric realization. Novik and Swartz […]

Flag Gromov-Witten invariants via crystals

Morse, Jennifer ; Schilling, Anne.
We apply ideas from crystal theory to affine Schubert calculus and flag Gromov-Witten invariants. By defining operators on certain decompositions of elements in the type-$A$ affine Weyl group, we produce a crystal reflecting the internal structure of Specht modules associated to permutation […]

Bijactions in Cataland

Williams, Nathan.
In this abstract, I will survey the story of two enumerative miracles that relate certain Coxeter-theoretic objects and other poset-theoretic objects. The first miracle relates reduced words and linear extensions, while the second may be thought of as relating group elements and order ideals. The […]

A simple recurrence formula for the number of rooted maps on surfaces by edges and genus

Carrell, Sean ; Chapuy, Guillaume.
We establish a simple recurrence formula for the number $Q_g^n$ of rooted orientable maps counted by edges and genus. The formula is a consequence of the KP equation for the generating function of bipartite maps, coupled with a Tutte equation, and it was apparently unnoticed before. It gives by far […]

Selberg integrals and Hankel determinants

Ishikawa, Masao ; Zeng, Jiang.
In our previous works "Pfaffian decomposition and a Pfaffian analogue of $q$-Catalan Hankel determinants'' (by M.Ishikawa, H. Tagawa and J. Zeng, J. Combin. Theory Ser. A, 120, 2013, 1263-1284) we have proposed several ways to evaluate certain Catalan-Hankel Pffafians and also formulated several […]

Firing Patterns in the Parallel Chip-Firing Game

Scully, Ziv ; Jiang, Tian-Yi ; Zhang, Yan, .
The $\textit{parallel chip-firing game}$ is an automaton on graphs in which vertices "fire'' chips to their neighbors. This simple model, analogous to sandpiles forming and collapsing, contains much emergent complexity and has connections to different areas of mathematics including self-organized […]

Peak algebras, paths in the Bruhat graph and Kazhdan-Lusztig polynomials

Brenti, Francesco ; Caselli, Fabrizio.
We obtain a nonrecursive combinatorial formula for the Kazhdan-Lusztig polynomials which holds in complete generality and which is simpler and more explicit than any existing one, and which cannot be linearly simplified. Our proof uses a new basis of the peak subalgebra of the algebra of […]

A Murgnahan-Nakayama rule for Schubert polynomials

Morrison, Andrew.
We expose a rule for multiplying a general Schubert polynomial with a power sum polynomial in $k$ variables. A signed sum over cyclic permutations replaces the signed sum over rim hooks in the classical Murgnahan-Nakayama rule. In the intersection theory of flag manifolds this computes all […]

Piecewise-linear and birational toggling

Einstein, David ; Propp, James.
We define piecewise-linear and birational analogues of toggle-involutions, rowmotion, and promotion on order ideals of a poset $P$ as studied by Striker and Williams. Piecewise-linear rowmotion relates to Stanley's transfer map for order polytopes; piecewise-linear promotion relates to […]

Honeycombs from Hermitian Matrix Pairs

Appleby, Glenn ; Whitehead, Tamsen.
Knutson and Tao's work on the Horn conjectures used combinatorial invariants called hives and honeycombs to relate spectra of sums of Hermitian matrices to Littlewood-Richardson coefficients and problems in representation theory, but these relationships remained implicit. Here, let $M$ and $N$ be […]

Noncrossing sets and a Graßmannian associahedron

Santos, Francisco ; Stump, Christian ; Welker, Volkmar.
We study a natural generalization of the noncrossing relation between pairs of elements in $[n]$ to $k$-tuples in $[n]$. We show that the flag simplicial complex on $\binom{[n]}{k}$ induced by this relation is a regular, unimodular and flag triangulation of the order polytope of the poset given by […]

Centralizers of the infinite symmetric group

Daugherty, Zajj ; Herbrich, Peter.
We review and introduce several approaches to the study of centralizer algebras of the infinite symmetric group $S_{\infty}$. Our work is led by the double commutant relationship between finite symmetric groups and partition algebras; in the case of $S_{\infty}$, we obtain centralizer algebras that […]

SIF Permutations and Chord-Connected Permutations

Blitvić, Natasha.
A stabilized-interval-free (SIF) permutation on [n], introduced by Callan, is a permutation that does not stabilize any proper interval of [n]. Such permutations are known to be the irreducibles in the decomposition of permutations along non-crossing partitions. That is, if $s_n$ denotes the […]

Arrangements of equal minors in the positive Grassmannian

Farber, Miriam ; Postnikov, Alexander.
We discuss arrangements of equal minors in totally positive matrices. More precisely, we would like to investigate the structure of possible equalities and inequalities between the minors. We show that arrangements of equals minors of largest value are in bijection with sorted sets, which […]

Yamanouchi toppling

Cori, Robert ; Senato, Domenico ; Petrullo, Pasquale.
We study an extension of the chip-firing game. A given set of admissible moves, called Yamanouchi moves, allows the player to pass from a starting configuration $\alpha$ to a further configuration $\beta$. This can be encoded via an action of a certain group, the toppling group, associated with each […]

The freeness of ideal subarrangements of Weyl arrangements

Abe, Takuro ; Barakat, Mohamed ; Cuntz, Michael ; Hoge, Torsten ; Terao, Hiroaki.
A Weyl arrangement is the arrangement defined by the root system of a finite Weyl group. When a set of positive roots is an ideal in the root poset, we call the corresponding arrangement an ideal subarrangement. Our main theorem asserts that any ideal subarrangement is a free arrangement and that […]

Sorting with two stacks in parallel

Albert, Michael ; Bousquet-Mélou, Mireille.
At the end of the 1960s, Knuth characterised in terms of forbidden patterns the permutations that can be sorted using a stack. He also showed that they are in bijection with Dyck paths and thus counted by the Catalan numbers. Subsequently, Pratt and Tarjan asked about permutations that can be sorted […]

Deformations of Weyl's Denominator Formula

Hamel, Angêle,  ; King, Ronald, .
We introduce a series of conjectured identities that deform Weyl's denominator formula and generalize Tokuyama's formula to other root systems. These conjectures generalize a number of well-known results due to Okada. We also prove a related result for $B'_n$ that generalizes a theorem of Simpson.

A product formula for the TASEP on a ring

Aas, Erik ; Sjöstrand, Jonas.
For a random permutation sampled from the stationary distribution of the TASEP on a ring, we show that, conditioned on the event that the first entries are strictly larger than the last entries, the $\textit{order}$ of the first entries is independent of the $\textit{order}$ of the last entries. The […]

Hopf Algebra of Sashes

Law, Shirley.
A general lattice theoretic construction of Reading constructs Hopf subalgebras of the Malvenuto-Reutenauer Hopf algebra (MR) of permutations. The products and coproducts of these Hopf subalgebras are defined extrinsically in terms of the embedding in MR. The goal of this paper is to find an […]

Bijections on m-level Rook Placements

Barrese, Kenneth ; Sagan, Bruce, .
Partition the rows of a board into sets of $m$ rows called levels. An $m$-level rook placement is a subset of squares of the board with no two in the same column or the same level. We construct explicit bijections to prove three theorems about such placements. We start with two bijections between […]

Positroids, non-crossing partitions, and positively oriented matroids

Ardila, Federico ; Rincón, Felipe ; Williams, Lauren.
We investigate the role that non-crossing partitions play in the study of positroids, a class of matroids introduced by Postnikov. We prove that every positroid can be constructed uniquely by choosing a non-crossing partition on the ground set, and then freely placing the structure of a connected […]

Affine permutations and rational slope parking functions

Gorsky, Eugene ; Mazin, Mikhail ; Vazirani, Monica.
We introduce a new approach to the enumeration of rational slope parking functions with respect to the area and a generalized dinv statistics, and relate the combinatorics of parking functions to that of affine permutations. We relate our construction to two […]

Chevalley-Monk and Giambelli formulas for Peterson Varieties

Drellich, Elizabeth.
A Peterson variety is a subvariety of the flag variety $G/B$ defined by certain linear conditions. Peterson varieties appear in the construction of the quantum cohomology of partial flag varieties and in applications to the Toda flows. Each Peterson variety has a one-dimensional torus $S^1$ acting […]

Gallery Posets of Supersolvable Arrangements

McConville, Thomas.
We introduce a poset structure on the reduced galleries in a supersolvable arrangement of hyperplanes. In particular, for Coxeter groups of type A or B, we construct a poset of reduced words for the longest element whose Hasse diagram is the graph of reduced words. Using Rambau's Suspension Lemma, […]

Weakly prudent self-avoiding bridges

Bacher, Axel ; Beaton, Nicholas, .
We define and enumerate a new class of self-avoiding walks on the square lattice, which we call weakly prudent bridges. Their definition is inspired by two previously-considered classes of self-avoiding walks, and can be viewed as a combination of those two models. We consider several methods […]

Hopf algebra of permutation pattern functions

Vargas, Yannic.
We study permutation patterns from an algebraic combinatorics point of view. Using analogues of the classical shuffle and infiltration products for word, we define two new Hopf algebras of permutations related to the notion of permutation pattern. We show several remarkable properties of permutation […]

Sweep maps for lattice paths

Loehr, Nicholas,  ; Warrington, Gregory, .
Sweep maps are a family of maps on words that, while simple to define, are not yet known to be injective in general. This family subsumes many of the "zeta maps" that have arisen in the study of q,t-Catalan numbers in the course of relating the three statistics of area, bounce and dinv. A sweep map […]

Descents of $\lambda$-unimodal cyclic permutations

Archer, Kassie.
We prove an identity conjectured by Adin and Roichman involving the descent set of $\lambda$-unimodal cyclic permutations. These permutations appear in the character formulas for certain representations of the symmetric group and these formulas are usually proven algebraically. Here, we give a […]

Coloring Rings in Species

White, Jacob, .
We present a generalization of the chromatic polynomial, and chromatic symmetric function, arising in the study of combinatorial species. These invariants are defined for modules over lattice rings in species. The primary examples are graphs and set partitions. For these new invariants, we present […]

A new generation tree for permutations, preserving the number of fixed points

Duchon, Philippe ; Duvignau, Romaric.
We describe a new uniform generation tree for permutations with the specific property that, for most permutations, all of their descendants in the generation tree have the same number of fixed points. Our tree is optimal for the number of permutations having this property. We then use this tree to […]

Combinatorics of diagrams of permutations

Lewis, Joel Brewster ; Morales, Alejandro, .
There are numerous combinatorial objects associated to a Grassmannian permutation $w_λ$ that index cells of the totally nonnegative Grassmannian. We study some of these objects (rook placements, acyclic orientations, various restricted fillings) and their q-analogues in the case of permutations […]

Hall-Littlewood Polynomials in terms of Yamanouchi words

Roberts, Austin.
This paper uses the theory of dual equivalence graphs to give explicit Schur expansions to several families of symmetric functions. We begin by giving a combinatorial definition of the modified Macdonald polynomials and modified Hall-Littlewood polynomials indexed by any diagram $δ ⊂ \mathbb{Z} […]

Schubert varieties, inversion arrangements, and Peterson translation

Slofstra, William.
We show that an element $\mathcal{w}$ of a finite Weyl group W is rationally smooth if and only if the hyperplane arrangement $\mathcal{I} (\mathcal{w})$ associated to the inversion set of \mathcal{w} is inductively free, and the product $(d_1+1) ...(d_l+1)$ of the coexponents $d_1,\ldots,d_l$ is […]

Partial categorification of Hopf algebras and representation theory of towers of \mathcalJ-trivial monoids

Virmaux, Aladin.
This paper considers the representation theory of towers of algebras of $\mathcal{J} -trivial$ monoids. Using a very general lemma on induction, we derive a combinatorial description of the algebra and coalgebra structure on the Grothendieck rings $G_0$ and $K_0$. We then apply our theory to some […]

The order of birational rowmotion

Grinberg, Darij ; Roby, Tom.
Various authors have studied a natural operation (under various names) on the order ideals (equivalently antichains) of a finite poset, here called \emphrowmotion. For certain posets of interest, the order of this map is much smaller than one would naively expect, and the orbits exhibit unexpected […]

Some combinatorics of rhomboid-shaped fully packed loop configurations

Beil, Sabine.
The study of rhomboid-shaped fully packed loop configurations (RFPLs) is inspired by the work of Fischer and Nadeau on triangular fully packed loop configurations (TFPLs). By using the same techniques as they did some nice combinatorics for RFPLs arise. To each RFPL and to each oriented RFPL a […]

Bott-Samelson Varieties, Subword Complexes and Brick Polytopes

Escobar, Laura.
Bott-Samelson varieties factor the flag variety $G/B$ into a product of $\mathbb{C}\mathbb{P}^1$'s with a map into $G/B$. These varieties are mostly studied in the case in which the map into $G/B$ is birational; however in this paper we study fibers of this map when it is not birational. We will see […]

The arithmetic Tutte polynomials of the classical root systems

Ardila, Federico ; Castillo, Federico ; Henley, Michael.
Many combinatorial and topological invariants of a hyperplane arrangement can be computed in terms of its Tutte polynomial. Similarly, many invariants of a hypertoric arrangement can be computed in terms of its arithmetic Tutte polynomial. We compute the arithmetic Tutte polynomials of the […]

A diagrammatic approach to Kronecker squares

Vallejo, Ernesto.
In this paper we improve a method of Robinson and Taulbee for computing Kronecker coefficients and show that for any partition $øverline{ν}$ of $d$ there is a polynomial $k_{øverline{ν}}$ with rational coefficients in variables $x_C$, where $C$ runs over the set of isomorphism classes of connected […]

Quasisymmetric Schur functions and modules of the $0$-Hecke algebra

Tewari, Vasu,  ; van Willigenburg, Stephanie, .
We define a $0$-Hecke action on composition tableaux, and then use it to derive $0$-Hecke modules whose quasisymmetric characteristic is a quasisymmetric Schur function. We then relate the modules to the weak Bruhat order and use them to derive a new basis for quasisymmetric functions. We also […]

Reflection factorizations of Singer cycles

Lewis, J.B. ; Reiner, V. ; Stanton, D..
The number of shortest factorizations into reflections for a Singer cycle in $GL_n(\mathbb{F}_q)$ is shown to be $(q^n-1)^{n-1}$. Formulas counting factorizations of any length, and counting those with reflections of fixed conjugacy classes are also given.

Splines, lattice points, and (arithmetic) matroids

Lenz, Matthias.
Let $X$ be a $(d \times N)$-matrix. We consider the variable polytope $\Pi_X(u) = \left\{ w \geq 0 : Xw = u \right\}$. It is known that the function $T_X$ that assigns to a parameter $u \in \mathbb{R}^N$ the volume of the polytope $\Pi_X(u)$ is piecewise polynomial. Formulas of Khovanskii-Pukhlikov […]

An equivariant rim hook rule for quantum cohomology of Grassmannians

Beazley, Elizabeth ; Bertiger, Anna ; Taipale, Kaisa.
A driving question in (quantum) cohomology of flag varieties is to find non-recursive, positive combinatorial formulas for expressing the quantum product in a particularly nice basis, called the Schubert basis. Bertram, Ciocan-Fontanine and Fulton provide a way to compute quantum products of […]

Poset topology and homological invariants of algebras arising in algebraic combinatorics

Margolis, Stuart ; Saliola, Franco ; Steinberg, Benjamin.
We present a beautiful interplay between combinatorial topology and homological algebra for a class of monoids that arise naturally in algebraic combinatorics. We explore several applications of this interplay. For instance, we provide a new interpretation of the Leray number of a clique complex in […]

A generalization of the carries process

Fujita, Takahiko ; Nakano, Fumihiko ; Sadahiro, Taizo.
We consider a carries process which is a generalization of that by Holte in the sense that (i) we take various digit sets, and (ii) we also consider negative base. Our results are : (i) eigenvalues and eigenvectors of the transition probability matrices, and their connection to combinatorics and […]

Super quasi-symmetric functions via Young diagrams

Aval, Jean-Christophe ; Féray, Valentin ; Novelli, Jean-Christophe ; Thibon, J.-Y..
We consider the multivariate generating series $F_P$ of $P-$partitions in infinitely many variables $x_1, x_2, \ldots$ . For some family of ranked posets $P$, it is natural to consider an analog $N_P$ with two infinite alphabets. When we collapse these two alphabets, we trivially recover $F_P$. Our […]

Many neighborly inscribed polytopes and Delaunay triangulations

Gonska, Bernd ; Padrol, Arnau.
We present a very simple explicit technique to generate a large family of point configurations with neighborly Delaunay triangulations. This proves that there are superexponentially many combinatorially distinct neighborly $d$-polytopes with $n$ vertices that admit realizations inscribed on the […]

Kronecker coefficients: the tensor square conjecture and unimodality

Pak, Igor ; Panova, Greta ; Vallejo, Ernesto.
We consider two aspects of Kronecker coefficients in the directions of representation theory and combinatorics. We consider a conjecture of Jan Saxl stating that the tensor square of the $S_n$-irreducible representation indexed by the staircase partition contains every irreducible representation of […]

Newton Polytopes of Cluster Variables of Type $A_n$

Kalman, Adam.
We study Newton polytopes of cluster variables in type $A_n$ cluster algebras, whose cluster and coefficient variables are indexed by the diagonals and boundary segments of a polygon. Our main results include an explicit description of the affine hull and facets of the Newton polytope of the Laurent […]

Factorization of the Characteristic Polynomial

Hallam, Joshua ; Sagan, Bruce, .
We introduce a new method for showing that the roots of the characteristic polynomial of a finite lattice are all nonnegative integers. Our method gives two simple conditions under which the characteristic polynomial factors. We will see that Stanley's Supersolvability Theorem is a corollary of this […]

Bijective Proofs of Partition Identities of MacMahon, Andrews, and Subbarao

Fu, Shishuo ; Sellers, James, .
We revisit a classic partition theorem due to MacMahon that relates partitions with all parts repeated at least once and partitions with parts congruent to $2,3,4,6 \pmod{6}$, together with a generalization by Andrews and two others by Subbarao. Then we develop a unified bijective proof for all four […]

The Selberg integral and Young books

Kim, Jang Soo ; Oh, Suho.
The Selberg integral is an important integral first evaluated by Selberg in 1944. Stanley found a combinatorial interpretation of the Selberg integral in terms of permutations. In this paper, new combinatorial objects "Young books'' are introduced and shown to have a connection with the Selberg […]

The $m$-Cover Posets and the Strip-Decomposition of $m$-Dyck Paths

Kallipoliti, Myrto ; Mühle, Henri.
In the first part of this article we present a realization of the $m$-Tamari lattice $\mathcal{T}_n^{(m)}$ in terms of $m$-tuples of Dyck paths of height $n$, equipped with componentwise rotation order. For that, we define the $m$-cover poset $\mathcal{P}^{\langle m \rangle}$ of an arbitrary bounded […]

On Bruhat posets associated to compositions

Can, Mahir Bilen ; Cherniavsky, Yonah.
The purpose of this work is to initiate a combinatorial study of the Bruhat-Chevalley ordering on certain sets of permutations obtained by omitting the parentheses from their standard cyclic notation. In particular, we show that these sets form bounded, graded, unimodal, rank-symmetric and […]

Signed tree associahedra

Pilaud, Vincent.
An associahedron is a polytope whose vertices correspond to the triangulations of a convex polygon and whose edges correspond to flips between them. J.-L. Loday gave a particularly elegant realization of the associahedron, which was then generalized in two directions: on the one hand to obtain […]

Estimating deep Littlewood-Richardson Coefficients

Narayanan, Hariharan.
Littlewood Richardson coefficients are structure constants appearing in the representation theory of the general linear groups $(GL_n)$. The main results of this paper are: 1. A strongly polynomial randomized approximation scheme for Littlewood-Richardson coefficients corresponding to indices […]

An extension of MacMahon's Equidistribution Theorem to ordered multiset partitions

Wilson, Andrew Timothy.
A classical result of MacMahon states that inversion number and major index have the same distribution over permutations of a given multiset. In this work we prove a strengthening of this theorem originally conjectured by Haglund. Our result can be seen as an equidistribution theorem over the […]

Boyd-Maxwell ball packings

Chen, Hao ; Labbé, Jean-Philippe.
In the recent study of infinite root systems, fractal patterns of ball packings were observed while visualizing roots in affine space. In fact, the observed fractals are exactly the ball packings described by Boyd and Maxwell. This correspondence is a corollary of a more fundamental result: given a […]

On the $H$-triangle of generalised nonnesting partitions

Thiel, Marko.
With a crystallographic root system $\Phi$ , there are associated two Catalan objects, the set of nonnesting partitions $NN(\Phi)$, and the cluster complex $\Delta (\Phi)$. These possess a number of enumerative coincidences, many of which are captured in a surprising identity, first conjectured by […]

Bigraphical arrangements

Hopkins, Sam ; Perkinson, David.
We define the bigraphical arrangement of a graph and show that the Pak-Stanley labels of its regions are the parking functions of a closely related graph, thus proving conjectures of Duval, Klivans, and Martin and of Hopkins and Perkinson. A consequence is a new proof of a bijection between labeled […]

Polytopes and $C^1$-convex bodies

Adiprasito, Karim ; Samper, José Alejandro.
The face numbers of simplicial polytopes that approximate $C^1$-convex bodies in the Hausdorff metric is studied. Several structural results about the skeleta of such polytopes are studied and used to derive a lower bound theorem for this class of polytopes. This partially resolves a conjecture made […]

Genus one partitions

Cori, Robert ; Hetyei, Gábor.
We prove the conjecture by M. Yip stating that counting genus one partitions by the number of their elements and parts yields, up to a shift of indices, the same array of numbers as counting genus one rooted hypermonopoles. Our proof involves representing each genus one permutation by a four-colored […]

Tropical Graph Parameters

Labai, Nadia ; Makowsky, Johann, .
Connection matrices for graph parameters with values in a field have been introduced by M. Freedman, L. Lovász and A. Schrijver (2007). Graph parameters with connection matrices of finite rank can be computed in polynomial time on graph classes of bounded tree-width. We introduce join matrices, a […]

Electrical network and Lie theory

Su, Yi.
Curtis-Ingerman-Morrow studied the space of circular planar electrical networks, and classified all possible response matrices for such networks. Lam and Pylyavskyy found a Lie group $EL_{2n}$ whose positive part $(EL_{2n})_{\geq 0}$ naturally acts on the circular planar electrical network via some […]

Symmetry properties of the Novelli-Pak-Stoyanovskii algorithm

Sulzgruber, Robin.
The number of standard Young tableaux of a fixed shape is famously given by the hook-length formula due to Frame, Robinson and Thrall. A bijective proof of Novelli, Pak and Stoyanovskii relies on a sorting algorithm akin to jeu-de-taquin which transforms an arbitrary filling of a partition into a […]

The purity of set-systems related to Grassmann necklaces

Danilov, Vladimir,  ; Karzanov, Alexander,  ; Koshevoy, Gleb, .
Studying the problem of quasicommuting quantum minors, Leclerc and Zelevinsky introduced in 1998 the notion of weakly separated sets in $[n]:=\{1,\ldots, n\}$. Moreover, they raised several conjectures on the purity for this symmetric relation, in particular, on the Boolean cube $2^{[n]}$. In […]

Generalized Dyck tilings (Extended Abstract)

Josuat-Vergès, Matthieu ; Kim, Jang Soo.
Recently, Kenyon and Wilson introduced Dyck tilings, which are certain tilings of the region between two Dyck paths. The enumeration of Dyck tilings is related with hook formulas for forests and the combinatorics of Hermite polynomials. The first goal of this work is to give an alternative point of […]

$\ell$-restricted $Q$-systems and quantum affine algebras

Gleitz, Anne-Sophie.
Kuniba, Nakanishi, and Suzuki (1994) have formulated a general conjecture expressing the positive solution of an $\ell$-restricted $Q$-system in terms of quantum dimensions of Kirillov-Reshetikhin modules. After presenting this conjecture, we sketch a proof for the exceptional type $E_6$ following […]

Two special cases of the Rational Shuffle Conjecture

Leven, Emily.
The Classical Shuffle Conjecture of Haglund et al. (2005) has a symmetric function side and a combinatorial side. The combinatorial side $q,t$-enumerates parking functions in the $n ×n$ lattice. The symmetric function side may be simply expressed as $∇ e_n$ , where $∇$ is the Macdonald […]

$0$-Hecke algebra action on the Stanley-Reisner ring of the Boolean algebra

Huang, Jia.
We define an action of the $0$-Hecke algebra of type A on the Stanley-Reisner ring of the Boolean algebra. By studying this action we obtain a family of multivariate noncommutative symmetric functions, which specialize to the noncommutative Hall-Littlewood symmetric functions and their […]

Number of cycles in the graph of $312$-avoiding permutations

Ehrenborg, Richard ; Kitaev, Sergey ; Steingrımsson, Einar.
The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their […]

Supercharacters of Unipotent Groups

Andrews, Scott.
\textbfAbstract. We construct supercharacter theories of finite unipotent groups in the orthogonal, symplectic and unitary types. Our method utilizes group actions in a manner analogous to that of Diaconis and Isaacs in their construction of supercharacters of algebra groups. The resulting […]

The topology of the permutation pattern poset

McNamara, Peter,  ; Steingrımsson, Einar.
The set of all permutations, ordered by pattern containment, forms a poset. This extended abstract presents the first explicit major results on the topology of intervals in this poset. We show that almost all (open) intervals in this poset have a disconnected subinterval and are thus not shellable. […]

Two bijections on Tamari Intervals

Chapoton, Frédéric ; Chatel, Gregory ; Pons, Viviane.
We use a recently introduced combinatorial object, the $\textit{interval-poset}$, to describe two bijections on intervals of the Tamari lattice. Both bijections give a combinatorial proof of some previously known results. The first one is an inner bijection between Tamari intervals that exchanges […]

Quasisymmetric (k,l)-hook Schur functions

Mason, Sarah,  ; Niese, Elizabeth.
We introduce a quasisymmetric generalization of Berele and Regev's hook Schur functions and prove that these new quasisymmetric hook Schur functions decompose the hook Schur functions in a natural way. In this paper we examine the combinatorics of the quasisymmetric hook Schur functions, providing […]

The Rearrangement Conjecture

Pantone, Jay ; Vatter, Vincent.
The Rearrangement Conjecture states that if two words over $\mathbb{P}$ are Wilf-equivalent in the factor order on $\mathbb{P}^{\ast}$ then they are rearrangements of each other. We introduce the notion of strong Wilf-equivalence and prove that if two words over $\mathbb{P}$ are strongly […]

A $q,t-$analogue of Narayana numbers

Aval, Jean-Christophe ; D'Adderio, Michele ; Dukes, Mark ; Hicks, Angela ; Le Borgne, Yvan.
We study the statistics $\mathsf{area}$, $\mathsf{bounce}$ and $\mathsf{dinv}$ associated to polyominoes in a rectangular box $m$ times $n$. We show that the bi-statistics ($\mathsf{area}$,$\mathsf{bounce}$) and ($\mathsf{area}$,$\mathsf{dinv}$) give rise to the same $q,t-$analogue of Narayana […]

Top Coefficients of the Denumerant

Baldoni, Velleda ; Berline, Nicole ; Dutra, Brandon ; Köppe, Matthias ; Vergne, Michele ; De Loera, Jesus.
For a given sequence $\alpha = [\alpha_1,\alpha_2,\ldots , \alpha_N, \alpha_{N+1}]$ of $N+1$ positive integers, we consider the combinatorial function $E(\alpha)(t)$ that counts the nonnegative integer solutions of the equation $\alpha_1x_1+\alpha_2 x_2+ \ldots+ \alpha_Nx_N+ \alpha_{N+1}x_{N+1}=t$, […]

Combinatorial Topology of Toric arrangements

d'Antonio, Giacomo ; Delucchi, Emanuele.
We prove that the complement of a complexified toric arrangement has the homotopy type of a minimal CW-complex, and thus its homology is torsion-free. To this end, we consider the toric Salvetti complex, a combinatorial model for the arrangement's complement. Using diagrams of acyclic categories we […]

A Parking Function Setting for Nabla Images of Schur Functions

Kim, Yeonkyung.
In this article, we show how the compositional refinement of the ``Shuffle Conjecture'' due to Jim Haglund, Jennifer Morse, and Mike Zabrocki can be used to express the image of a Schur function under the Bergeron-Garsia Nabla operator as a weighted sum of a suitable collection of ``Parking […]

Asymptotic properties of some minor-closed classes of graphs (conference version)

Bousquet-Mélou, Mireille ; Weller, Kerstin.
Let $\mathcal{A}$ be a minor-closed class of labelled graphs, and let $G_n$ be a random graph sampled uniformly from the set of n-vertex graphs of $\mathcal{A}$. When $n$ is large, what is the probability that $G_n$ is connected? How many components does it have? How large is its biggest component? […]

EL-labelings and canonical spanning trees for subword complexes

Pilaud, Vincent ; Stump, Christian.
We describe edge labelings of the increasing flip graph of a subword complex on a finite Coxeter group, and study applications thereof. On the one hand, we show that they provide canonical spanning trees of the facet-ridge graph of the subword complex, describe inductively these trees, and present […]

On the Topology of the Cambrian Semilattices

Kallipoliti, Myrto ; Mühle, Henri.
For an arbitrary Coxeter group $W$, David Speyer and Nathan Reading defined Cambrian semilattices $C_{\gamma}$ as certain sub-semilattices of the weak order on $W$. In this article, we define an edge-labelling using the realization of Cambrian semilattices in terms of $\gamma$-sortable elements, and […]

Poset vectors and generalized permutohedra

Croitoru, Dorian ; Oh, Suho ; Postnikov, Alexander.
We show that given a poset $P$ and and a subposet $Q$, the integer points obtained by restricting linear extensions of $P$ to $Q$ can be explained via integer lattice points of a generalized permutohedron.

A Hopf-power Markov chain on compositions

Pang, C.Y. Amy.
In a recent paper, Diaconis, Ram and I constructed Markov chains using the coproduct-then-product map of a combinatorial Hopf algebra. We presented an algorithm for diagonalising a large class of these "Hopf-power chains", including the Gilbert-Shannon-Reeds model of riffle-shuffling of a deck of […]

Singularity analysis via the iterated kernel method

Melczer, Stephen ; Mishna, Marni.
We provide exact and asymptotic counting formulas for five singular lattice path models in the quarter plane. Furthermore, we prove that these models have a non D-finite generating function.

Eulerian polynomials of type $D$ have only real roots

Savage, Carla D. ; Visontai, Mirkó.
We give an intrinsic proof of a conjecture of Brenti that all the roots of the Eulerian polynomial of type $D$ are real and a proof of a conjecture of Dilks, Petersen, and Stembridge that all the roots of the affine Eulerian polynomial of type $B$ are real, as well.

On Kerov polynomials for Jack characters (extended abstract)

Féray, Valentin ; Dołęga, Maciej.
We consider a deformation of Kerov character polynomials, linked to Jack symmetric functions. It has been introduced recently by M. Lassalle, who formulated several conjectures on these objects, suggesting some underlying combinatorics. We give a partial result in this direction, showing that some […]

Root-theoretic Young Diagrams, Schubert Calculus and Adjoint Varieties

Searles, Dominic ; Yong, Alexander.
Root-theoretic Young diagrams are a conceptual framework to discuss existence of a root-system uniform and manifestly non-negative combinatorial rule for Schubert calculus. Our main results use them to obtain formulas for (co)adjoint varieties of classical Lie type. This case is the simplest after […]

A generalization of Mehta-Wang determinant and Askey-Wilson polynomials

Guo, Victor J. W. ; Ishikawa, Masao ; Tagawa, Hiroyuki ; Zeng, Jiang.
Motivated by the Gaussian symplectic ensemble, Mehta and Wang evaluated the $n×n$ determinant $\det ((a+j-i)Γ (b+j+i))$ in 2000. When $a=0$, Ciucu and Krattenthaler computed the associated Pfaffian $\mathrm{Pf}((j-i)Γ (b+j+i))$ with an application to the two dimensional dimer system in 2011. […]

Extending the parking space

Berget, Andrew ; Rhoades, Brendon.
The action of the symmetric group $S_n$ on the set $\mathrm{Park}_n$ of parking functions of size $n$ has received a great deal of attention in algebraic combinatorics. We prove that the action of $S_n$ on $\mathrm{Park}_n$ extends to an action of $S_{n+1}$. More precisely, we construct a graded […]

Kazhdan-Lusztig polynomials of boolean elements

Mongelli, Pietro.
We give closed combinatorial product formulas for Kazhdan–Lusztig poynomials and their parabolic analogue of type $q$ in the case of boolean elements, introduced in [M. Marietti, Boolean elements in Kazhdan–Lusztig theory, J. Algebra 295 (2006)], in Coxeter groups whose Coxeter graph is a tree. Such […]

Redfield-Pólya theorem in $\mathrm{WSym}$

Bultel, Jean-Paul ; Chouria, Ali ; Luque, Jean-Gabriel ; Mallet, Olivier.
We give noncommutative versions of the Redfield-Pólya theorem in $\mathrm{WSym}$, the algebra of word symmetric functions, and in other related combinatorial Hopf algebras.

Structure coefficients of the Hecke algebra of $(\mathcal{S}_{2n}, \mathcal{B}_n)$

Tout, Omar.
The Hecke algebra of the pair $(\mathcal{S}_{2n}, \mathcal{B}_n)$, where $\mathcal{B}_n$ is the hyperoctahedral subgroup of $\mathcal{S}_{2n}$, was introduced by James in 1961. It is a natural analogue of the center of the symmetric group algebra. In this paper, we give a polynomiality property of […]

Number of standard strong marked tableaux

Fishel, Susanna ; Konvalinka, Matjaž.
Many results involving Schur functions have analogues involving $k-$Schur functions. Standard strong marked tableaux play a role for $k-$Schur functions similar to the role standard Young tableaux play for Schur functions. We discuss results and conjectures toward an analogue of the hook length […]

Generation modulo the action of a permutation group

Borie, Nicolas.
Originally motivated by algebraic invariant theory, we present an algorithm to enumerate integer vectors modulo the action of a permutation group. This problem generalizes the generation of unlabeled graph up to an isomorphism. In this paper, we present the full development of a generation engine by […]

The combinatorics of CAT(0) cubical complexes

Ardila, Federico ; Baker, Tia ; Yatchak, Rika.
Given a reconfigurable system $X$, such as a robot moving on a grid or a set of particles traversing a graph without colliding, the possible positions of $X$ naturally form a cubical complex $\mathcal{S}(X)$. When $\mathcal{S}(X)$ is a CAT(0) space, we can explicitly construct the shortest path […]

Gelfand Models for Diagram Algebras

Halverson, Tom.
A Gelfand model for a semisimple algebra $\mathsf{A}$ over $\mathbb{C}$ is a complex linear representation that contains each irreducible representation of $\mathsf{A}$ with multiplicity exactly one. We give a method of constructing these models that works uniformly for a large class of […]

Some simple varieties of trees arising in permutation analysis

Bouvel, Mathilde ; Mishna, Marni ; Nicaud, Cyril.
After extending classical results on simple varieties of trees to trees counted by their number of leaves, we describe a filtration of the set of permutations based on their strong interval trees. For each subclass we provide asymptotic formulas for number of trees (by leaves), average number of […]

Algebraic properties for some permutation statistics

Vong, Vincent.
In this article, we study some quotient sets on permutations built from peaks, valleys, double rises and double descents. One part is dedicated to the enumeration of the cosets using the bijection of Francon-Viennot which is a bijection between permutations and the so-called Laguerre histories. Then […]

Divisors on graphs, Connected flags, and Syzygies

Mohammadi, Fatemeh ; Shokrieh, Farbod.
We study the binomial and monomial ideals arising from linear equivalence of divisors on graphs from the point of view of Gröbner theory. We give an explicit description of a minimal Gröbner basis for each higher syzygy module. In each case the given minimal Gröbner basis is also a minimal […]

The probability of planarity of a random graph near the critical point

Noy, Marc ; Ravelomanana, Vlady ; Rué, Juanjo.
Erdős and Rényi conjectured in 1960 that the limiting probability $p$ that a random graph with $n$ vertices and $M=n/2$ edges is planar exists. It has been shown that indeed p exists and is a constant strictly between 0 and 1. In this paper we answer completely this long standing question by finding […]

A bijection between permutations and a subclass of TSSCPPs

Striker, Jessica.
We define a subclass of totally symmetric self-complementary plane partitions (TSSCPPs) which we show is in direct bijection with permutation matrices. This bijection maps the inversion number of the permutation, the position of the 1 in the last column, and the position of the 1 in the last row to […]

Balanced labellings of affine permutations

Yoo, Hwanchul ; Yun, Taedong.
We study the $\textit{diagrams}$ of affine permutations and their $\textit{balanced}$ labellings. As in the finite case, which was investigated by Fomin, Greene, Reiner, and Shimozono, the balanced labellings give a natural encoding of reduced decompositions of affine permutations. In fact, we show […]

The critical surface fugacity for self-avoiding walks on a rotated honeycomb lattice

Beaton, Nicholas R..
In a recent paper with Bousquet-Mélou, de Gier, Duminil-Copin and Guttmann (2012), we proved that a model of self-avoiding walks on the honeycomb lattice, interacting with an impenetrable surface, undergoes an adsorption phase transition when the surface fugacity is 1+√2. Our proof used a […]

A Divided Difference Operator

Teff, Nicholas.
We construct a divided difference operator using GKM theory. This generalizes the classical divided difference operator for the cohomology of the complete flag variety. This construction proves a special case of a recent conjecture of Shareshian and Wachs. Our methods are entirely combinatorial and […]

Arc-Coloured Permutations

Yen, Lily.
The equidistribution of many crossing and nesting statistics exists in several combinatorial objects like matchings, set partitions, permutations, and embedded labelled graphs. The involutions switching nesting and crossing numbers for set partitions given by Krattenthaler, also by Chen, Deng, Du, […]

Lattice of combinatorial Hopf algebras: binary trees with multiplicities

Priez, Jean-Baptiste.
In a first part, we formalize the construction of combinatorial Hopf algebras from plactic-like monoids using polynomial realizations. Thank to this construction we reveal a lattice structure on those combinatorial Hopf algebras. As an application, we construct a new combinatorial Hopf algebra on […]

Non-symmetric Cauchy kernels

Azenhas, Olga ; Emami, Aram.
Using an analogue of the Robinson-Schensted-Knuth (RSK) algorithm for semi-skyline augmented fillings, due to Sarah Mason, we exhibit expansions of non-symmetric Cauchy kernels $∏_(i,j)∈\eta (1-x_iy_j)^-1$, where the product is over all cell-coordinates $(i,j)$ of the stair-type partition shape […]

A Murnaghan-Nakayama Rule for Generalized Demazure Atoms

LoBue, Jamine ; Remmel, Jeffrey B..
We prove an analogue of the Murnaghan-Nakayama rule to express the product of a power symmetric function and a generalized Demazure atom in terms of generalized Demazure atoms.

The height of the Lyndon tree

Mercier, Lucas ; Chassaing, Philippe.
We consider the set $\mathcal{L}_n<$ of n-letters long Lyndon words on the alphabet $\mathcal{A}=\{0,1\}$. For a random uniform element ${L_n}$ of the set $\mathcal{L}_n$, the binary tree $\mathfrak{L} (L_n)$ obtained by successive standard factorization of $L_n$ and of the factors produced by these […]

The Gaussian free field and strict plane partitions

Vuletić, Mirjana.
We study height fluctuations around the limit shape of a measure on strict plane partitions. It was shown in our earlier work that this measure is a Pfaffian process. We show that the height fluctuations converge to a pullback of the Green's function for the Laplace operator with Dirichlet boundary […]

Convolution Powers of the Identity

Aguiar, Marcelo ; Lauve, Aaron.
We study convolution powers $\mathtt{id}^{\ast n}$ of the identity of graded connected Hopf algebras $H$. (The antipode corresponds to $n=-1$.) The chief result is a complete description of the characteristic polynomial - both eigenvalues and multiplicity - for the action of the operator […]

Coefficients of algebraic functions: formulae and asymptotics

Banderier, Cyril ; Drmota, Michael.
This paper studies the coefficients of algebraic functions. First, we recall the too-little-known fact that these coefficients $f_n$ have a closed form. Then, we study their asymptotics, known to be of the type $f_n \sim C A^n n^{\alpha}$. When the function is a power series associated to a […]

Long Cycle Factorizations: Bijective Computation in the General Case

Vassilieva, Ekaterina A..
This paper is devoted to the computation of the number of ordered factorizations of a long cycle in the symmetric group where the number of factors is arbitrary and the cycle structure of the factors is given. Jackson (1988) derived the first closed form expression for the generating series of these […]

On the ranks of configurations on the complete graph

Cori, Robert ; Borgne, Yvan Le.
We consider the parameter rank introduced for graph configurations by M. Baker and S. Norine. We focus on complete graphs and obtain an efficient algorithm to determine the rank for these graphs. The analysis of this algorithm leads to the definition of a parameter on Dyck words, which we call […]

Weighted partitions

D'León, Rafael González S. ; Wachs, Michelle L..
In this extended abstract we consider the poset of weighted partitions Π _n^w, introduced by Dotsenko and Khoroshkin in their study of a certain pair of dual operads. The maximal intervals of Π _n^w provide a generalization of the lattice Π _n of partitions, which we show possesses many of the […]

Operators of equivalent sorting power and related Wilf-equivalences

Albert, Michael ; Bouvel, Mathilde.
We study sorting operators $\textrm{A}$ on permutations that are obtained composing Knuth's stack sorting operator \textrmS and the reverse operator $\textrm{R}$, as many times as desired. For any such operator $\textrm{A}$, we provide a bijection between the set of permutations sorted by […]

Pattern-avoiding Dyck paths

Bernini, Antonio ; Ferrari, Luca ; Pinzani, Renzo ; West, Julian.
We introduce the notion of $\textit{pattern}$ in the context of lattice paths, and investigate it in the specific case of Dyck paths. Similarly to the case of permutations, the pattern-containment relation defines a poset structure on the set of all Dyck paths, which we call the $\textit{Dyck […]

Cycles and sorting index for matchings and restricted permutations

Poznanović, Svetlana.
We prove that the Mahonian-Stirling pairs of permutation statistics $(sor, cyc)$ and $(∈v , \mathrm{rlmin})$ are equidistributed on the set of permutations that correspond to arrangements of $n$ non-atacking rooks on a fixed Ferrers board with $n$ rows and $n$ columns. The proofs are combinatorial […]

Gale-Robinson Sequences and Brane Tilings

Jeong, In-Jee ; Musiker, Gregg ; Zhang, Sicong.
We study variants of Gale-Robinson sequences, as motivated by cluster algebras with principal coefficients. For such cases, we give combinatorial interpretations of cluster variables using brane tilings, as from the physics literature.

The Robinson―Schensted Correspondence and $A_2$-webs

Housley, Matthew ; Russell, Heather M. ; Tymoczko, Julianna.
The $A_2$-spider category encodes the representation theory of the $sl_3$ quantum group. Kuperberg (1996) introduced a combinatorial version of this category, wherein morphisms are represented by planar graphs called $\textit{webs}$ and the subset of $\textit{reduced webs}$ forms bases for morphism […]

Periodic Patterns of Signed Shifts

Archer, Kassie ; Elizalde, Sergi.
The periodic patterns of a map are the permutations realized by the relative order of the points in its periodic orbits. We give a combinatorial description of the periodic patterns of an arbitrary signed shift, in terms of the structure of the descent set of a certain transformation of the pattern. […]

Patterns in matchings and rook placements

Bloom, Jonathan ; Elizalde, Sergi.
Extending the notion of pattern avoidance in permutations, we study matchings and set partitions whose arc diagram representation avoids a given configuration of three arcs. These configurations, which generalize 3-crossings and 3-nestings, have an interpretation, in the case of matchings, in terms […]

Rational Catalan Combinatorics: The Associahedron

Armstrong, Drew ; Rhoades, Brendon ; Williams, Nathan.
Each positive rational number $x>0$ can be written $\textbf{uniquely}$ as $x=a/(b-a)$ for coprime positive integers 0<$a$<$b$. We will identify $x$ with the pair $(a,b)$. In this extended abstract we use $\textit{rational Dyck paths}$ to define for each positive rational $x>0$ a simplicial complex […]

Homomesy in products of two chains

Propp, James ; Roby, Tom.
Many cyclic actions $τ$ on a finite set $\mathcal{S}$ ; of combinatorial objects, along with a natural statistic $f$ on $\mathcal{S}$, exhibit ``homomesy'': the average of $f$ over each $τ$-orbit in $\mathcal{S} $ is the same as the average of $f$ over the whole set $\mathcal{S} $. This phenomenon […]

Dual Equivalence Graphs Revisited

Roberts, Austin.
In 2007 Sami Assaf introduced dual equivalence graphs as a method for demonstrating that a quasisymmetric function is Schur positive. The method involves the creation of a graph whose vertices are weighted by Ira Gessel's fundamental quasisymmetric functions so that the sum of the weights of a […]

Counting strings over $\mathbb{Z}2^d$ with Given Elementary Symmetric Function Evaluations

Miers, Charles Robert ; Ruskey, Franck.
Let $\alpha$ be a string over $\mathbb{Z}_q$, where $q = 2^d$. The $j$-th elementary symmetric function evaluated at $\alpha$ is denoted $e_j(\alpha)$ . We study the cardinalities $S_q(m;\mathcal{T} _1,\mathcal{T} _2,\ldots,\mathcal{T} _t)$ of the set of length $m$ strings for which $e_j(\alpha) = […]

Evaluations of Hecke algebra traces at Kazhdan-Lusztig basis elements

Clearman, Sam ; Hyatt, Matthew ; Shelton, Brittany ; Skandera, Mark.
For irreducible characters $\{ \chi_q^{\lambda} | \lambda \vdash n\}$ and induced sign characters $\{\epsilon_q^{\lambda} | \lambda \vdash n\}$ of the Hecke algebra $H_n(q)$, and Kazhdan-Lusztig basis elements $C'_w(q)$ with $w$ avoiding the pattern 312, we combinatorially interpret the polynomials […]

q-Rook placements and Jordan forms of upper-triangular nilpotent matrices

Yip, Martha.
The set of $n$ by $n$ upper-triangular nilpotent matrices with entries in a finite field $F_q$ has Jordan canonical forms indexed by partitions $λ \vdash n$. We study a connection between these matrices and non-attacking q-rook placements, which leads to a combinatorial formula for the number$ F_λ […]

Generalized monotone triangles

Riegler, Lukas.
In a recent work, the combinatorial interpretation of the polynomial $\alpha (n; k_1,k_2,\ldots,k_n)$ counting the number of Monotone Triangles with bottom row $k_1 < k_2 < ⋯< k_n$ was extended to weakly decreasing sequences $k_1 ≥k_2 ≥⋯≥k_n$. In this case the evaluation of the polynomial is equal […]

A $t$-generalization for Schubert Representatives of the Affine Grassmannian

Dalal, Avinash J. ; Morse, Jennifer.
We introduce two families of symmetric functions with an extra parameter $t$ that specialize to Schubert representatives for cohomology and homology of the affine Grassmannian when $t=1$. The families are defined by a statistic on combinatorial objects associated to the type-$A$ affine Weyl group […]

The number of $k$-parallelogram polyominoes

Battaglino, Daniela ; Fédou, Jean-Marc ; Rinaldi, Simone ; Socci, Samanta.
A convex polyomino is $k$-$\textit{convex}$ if every pair of its cells can be connected by means of a $\textit{monotone path}$, internal to the polyomino, and having at most $k$ changes of direction. The number $k$-convex polyominoes of given semi-perimeter has been determined only for small values […]

The unreasonable ubiquitousness of quasi-polynomials

Woods, Kevin.
A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_m-1$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials classically – and ``reasonably'' – appear in Ehrhart theory and in other contexts where one […]

Counting words with Laguerre polynomials

Taylor, Jair.
We develop a method for counting words subject to various restrictions by finding a combinatorial interpretation for a product of formal sums of Laguerre polynomials. We use this method to find the generating function for $k$-ary words avoiding any vincular pattern that has only ones. We also give […]

Les polynômes eul\IeC èriens stables de type B

Visontai, Mirkó ; Williams, Nathan.
We give a multivariate analog of the type B Eulerian polynomial introduced by Brenti. We prove that this multivariate polynomial is stable generalizing Brenti's result that every root of the type B Eulerian polynomial is real. Our proof combines a refinement of the descent statistic for signed […]

Coherent fans in the space of flows in framed graphs

Danilov, Vladimir I. ; Karzanov, Alexander V. ; Koshevoy, Gleb A..
Let $G=(V,E)$ be a finite acyclic directed graph. Being motivated by a study of certain aspects of cluster algebras, we are interested in a class of triangulations of the cone of non-negative flows in $G, \mathcal F_+(G)$. To construct a triangulation, we fix a raming at each inner vertex $v$ of […]

Combinatorial Reciprocity for Monotone Triangles

Fischer, Ilse ; Riegler, Lukas.
The number of Monotone Triangles with bottom row $k_1 < k_2 < ⋯< k_n$ is given by a polynomial $\alpha (n; k_1,\ldots,k_n)$ in $n$ variables. The evaluation of this polynomial at weakly decreasing sequences $k_1 ≥k_2 ≥⋯≥k_n $turns out to be interpretable as signed enumeration of new combinatorial […]

A simple formula for bipartite and quasi-bipartite maps with boundaries

Collet, Gwendal ; Fusy, Eric.
We obtain a very simple formula for the generating function of bipartite (resp. quasi-bipartite) planar maps with boundaries (holes) of prescribed lengths, which generalizes certain expressions obtained by Eynard in a book to appear. The formula is derived from a bijection due to Bouttier, Di […]

Triangulations of cyclic polytopes

Oppermann, Steffen ; Thomas, Hugh.
We give a new description of the combinatorics of triangulations of even-dimensional cyclic polytopes, and of their bistellar flips. We show that the tropical exchange relation governing the number of intersections between diagonals of a polygon and a lamination (which generalizes to arbitrary […]

Extremal Statistics on Non-Crossing Configurations

Mier, Anna,  ; Noy, Marc.
We obtain several properties of extremal statistics in non-crossing configurations with n vertices. We prove that the maximum degree and the largest component are of logarithmic order, and the diameter is of order $\sqrt{n}$. The proofs are based on singularity analysis, an application of the first […]

Skew Pieri Rules for Hall-Littlewood Functions

Konvalinka, Matjaž ; Lauve, Aaron.
We produce skew Pieri Rules for Hall–Littlewood functions in the spirit of Assaf and McNamara (FPSAC, 2010). The first two were conjectured by the first author (FPSAC, 2011). The key ingredients in the proofs are a q-binomial identity for skew partitions that are horizontal strips and a Hopf […]

Cayley and Tutte polytopes

Konvalinka, Matjaž ; Pak, Igor.
Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun's conjecture, which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to a two-variable deformations, […]

Product of Stanley symmetric functions

Li, Nan.
We study the problem of expanding the product of two Stanley symmetric functions $F_w·F_u$ into Stanley symmetric functions in some natural way. Our approach is to consider a Stanley symmetric function as a stabilized Schubert polynomial $F_w=\lim _n→∞\mathfrak{S}_{1^n×w}$, and study the behavior of […]

Sorting and preimages of pattern classes

Claesson, Anders ; Úlfarsson, Henning.
We introduce an algorithm to determine when a sorting operation, such as stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a new proof of the description of West-2-stack-sortable permutations, that is permutations that are completely sorted when passed twice through a stack, […]

Hecke algebra and quantum chromatic symmetric functions

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

On a Subposet of the Tamari Lattice

Csar, Sebastian A. ; Sengupta, Rik ; Suksompong, Warut.
We discuss some properties of a subposet of the Tamari lattice introduced by Pallo (1986), which we call the comb poset. We show that three binary functions that are not well-behaved in the Tamari lattice are remarkably well-behaved within an interval of the comb poset: rotation distance, meets and […]

Moment graphs and KL-polynomials

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

Minimal transitive factorizations of a permutation of type (p,q)

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

Chromatic roots as algebraic integers

Bohn, Adam.
A chromatic root is a zero of the chromatic polynomial of a graph. At a Newton Institute workshop on Combinatorics and Statistical Mechanics in 2008, two conjectures were proposed on the subject of which algebraic integers can be chromatic roots, known as the ``$α +n$ conjecture'' and the ``$nα$ […]

Classification of Ehrhart polynomials of integral simplices

Higashitani, Akihiro.
Let $δ (\mathcal{P} )=(δ _0,δ _1,\ldots,δ _d)$ be the $δ$ -vector of an integral convex polytope $\mathcal{P}$ of dimension $d$. First, by using two well-known inequalities on $δ$ -vectors, we classify the possible $δ$ -vectors with $\sum_{i=0}^d δ _i ≤3$. Moreover, by means of Hermite normal forms […]

A simple model of trees for unicellular maps

Chapuy, Guillaume ; Feray, Valentin ; Fusy, Eric.
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 […]

EL-Shellability of Generalized Noncrossing Partitions

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

Noncommutative symmetric functions with matrix parameters

Lascoux, Alain ; Novelli, Jean-Christophe ; Thibon, Jean-Yves.
We define new families of noncommutative symmetric functions and quasi-symmetric functions depending on two matrices of parameters, and more generally on parameters associated with paths in a binary tree. Appropriate specializations of both matrices then give back the two-vector families of Hivert, […]

Phylogenetic trees and the tropical geometry of flag varieties

Manon, Christopher.
We will discuss some recent theorems relating the space of weighted phylogenetic trees to the tropical varieties of each flag variety of type A. We will also discuss the tropicalizations of the functions corresponding to semi-standard tableaux, in particular we relate them to familiar functions from […]

Correlations for the Novak process

Nordenstam, Eric ; Young, Benjamin.
We study random lozenge tilings of a certain shape in the plane called the Novak half-hexagon, and compute the correlation functions for this process. This model was introduced by Nordenstam and Young (2011) and has many intriguing similarities with a more well-studied model, domino tilings of the […]

An algorithm which generates linear extensions for a non-simply-laced d-complete poset with uniform probability

Nakada, Kento.
\textbfAbstract. The purpose of this paper is to present an algorithm which generates linear extensions for a non-simply-laced d-complete poset with uniform probability. ≠wline

The multivariate arithmetic Tutte polynomial

Brändèn, Petter ; Moci, Luca.
We introduce an arithmetic version of the multivariate Tutte polynomial recently studied by Sokal, and a quasi-polynomial that interpolates between the two. We provide a generalized Fortuin-Kasteleyn representation for representable arithmetic matroids, with applications to arithmetic colorings and […]

New light on Bergman complexes by decomposing matroid types

Dlugosch, Martin.
Bergman complexes are polyhedral complexes associated to matroids. Faces of these complexes are certain matroids, called matroid types, too. In order to understand the structure of these faces we decompose matroid types into direct summands. Ardila/Klivans proved that the Bergman Complex of a […]

Bijections for lattice paths between two boundaries

Elizalde, Sergi ; Rubey, Martin.
We prove that on the set of lattice paths with steps $N=(0,1)$ and $E=(1,0)$ that lie between two boundaries $B$ and $T$, the two statistics `number of $E$ steps shared with $B$' and `number of $E$ steps shared with $T$' have a symmetric joint distribution. We give an involution that switches these […]

Computing Tutte Polynomials

Monagan, Michael.
We present a new edge selection heuristic and vertex ordering heuristic that together enable one to compute the Tutte polynomial of much larger sparse graphs than was previously doable. As a specific example, we are able to compute the Tutte polynomial of the truncated icosahedron graph using our […]

Constructing neighborly polytopes and oriented matroids

Padrol, Arnau.
A $d$-polytope $P$ is neighborly if every subset of $\lfloor\frac{d}{2}\rfloor $vertices is a face of $P$. In 1982, Shemer introduced a sewing construction that allows to add a vertex to a neighborly polytope in such a way as to obtain a new neighborly polytope. With this, he constructed […]

The Möbius function of generalized subword order

McNamara, Peter R. W. ; Sagan, Bruce E..
Let $P$ be a poset and let $P^*$ be the set of all finite length words over $P$. Generalized subword order is the partial order on $P^*$ obtained by letting $u≤ w$ if and only if there is a subword $u'$ of $w$ having the same length as $u$ such that each element of $u$ is less than or equal to the […]

Combinatorial Hopf algebra of supercharacters of type D

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

Modified Growth Diagrams, Permutation Pivots, and the BWX Map $\phi^*$

Bloom, Jonathan ; Saracino, Dan.
In their paper on Wilf-equivalence for singleton classes, Backelin, West, and Xin introduced a transformation $\phi^*$, defined by an iterative process and operating on (all) full rook placements on Ferrers boards. Bousquet-Mélou and Steingrimsson proved the analogue of the main result of Backelin, […]

On an algebraicity theorem of Kontsevich

Reutenauer, Christophe ; Robado, Marco.
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 […]

Enumeration of Graded (3 + 1)-Avoiding Posets

Lewis Brewster, Joel ; Zhang, Yan X.
The notion of (3+1)-avoidance appears in many places in enumerative combinatorics, but the natural goal of enumerating all (3+1)-avoiding posets remains open. In this paper, we enumerate \emphgraded (3+1)-avoiding posets. Our proof consists of a number of structural theorems followed by some […]

On the degree-chromatic polynomial of a tree

Cifuentes, Diego.
The degree chromatic polynomial $P_m(G,k)$ of a graph $G$ counts the number of $k$ -colorings in which no vertex has m adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.

Involutions on Baxter Objects

Dilks, Kevin.
Baxter numbers are known to count several families of combinatorial objects, all of which come equipped with natural involutions. In this paper, we add a combinatorial family to the list, and show that the known bijections between these objects respect these involutions. We also give a formula for […]

Constellations and multicontinued fractions: application to Eulerian triangulations

Albenque, Marie ; Bouttier, Jérémie.
We consider the problem of enumerating planar constellations with two points at a prescribed distance. Our approach relies on a combinatorial correspondence between this family of constellations and the simpler family of rooted constellations, which we may formulate algebraically in terms of […]

Flows on Simplicial Complexes

Beck, Matthias ; Kemper, Yvonne.
Given a graph $G$, the number of nowhere-zero $\mathbb{Z}_q$-flows $\phi _G(q)$ is known to be a polynomial in $q$. We extend the definition of nowhere-zero $\mathbb{Z} _q$-flows to simplicial complexes $\Delta$ of dimension greater than one, and prove the polynomiality of the corresponding function […]

Crystal energy via charge

Lenart, Cristian ; Schilling, Anne.
The Ram–Yip formula for Macdonald polynomials (at t=0) provides a statistic which we call charge. In types ${A}$ and ${C}$ it can be defined on tensor products of Kashiwara–Nakashima single column crystals. In this paper we show that the charge is equal to the (negative of the) energy function on […]

Excedances in classical and affine Weyl groups

Mongelli, Pietro.
Based on the notion of colored and absolute excedances introduced by Bagno and Garber we give an analogue of the derangement polynomials. We obtain some basic properties of these polynomials. Moreover, we define an excedance statistic for the affine Weyl groups of type $\widetilde{B}_n, \widetilde […]

An explicit formula for ndinv, a new statistic for two-shuffle parking functions

Hicks, Angela ; Kim, Yeonkyung.
In a recent paper, Duane, Garsia, and Zabrocki introduced a new statistic, "ndinv'', on a family of parking functions. The definition was guided by a recursion satisfied by the polynomial $\langle\Delta_{h_m}C_p1C_p2...C_{pk}1,e_n\rangle$, for $\Delta_{h_m}$ a Macdonald eigenoperator, $C_{p_i}$ a […]

On the Sperner property and Gorenstein Algebras Associated to Matroids

Maeno, Toshiaki ; Numata, Yasuhide.
We introduce a certain class of algebras associated to matroids. We prove the Lefschetz property of the algebras for some special cases. Our result implies the Sperner property for the Boolean lattice and the vector space lattice.

Tropical Oriented Matroids

Horn, Silke.
Tropical oriented matroids were defined by Ardila and Develin in 2007. They are a tropical analogue of classical oriented matroids in the sense that they encode the properties of the types of points in an arrangement of tropical hyperplanes – in much the same way as the covectors of (classical) […]

Explicit generating series for connection coefficients

Vassilieva, Ekaterina A..
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 […]

Symmetries of the k-bounded partition lattice

Berg, Chris ; Zabrocki, Mike.
We generalize the symmetry on Young's lattice, found by Suter, to a symmetry on the $k$-bounded partition lattice of Lapointe, Lascoux and Morse.

Polynomials and Parking Functions

Hicks, Angela.
In a 2010 paper Haglund, Morse, and Zabrocki studied the family of polynomials $\nabla C_{p1}\dots C_{pk}1$ , where $p=(p_1,\ldots,p_k)$ is a composition, $\nabla$ is the Bergeron-Garsia Macdonald operator and the $C_\alpha$ are certain slightly modified Hall-Littlewood vertex operators. They […]

Proofs of two conjectures of Kenyon and Wilson on Dyck tilings

Kim, Jang Soo.
Recently, Kenyon and Wilson introduced a certain matrix M in order to compute pairing probabilities of what they call the double-dimer model. They showed that the absolute value of each entry of the inverse matrix $M^-1$ is equal to the number of certain Dyck tilings of a skew shape. They […]

Integrality of hook ratios

Dehaye, Paul-Olivier.
We study integral ratios of hook products of quotient partitions. This question is motivated by an analogous question in number theory concerning integral factorial ratios. We prove an analogue of a theorem of Landau that already applied in the factorial case. Under the additional condition that the […]

Generalized associahedra via brick polytopes

Pilaud, Vincent ; Stump, Christian.
We generalize the brick polytope of V. Pilaud and F. Santos to spherical subword complexes for finite Coxeter groups. This construction provides polytopal realizations for a certain class of subword complexes containing all cluster complexes of finite types. For the latter, the brick polytopes turn […]

Multi-cluster complexes

Ceballos, Cesar ; Labbé, Jean-Philippe ; Stump, Christian.
We present a family of simplicial complexes called \emphmulti-cluster complexes. These complexes generalize the concept of cluster complexes, and extend the notion of multi-associahedra of types ${A}$ and ${B}$ to general finite Coxeter groups. We study combinatorial and geometric properties of […]

A polynomial realization of the Hopf algebra of uniform block permutations

Maurice, Rémi.
We investigate the combinatorial Hopf algebra based on uniform block permutations and we realize this algebra in terms of noncommutative polynomials in infinitely many bi-letters.

A generalization of the alcove model and its applications

Lenart, Cristian ; Lubovsky, Arthur.
The alcove model of the first author and Postnikov describes highest weight crystals of semisimple Lie algebras. We present a generalization, called the quantum alcove model, and conjecture that it uniformly describes tensor products of column shape Kirillov-Reshetikhin crystals, for all untwisted […]

Cartan invariant matrices for finite monoids

Thiéry, Nicolas M..
Let $M$ be a finite monoid. In this paper we describe how the Cartan invariant matrix of the monoid algebra of $M$ over a field $\mathbb{K}$ of characteristic zero can be expressed using characters and some simple combinatorial statistic. In particular, it can be computed efficiently from the […]

Enumeration of Cylindric Plane Partitions

Langer, Robin.
Cylindric plane partitions may be thought of as a natural generalization of reverse plane partitions. A generating series for the enumeration of cylindric plane partitions was recently given by Borodin. As in the reverse plane partition case, the right hand side of this identity admits a simple […]

Combinatorial specification of permutation classes

Bassino, Frédérique ; Bouvel, Mathilde ; Pierrot, Adeline ; Pivoteau, Carine ; Rossin, Dominique.
This article presents a methodology that automatically derives a combinatorial specification for the permutation class $\mathcal{C} = Av(B)$, given its basis $B$ of excluded patterns and the set of simple permutations in $\mathcal{C}$, when these sets are both finite. This is achieved considering […]

$Star^1$-convex functions on tropical linear spaces of complete graphs

Escobar, Laura.
Given a fan $\Delta$ and a cone $\sigma \in \Delta$ let $star^1(\sigma )$ be the set of cones that contain $\sigma$ and are one dimension bigger than $\sigma$ . In this paper we study two cones of piecewise linear functions defined on $\delta$ : the cone of functions which are convex on […]

Standard fillings to parking functions

Niese, Elizabeth.
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 […]

Fusion coefficients

Morse, Jennifer ; Schilling, Anne.
Using the expansion of the inverse of the Kostka matrix in terms of tabloids as presented by Eğecioğlu and Remmel, we show that the fusion coefficients can be expressed as an alternating sum over cylindric tableaux. Cylindric tableaux are skew tableaux with a certain cyclic symmetry. When the skew […]

Universal Polynomials for Severi Degrees of Toric Surfaces

Ardila, Federico ; Block, Florian.
The Severi variety parametrizes plane curves of degree $d$ with $\delta$ nodes. Its degree is called the Severi degree. For large enough $d$, the Severi degrees coincide with the Gromov-Witten invariants of $\mathbb{CP}^2$. Fomin and Mikhalkin (2009) proved the 1995 conjecture that for fixed […]

Enumeration of permutations sorted with two passes through a stack and D_8 symmetries

Bouvel, Mathilde ; Guibert, Olivier.
We examine the sets of permutations that are sorted by two passes through a stack with a $D_8$ operation performed in between. From a characterization of these in terms of generalized excluded patterns, we prove two conjectures on their enumeration, that can be refined with the distribution of some […]

Which Schubert varieties are local complete intersections?

Úlfarsson, Henning ; Woo, Alexander.
We characterize by pattern avoidance the Schubert varieties for $\mathrm{GL}_n$ which are local complete intersections (lci). For those Schubert varieties which are local complete intersections, we give an explicit minimal set of equations cutting out their neighbourhoods at the identity. Although […]

An inequality of Kostka numbers and Galois groups of Schubert problems

Brooks, Christopher J. ; Campo, Abraham Mart\'ın,  ; Sottile, Frank.
We show that the Galois group of any Schubert problem involving lines in projective space contains the alternating group. Using a criterion of Vakil and a special position argument due to Schubert, this follows from a particular inequality among Kostka numbers of two-rowed tableaux. In most cases, […]

Extending from bijections between marked occurrences of patterns to all occurrences of patterns

Remmel, Jeffrey ; Tiefenbruck, Mark.
We consider two recent open problems stating that certain statistics on various sets of combinatorial objects are equidistributed. The first, posed by Anders Claesson and Svante Linusson, relates nestings in matchings on $\{1,2,\ldots,2n\}$ to occurrences of a certain pattern in permutations in […]

Flow polytopes and the Kostant partition function

Mészáros, Karola ; Morales, Alejandro H..
We establish the relationship between volumes of flow polytopes associated to signed graphs and the Kostant partition function. A special case of this relationship, namely, when the graphs are signless, has been studied in detail by Baldoni and Vergne using techniques of residues. In contrast with […]

Perturbation of transportation polytopes

Liu, Fu.
We describe a perturbation method that can be used to compute the multivariate generating function (MGF) of a non-simple polyhedron, and then construct a perturbation that works for any transportation polytope. Applying this perturbation to the family of central transportation polytopes of order $kn […]

The ABC's of affine Grassmannians and Hall-Littlewood polynomials

Dalal, Avinash J. ; Morse, Jennifer.
We give a new description of the Pieri rule for $k$-Schur functions using the Bruhat order on the affine type-$A$ Weyl group. In doing so, we prove a new combinatorial formula for representatives of the Schubert classes for the cohomology of affine Grassmannians. We show how new combinatorics […]

Lifted generalized permutahedra and composition polynomials

Ardila, Federico ; Doker, Jeffrey.
We introduce a "lifting'' construction for generalized permutohedra, which turns an $n$-dimensional generalized permutahedron into an $(n+1)$-dimensional one. We prove that this construction gives rise to Stasheff's multiplihedron from homotopy theory, and to the more general "nestomultiplihedra,'' […]

$q$-Floor Diagrams computing Refined Severi Degrees for Plane Curves

Block, Florian.
The Severi degree is the degree of the Severi variety parametrizing plane curves of degree $d$ with $\delta$ nodes. Recently, Göttsche and Shende gave two refinements of Severi degrees, polynomials in a variable $q$, which are conjecturally equal, for large $d$. At $q=1$, one of the refinements, the […]

Maximal Newton polygons via the quantum Bruhat graph

Beazley, Elizabeth T..
This paper discusses a surprising relationship between the quantum cohomology of the variety of complete flags and the partially ordered set of Newton polygons associated to an element in the affine Weyl group. One primary key to establishing this connection is the fact that paths in the quantum […]

Dyck tilings, linear extensions, descents, and inversions

Kim, Jang Soo ; Mészáros, Karola ; Panova, Greta ; Wilson, David B..
Dyck tilings were introduced by Kenyon and Wilson in their study of double-dimer pairings. They are certain kinds of tilings of skew Young diagrams with ribbon tiles shaped like Dyck paths. We give two bijections between "cover-inclusive'' Dyck tilings and linear extensions of tree posets. The first […]

Asymptotical behaviour of roots of infinite Coxeter groups I

Hohlweg, Christophe ; Labbé, Jean-Philippe ; Ripoll, Vivien.
Let $W$ be an infinite Coxeter group, and $\Phi$ be the root system constructed from its geometric representation. We study the set $E$ of limit points of "normalized'' roots (representing the directions of the roots). We show that $E$ is contained in the isotropic cone $Q$ of the bilinear form […]

Data Streams as Random Permutations: the Distinct Element Problem

Helmi, Ahmed ; Lumbroso, Jérémie ; Martínez, Conrado ; Viola, Alfredo.
In this paper, we show that data streams can sometimes usefully be studied as random permutations. This simple observation allows a wealth of classical and recent results from combinatorics to be recycled, with minimal effort, as estimators for various statistics over data streams. We illustrate […]

On the number of transversals in random trees

Gittenberger, Bernhard ; Kraus, Veronika.
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 […]

Matching solid shapes in arbitrary dimension via random sampling

Schymura, Daria.
We give simple probabilistic algorithms that approximately maximize the volume of overlap of two solid, i.e. full-dimensional, shapes under translations and rigid motions. The shapes are subsets of $ℝ^d$ where $d≥ 2$. The algorithms approximate with respect to an pre-specified additive error and […]

Additive tree functionals with small toll functions and subtrees of random trees

Wagner, Stephan.
Many parameters of trees are additive in the sense that they can be computed recursively from the sum of the branches plus a certain toll function. For instance, such parameters occur very frequently in the analysis of divide-and-conquer algorithms. Here we are interested in the situation that the […]

Biased Boltzmann samplers and generation of extended linear languages with shuffle

Darrasse, Alexis ; Panagiotou, Konstantinos ; Roussel, Olivier ; Soria, Michele.
This paper is devoted to the construction of Boltzmann samplers according to various distributions, and uses stochastic bias on the parameter of a Boltzmann sampler, to produce a sampler with a different distribution for the size of the output. As a significant application, we produce Boltzmann […]

Exact $L^2$-Distance from the Limit for QuickSort Key Comparisons (Extended Abstract)

Bindjeme, Patrick ; fill, james Allen.
Using a recursive approach, we obtain a simple exact expression for the $L^2$-distance from the limit in the classical limit theorem of Régnier (1989) for the number of key comparisons required by $\texttt{QuickSort}$. A previous study by Fill and Janson (2002) using a similar approach found that […]

Analysis of Digital Expansions of Minimal Weight

Heigl, Florian ; Heuberger, Clemens.
Extending an idea of Suppakitpaisarn, Edahiro and Imai, a dynamic programming approach for computing digital expansions of minimal weight is transformed into an asymptotic analysis of minimal weight expansions. The minimal weight of an optimal expansion of a random input of length $\ell$ is shown to […]

On the Number of 2-Protected Nodes in Tries and Suffix Trees

Gaither, Jeffrey ; Homma, Yushi ; Sellke, Mark ; Ward, Mark Daniel.
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 […]

Toward the asymptotic count of bi-modular hidden patterns under probabilistic dynamical sources: a case study

Lhote, Loïck ; Lladser, Manuel E..
Consider a countable alphabet $\mathcal{A}$. A multi-modular hidden pattern is an $r$-tuple $(w_1,\ldots , w_r)$, where each $w_i$ is a word over $\mathcal{A}$ called a module. The hidden pattern is said to occur in a text $t$ when the later admits the decomposition $t = v_0 w_1v_1 \cdots v_{r−1}w_r […]

Generic properties of random subgroups of a free group for general distributions

Bassino, Frédérique ; Nicaud, Cyril ; Weil, Pascal.
We consider a generalization of the uniform word-based distribution for finitely generated subgroups of a free group. In our setting, the number of generators is not fixed, the length of each generator is determined by a random variable with some simple constraints and the distribution of words of a […]

On total variation approximations for random assemblies

Manstavičius, Eugenijus.
We prove a total variation approximation for the distribution of component vector of a weakly logarithmic random assembly. The proof demonstrates an analytic approach based on a comparative analysis of the coefficients of two power series.

Domination analysis for scheduling on non preemptive uniformly related machines

Eisner, Idan ; Vainshtein, Alek.
no abstract

On Bernoulli Sums and Bernstein Polynomials

Cichoń, Jacek ; Gołębiewski, Zbigniew.
In the paper we discuss a technology based on Bernstein polynomials of asymptotic analysis of a class of binomial sums that arise in information theory. Our method gives a quick derivation of required sums and can be generalized to multinomial distributions. As an example we derive a formula for the […]

Mixing times of Markov chains on 3-Orientations of Planar Triangulations

Miracle, Sarah ; Randall, Dana ; Streib, Amanda Pascoe ; Tetali, Prasad.
Given a planar triangulation, a 3-orientation is an orientation of the internal edges so all internal vertices have out-degree three. Each 3-orientation gives rise to a unique edge coloring known as a $\textit{Schnyder wood}$ that has proven useful for various computing and combinatorics […]

Exactly Solvable Balanced Tenable Urns with Random Entries via the Analytic Methodology

Morcrette, Basile ; Mahmoud, Hosam M..
This paper develops an analytic theory for the study of some Pólya urns with random rules. The idea is to extend the isomorphism theorem in Flajolet et al. (2006), which connects deterministic balanced urns to a differential system for the generating function. The methodology is based upon […]

Adaptive compression against a countable alphabet

Bontemps, Dominique ; Boucheron, Stephane ; Gassiat, Elisabeth.
This paper sheds light on universal coding with respect to classes of memoryless sources over a countable alphabet defined by an envelope function with finite and non-decreasing hazard rate. We prove that the auto-censuring (AC) code introduced by Bontemps (2011) is adaptive with respect to the […]

Asymptotics of Divide-And-Conquer Recurrences Via Iterated Function Systems

Kieffer, John, .
Let $k≥2$ be a fixed integer. Given a bounded sequence of real numbers $(a_n:n≥k)$, then for any sequence $(f_n:n≥1)$ of real numbers satisfying the divide-and-conquer recurrence $f_n = (k-mod(n,k))f_⌊n/k⌋+mod(n,k)f_⌈n/k⌉ + a_n, n ≥k$, there is a unique continuous periodic function […]

A New Binomial Recurrence Arising in a Graphical Compression Algorithm

Choi, Yongwook ; Knessl, Charles ; Szpankowski, Wojciech.
In a recently proposed graphical compression algorithm by Choi and Szpankowski (2009), the following tree arose in the course of the analysis. The root contains n balls that are consequently distributed between two subtrees according to a simple rule: In each step, all balls independently move down […]

Approximate Counting via the Poisson-Laplace-Mellin Method

Fuchs, Michael ; Lee, Chung-Kuei ; Prodinger, Helmut.
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 […]

On death processes and urn models

Kuba, Markus ; Panholzer, Alois.
We use death processes and embeddings into continuous time in order to analyze several urn models with a diminishing content. In particular we discuss generalizations of the pill's problem, originally introduced by Knuth and McCarthy, and generalizations of the well known sampling without […]

The Limiting Distribution for the Number of Symbol Comparisons Used by QuickSort is Nondegenerate (Extended Abstract)

Bindjeme, Patrick ; fill, james Allen.
In a continuous-time setting, Fill (2012) proved, for a large class of probabilistic sources, that the number of symbol comparisons used by $\texttt{QuickSort}$, when centered by subtracting the mean and scaled by dividing by time, has a limiting distribution, but proved little about that limiting […]

Stokes polyhedra for $X$-shaped polyminos

Baryshnikov, Yu. ; Hickok, L. ; Orlow, N. ; Son, S..
Consider a pair of $\textit{interlacing regular convex polygons}$, each with $2(n + 2)$ vertices, which we will be referring to as $\textit{red}$ and $\textit{black}$ ones. One can place these vertices on the unit circle $|z | = 1$ in the complex plane; the vertices of the red polygon at […]

Mean field analysis for inhomogeneous bike sharing systems

Fricker, Christine ; Gast, Nicolas ; Mohamed, Hanene.
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 […]

Asymptotic behavior of some statistics in Ewens random permutations

Feray, Valentin.
The purpose of this article is to present a general method to find limiting laws for some renormalized statistics on random permutations. The model considered here is Ewens sampling model, which generalizes uniform random permutations. We describe the asymptotic behavior of a large family of […]

Enumeration and Random Generation of Concurrent Computations

Bodini, Olivier ; Genitrini, Antoine ; Peschanski, Frédéric.
In this paper, we study the shuffle operator on concurrent processes (represented as trees) using analytic combinatorics tools. As a first result, we show that the mean width of shuffle trees is exponentially smaller than the worst case upper-bound. We also study the expected size (in total number […]

On Greedy Trie Execution

Gołębiewski, Zbigniew ; Zagórski, Filip.
In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping fair coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen. We give an answer to the […]

Some exact asymptotics in the counting of walks in the quarter plane

Fayolle, Guy ; Raschel, Kilian.
Enumeration of planar lattice walks is a classical topic in combinatorics, at the cross-roads of several domains (e.g., probability, statistical physics, computer science). The aim of this paper is to propose a new approach to obtain some exact asymptotics for walks confined to the quarter plane.

Invariants of vector configurations

Berget, Andrew ; Fink, Alex.
We investigate the Zariski closure of the projective equivalence class of a matrix. New results are presented regarding the matrices in this variety and their matroids, and we give equations for the variety. We also discuss the K-polynomial of the closure of a projective equivalence class, and two […]

Permutation Polytopes of Cyclic Groups

Baumeister, Barbara ; Haase, Christian ; Nill, Benjamin ; Paffenholz, Andreas.
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 […]

The down operator and expansions of near rectangular k-Schur functions

Berg, Chris ; Saliola, Franco ; Serrano, Luis.
We prove that the Lam-Shimozono ``down operator'' on the affine Weyl group induces a derivation of the affine Fomin-Stanley subalgebra of the affine nilCoxeter algebra. We use this to verify a conjecture of Berg, Bergeron, Pon and Zabrocki describing the expansion of k-Schur functions of ``near […]

Riffle shuffles with biased cuts

Assaf, Sami ; Diaconis, Persi ; Soundararajan, Kannan.
The well-known Gilbert-Shannon-Reeds model for riffle shuffles assumes that the cards are initially cut `about in half' and then riffled together. We analyze a natural variant where the initial cut is biased. Extending results of Fulman (1998), we show a sharp cutoff in separation and L-infinity […]

The sandpile model, polyominoes, and a $q,t$-Narayana polynomial

Dukes, Mark ; Le Borgne, Yvan.
We give a polyomino characterisation of recurrent configurations of the sandpile model on the complete bipartite graph $K_{m,n}$ in which one designated vertex is the sink. We present a bijection from these recurrent configurations to decorated parallelogram polyominoes whose bounding box is a $m×n$ […]

The Euclid Algorithm is totally gaussian

Vallée, Brigitte.
We consider Euclid’s gcd algorithm for two integers $(p, q)$ with $1 \leq p \leq q \leq N$, with the uniform distribution on input pairs. We study the distribution of the total cost of execution of the algorithm for an additive cost function $d$ on the set of possible digits, asymptotically for $N […]

Joint String Complexity for Markov Sources

Jacquet, Philippe ; Szpankowski, Wojciech.
String complexity is defined as the cardinality of a set of all distinct words (factors) of a given string. For two strings, we define $\textit{joint string complexity}$ as the set of words that are common to both strings. We also relax this definition and introduce $\textit{joint semi-complexity}$ […]

Locally Restricted Compositions IV. Nearly Free Large Parts and Gap-Freeness

Bender, Edward,  ; Canfield, Rodney,  ; Gao, Zhicheng.
We define the notion of $t$-free for locally restricted compositions, which means roughly that if such a composition contains a part $c_i$ and nearby parts are at least $t$ smaller, then $c_i$ can be replaced by any larger part. Two well-known examples are Carlitz and alternating compositions. We […]

Cumulants of the q-semicircular law, Tutte polynomials, and heaps

Josuat-Vergès, Matthieu.
The q-semicircular law as introduced by Bożejko and Speicher interpolates between the Gaussian law and the semicircular law, and its moments have a combinatorial interpretation in terms of matchings and crossings. We prove that the cumulants of this law are, up to some factor, polynomials in q with […]

The representation of the symmetric group on $m$-Tamari intervals (conference version)

Bousquet-Mélou, Mireille ; Chapuy, Guillaume ; Préville-Ratelle, Louis-François.
An $m$-ballot path of size $n$ is a path on the square grid consisting of north and east unit steps, starting at (0,0), ending at $(mn,n)$, and never going below the line $\{x=my\}$. The set of these paths can be equipped with a lattice structure, called the $m$-Tamari lattice and denoted by […]

Bases for modules of differential operators

Nakashima, Norihiro.
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 […]

Generating trees for partitions and permutations with no k-nestings

Burrill, Sophie ; Elizalde, Sergi ; Mishna, Marni ; Yen, Lily.
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 […]

On singularity confinement for the pentagram map

Glick, Max.
The pentagram map, introduced by R. Schwartz, is a birational map on the configuration space of polygons in the projective plane. We study the singularities of the iterates of the pentagram map. We show that a ``typical'' singularity disappears after a finite number of iterations, a confinement […]

A phase transition in the distribution of the length of integer partitions

Ralaivaosaona, Dimbinaina.
We assign a uniform probability to the set consisting of partitions of a positive integer $n$ such that the multiplicity of each summand is less than a given number $d$ and we study the limiting distribution of the number of summands in a random partition. It is known from a result by Erdős and […]

Arc Permutations (extended abstract)

Elizalde, Sergi ; Roichman, Yuval.
Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. In this paper we describe combinatorial properties of these permutations, including characterizations in terms of pattern avoidance, connections to Young tableaux, and an affine Weyl group […]

Promotion and Rowmotion

Striker, Jessica ; Williams, Nathan.
We present an equivariant bijection between two actions—promotion and rowmotion—on order ideals in certain posets. This bijection simultaneously generalizes a result of R. Stanley concerning promotion on the linear extensions of two disjoint chains and certain cases of recent work of D. Armstrong, […]

Support and density of the limit $m$-ary search trees distribution

Chauvin, Brigitte ; Liu, Quansheng ; Pouyanne, Nicolas.
The space requirements of an $m$-ary search tree satisfies a well-known phase transition: when $m\leq 26$, the second order asymptotics is Gaussian. When $m\geq 27$, it is not Gaussian any longer and a limit $W$ of a complex-valued martingale arises. We show that the distribution of $W$ has a square […]

The weighted words collector

Du Boisberranger, Jérémie ; Gardy, Danièle ; Ponty, Yann.
We consider the word collector problem, i.e. the expected number of calls to a random weighted generator before all the words of a given length in a language are generated. The originality of this instance of the non-uniform coupon collector lies in the, potentially large, multiplicity of the […]

Simply generated trees, conditioned Galton―Watson trees, random allocations and condensation: Extended abstract

Janson, Svante.
We give a unified treatment of the limit, as the size tends to infinity, of random simply generated trees, including both the well-known result in the standard case of critical Galton-Watson trees and similar but less well-known results in the other cases (i.e., when no equivalent critical […]

Infinite Systems of Functional Equations and Gaussian Limiting Distributions

Drmota, Michael ; Gittenberger, Bernhard ; Morgenbesser, Johannes F..
In this paper infinite systems of functional equations in finitely or infinitely many random variables arising in combinatorial enumeration problems are studied. We prove sufficient conditions under which the combinatorial random variables encoded in the generating function of the system tend to a […]

Smooth Fano polytopes whose Ehrhart polynomial has a root with large real part

Ohsugi, Hidefumi ; Shibata, Kazuki.
The symmetric edge polytopes of odd cycles (del Pezzo polytopes) are known as smooth Fano polytopes. In this extended abstract, we show that if the length of the cycle is 127, then the Ehrhart polynomial has a root whose real part is greater than the dimension. As a result, we have a smooth Fano […]

Consecutive patterns in permutations: clusters and generating functions

Elizalde, Sergi ; Noy, Marc.
We use the cluster method in order to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new ones, including some patterns of length 4 and 5, as well as some infinite families of patterns of a given shape. Our main tool […]

Arithmetic matroids and Tutte polynomials

D'Adderio, Michele ; Moci, Luca.
We introduce the notion of arithmetic matroid, whose main example is provided by a list of elements in a finitely generated abelian group. We study the representability of its dual, and, guided by the geometry of toric arrangements, we give a combinatorial interpretation of the associated arithmetic […]

Constructing combinatorial operads from monoids

Giraudo, Samuele.
We introduce a functorial construction which, from a monoid, produces a set-operad. We obtain new (symmetric or not) operads as suboperads or quotients of the operad obtained from the additive monoid. These involve various familiar combinatorial objects: parking functions, packed words, planar […]

Fluctuations of central measures on partitions

Mèliot, Pierre-Loïc.
We study the fluctuations of models of random partitions $(\mathbb{P}_n,ω )_n ∈\mathbb{N}$ stemming from the representation theory of the infinite symmetric group. Using the theory of polynomial functions on Young diagrams, we establish a central limit theorem for the values of the irreducible […]

Enumeration of minimal 3D polyominoes inscribed in a rectangular prism

Goupil, Alain ; Cloutier, Hugo.
We consider the family of 3D minimal polyominoes inscribed in a rectanglar prism. These objects are polyominos and so they are connected sets of unitary cubic cells inscribed in a given rectangular prism of size $b\times k \times h$ and of minimal volume equal to $b+k+h-2$. They extend the concept […]

Combinatorics of k-shapes and Genocchi numbers

Hivert, Florent ; Mallet, Olivier.
In this paper we present a work in progress on a conjectural new combinatorial model for the Genocchi numbers. This new model called irreducible k-shapes has a strong algebraic background in the theory of symmetric functions and leads to seemingly new features on the theory of Genocchi numbers. In […]

The short toric polynomial

Hetyei, Gábor.
We introduce the short toric polynomial associated to a graded Eulerian poset. This polynomial contains the same information as Stanley's pair of toric polynomials, but allows different algebraic manipulations. Stanley's intertwined recurrence may be replaced by a single recurrence, in which the […]

0-Hecke algebra actions on coinvariants and flags

Huang, Jia.
By investigating the action of the 0-Hecke algebra on the coinvariant algebra and the complete flag variety, we interpret generating functions counting the permutations with fixed inverse descent set by their inversion number and major index.

The Incidence Hopf Algebra of Graphs

Humpert, Brandon ; Martin, Jeremy L..
The graph algebra is a commutative, cocommutative, graded, connected incidence Hopf algebra, whose basis elements correspond to finite simple graphs and whose Hopf product and coproduct admit simple combinatorial descriptions. We give a new formula for the antipode in the graph algebra in terms of […]

Isotropical Linear Spaces and Valuated Delta-Matroids

Rincón, Felipe.
The spinor variety is cut out by the quadratic Wick relations among the principal Pfaffians of an $n \times n$ skew-symmetric matrix. Its points correspond to $n$-dimensional isotropic subspaces of a $2n$-dimensional vector space. In this paper we tropicalize this picture, and we develop a […]

A reciprocity approach to computing generating functions for permutations with no pattern matches

Jones, Miles Eli ; Remmel, Jeffrey.
In this paper, we develop a new method to compute generating functions of the form $NM_τ (t,x,y) = \sum\limits_{n ≥0} {\frac{t^n} {n!}}∑_{σ ∈\mathcal{lNM_{n}(τ )}} x^{LRMin(σ)} y^{1+des(σ )}$ where $τ$ is a permutation that starts with $1, \mathcal{NM_n}(τ )$ is the set of permutations in the […]

Counting self-dual interval orders

Jelínek, Vít.
In this paper, we first derive an explicit formula for the generating function that counts unlabeled interval orders (a.k.a. (2+2)-free posets) with respect to several natural statistics, including their size, magnitude, and the number of minimal and maximal elements. In the second part of the […]

The enumeration of fully commutative affine permutations

Hanusa, Christopher R. H. ; Jones, Brant C..
We give a generating function for the fully commutative affine permutations enumerated by rank and Coxeter length, extending formulas due to Stembridge and Barcucci–Del Lungo–Pergola–Pinzani. For fixed rank, the length generating functions have coefficients that are periodic with period dividing the […]

A polynomial expression for the Hilbert series of the quotient ring of diagonal coinvariants (condensed version)

Haglund, J..
A special case of Haiman's identity [Invent. Math. 149 (2002), pp. 371–407] for the character of the quotient ring of diagonal coinvariants under the diagonal action of the symmetric group yields a formula for the bigraded Hilbert series as a sum of rational functions in $q,t$. In this paper we show […]

Cyclic sieving phenomenon in non-crossing connected graphs

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

Bumping algorithm for set-valued shifted tableaux

Ikeda, Takeshi ; Naruse, Hiroshi ; Numata, Yasuhide.
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 […]

Stable rigged configurations and Littlewood―Richardson tableaux

Okado, Masato ; Sakamoto, Reiho.
For an affine algebra of nonexceptional type in the large rank we show the fermionic formula depends only on the attachment of the node 0 of the Dynkin diagram to the rest, and the fermionic formula of not type $A$ can be expressed as a sum of that of type $A$ with Littlewood–Richardson […]

Tableaux and plane partitions of truncated shapes (extended abstract)

Panova, Greta.
We consider a new kind of straight and shifted plane partitions/Young tableaux — ones whose diagrams are no longer of partition shape, but rather Young diagrams with boxes erased from their upper right ends. We find formulas for the number of standard tableaux in certain cases, namely a shifted […]

How often do we reject a superior value? (Extended abstract)

Oliver, Kamilla ; Prodinger, Helmut.
Words $a_1 a_2 \ldots a_n$ with independent letters $a_k$ taken from the set of natural numbers, and a weight (probability) attached via the geometric distribution $pq^{i-1}(p+q=1)$ are considered. A consecutive record (motivated by the analysis of a skip list structure) can only advance from $k$ to […]

Triangulations of $\Delta_{n-1} \times \Delta_{d-1}$ and Tropical Oriented Matroids

Oh, Suho ; Yoo, Hwanchul.
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 […]

Bijective evaluation of the connection coefficients of the double coset algebra

Morales, Alejandro H. ; Vassilieva, Ekaterina A..
This paper is devoted to the evaluation of the generating series of the connection coefficients of the double cosets of the hyperoctahedral group. Hanlon, Stanley, Stembridge (1992) showed that this series, indexed by a partition $ν$, gives the spectral distribution of some random matrices that are […]

Generalized permutohedra, h-vectors of cotransversal matroids and pure O-sequences (extended abstract)

Oh, Suho.
Stanley has conjectured that the h-vector of a matroid complex is a pure O-sequence. We will prove this for cotransversal matroids by using generalized permutohedra. We construct a bijection between lattice points inside a $r$-dimensional convex polytope and bases of a rank $r$ transversal matroid.

A topological interpretation of the cyclotomic polynomial

Musiker, Gregg ; Reiner, Victor.
We interpret the coefficients of the cyclotomic polynomial in terms of simplicial homology.

Kerov's central limit theorem for Schur-Weyl and Gelfand measures (extended abstract)

Méliot, Pierre-Loïc.
We show that the shapes of integer partitions chosen randomly according to Schur-Weyl measures of parameter $\alpha =1/2$ and Gelfand measures satisfy Kerov's central limit theorem. Thus, there is a gaussian process $\Delta$ such that under Plancherel, Schur-Weyl or Gelfand measures, the deviations […]

Row-strict quasisymmetric Schur functions

Mason, Sarah K ; Remmel, Jeffrey.
Haglund, Luoto, Mason, and van Willigenburg introduced a basis for quasisymmetric functions called the $\textit{quasisymmetric Schur function basis}$ which are generated combinatorially through fillings of composition diagrams in much the same way as Schur functions are generated through reverse […]

Matrices with restricted entries and q-analogues of permutations (extended abstract)

Lewis, Joel Brewster ; Liu, Ricky Ini ; Morales, Alejandro H. ; Panova, Greta ; Sam, Steven V ; Zhang, Yan.
We study the functions that count matrices of given rank over a finite field with specified positions equal to zero. We show that these matrices are $q$-analogues of permutations with certain restricted values. We obtain a simple closed formula for the number of invertible matrices with zero […]

Special Cases of the Parking Functions Conjecture and Upper-Triangular Matrices

Levande, Paul.
We examine the $q=1$ and $t=0$ special cases of the parking functions conjecture. The parking functions conjecture states that the Hilbert series for the space of diagonal harmonics is equal to the bivariate generating function of $area$ and $dinv$ over the set of parking functions. Haglund recently […]

The pentagram map and Y-patterns

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

Algebraic and combinatorial structures on Baxter permutations

Giraudo, Samuele.
We give a new construction of a Hopf subalgebra of the Hopf algebra of Free quasi-symmetric functions whose bases are indexed by objects belonging to the Baxter combinatorial family (\emphi.e. Baxter permutations, pairs of twin binary trees, \emphetc.). This construction relies on the definition of […]

Adjacent transformations in permutations

Pierrot, Adeline ; Rossin, Dominique ; West, Julian.
We continue a study of the equivalence class induced on $S_n$ when one is permitted to replace a consecutive set of elements in a permutation with the same elements in a different order. For each possible set of allowed replacements, we characterise and/or enumerate the set of permutations reachable […]

The brick polytope of a sorting network

Pilaud, Vincent ; Santos, Francisco.
The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud and Pocchiola in their study of pseudoline arrangements with […]

Hierarchical Zonotopal Power Ideals

Lenz, Matthias.
Zonotopal algebra deals with ideals and vector spaces of polynomials that are related to several combinatorial and geometric structures defined by a finite sequence of vectors. Given such a sequence $X$, an integer $k \geq -1$ and an upper set in the lattice of flats of the matroid defined by $X$, […]

Minkowski decompositions of associahedra

Lange, Carsten.
Realisations of associahedra can be obtained from the classical permutahedron by removing some of its facets and the set of facets is determined by the diagonals of certain labeled convex planar $n$-gons as shown by Hohlweg and Lange (2007). Ardila, Benedetti, and Doker (2010) expressed polytopes of […]

Closed paths whose steps are roots of unity

Labelle, Gilbert ; Lacasse, Annie.
We give explicit formulas for the number $U_n(N)$ of closed polygonal paths of length $N$ (starting from the origin) whose steps are $n^{\textrm{th}}$ roots of unity, as well as asymptotic expressions for these numbers when $N \rightarrow \infty$. We also prove that the sequences $(U_n(N))_{N \geq […]

Counting Shi regions with a fixed separating wall

Fishel, Susanna ; Tzanaki, Eleni ; Vazirani, Monica.
Athanasiadis introduced separating walls for a region in the extended Shi arrangement and used them to generalize the Narayana numbers. In this paper, we fix a hyperplane in the extended Shi arrangement for type A and calculate the number of dominant regions which have the fixed hyperplane as a […]

K-classes for matroids and equivariant localization

Fink, Alex ; Speyer, David.
To every matroid, we associate a class in the K-theory of the Grassmannian. We study this class using the method of equivariant localization. In particular, we provide a geometric interpretation of the Tutte polynomial. We also extend results of the second author concerning the behavior of such […]

Dissimilarity Vectors of Trees and Their Tropical Linear Spaces (Extended Abstract)

Iriarte Giraldo, Benjamin.
We study the combinatorics of weighted trees from the point of view of tropical algebraic geometry and tropical linear spaces. The set of dissimilarity vectors of weighted trees is contained in the tropical Grassmannian, so we describe here the tropical linear space of a dissimilarity vector and its […]

Cofree compositions of coalgebras

Forcey, Stefan ; Lauve, Aaron ; Sottile, Frank.
We develop the notion of the composition of two coalgebras, which arises naturally in higher category theory and the theory of species. We prove that the composition of two cofree coalgebras is cofree and give conditions which imply that the composition is a one-sided Hopf algebra. These conditions […]

Touchard-Riordan formulas, T-fractions, and Jacobi's triple product identity

Josuat-Vergès, Matthieu ; Kim, Jang-Soo.
We give a combinatorial proof of a Touchard-Riordan-like formula discovered by the first author. As a consequence we find a connection between his formula and Jacobi's triple product identity. We then give a combinatorial analog of Jacobi's triple product identity by showing that a finite sum can be […]

On the evaluation of the Tutte polynomial at the points (1,-1) and (2,-1)

Goodall, Andrew ; Merino, Criel ; de Mier, Anna ; Noy, Marc.
C. Merino [Electron. J. Combin. 15 (2008)] showed that the Tutte polynomial of a complete graph satisfies $t(K_{n+2};2,-1)=t(K_n;1,-1)$. We first give a bijective proof of this identity based on the relationship between the Tutte polynomial and the inversion polynomial for trees. Next we move to our […]

Skew quantum Murnaghan-Nakayama rule

Konvalinka, Matjaž.
In this extended abstract, we extend recent results of Assaf and McNamara, the skew Pieri rule and the skew Murnaghan-Nakayama rule, to a more general identity, which gives an elegant expansion of the product of a skew Schur function with a quantum power sum function in terms of skew Schur […]

Double homotopy Cohen-Macaulayness for the poset of injective words and the classical NC-partition lattice

Kallipoliti, Myrto ; Kubitzke, Martina.
In this paper we study topological properties of the poset of injective words and the lattice of classical non-crossing partitions. Specifically, it is shown that after the removal of the bottom and top elements (if existent) these posets are doubly Cohen-Macaulay. This extends the well-known result […]

Cyclic sieving for two families of non-crossing graphs

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

Meander Graphs

Heitsch, Christine E. ; Tetali, Prasad.
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 […]

Critical Groups of Simplicial Complexes

Duval, Art M. ; Klivans, Caroline J. ; Martin, Jeremy L..
We generalize the theory of critical groups from graphs to simplicial complexes. Specifically, given a simplicial complex, we define a family of abelian groups in terms of combinatorial Laplacian operators, generalizing the construction of the critical group of a graph. We show how to realize these […]

The Murnaghan―Nakayama rule for k-Schur functions

Bandlow, Jason ; Schilling, Anne ; Zabrocki, Mike.
We prove a Murnaghan–Nakayama rule for k-Schur functions of Lapointe and Morse. That is, we give an explicit formula for the expansion of the product of a power sum symmetric function and a k-Schur function in terms of k-Schur functions. This is proved using the noncommutative k-Schur functions in […]

On the enumeration of column-convex permutominoes

Beaton, Nicholas R. ; Disanto, Filippo ; Guttmann, Anthony J. ; Rinaldi, Simone.
We study the enumeration of \emphcolumn-convex permutominoes, i.e. column-convex polyominoes defined by a pair of permutations. We provide a direct recursive construction for the column-convex permutominoes of a given size, based on the application of the ECO method and generating trees, which leads […]

Submaximal factorizations of a Coxeter element in complex reflection groups

Ripoll, Vivien.
When $W$ is a finite reflection group, the noncrossing partition lattice $NC(W)$ of type $W$ is a very rich combinatorial object, extending the notion of noncrossing partitions of an $n$-gon. A formula (for which the only known proofs are case-by-case) expresses the number of multichains of a given […]

A Littlewood-Richardson type rule for row-strict quasisymmetric Schur functions

Ferreira, Jeffrey.
We establish several properties of an algorithm defined by Mason and Remmel (2010) which inserts a positive integer into a row-strict composition tableau. These properties lead to a Littlewood-Richardson type rule for expanding the product of a row-strict quasisymmetric Schur function and a […]

Deformed diagonal harmonic polynomials for complex reflection groups

Bergeron, François ; Borie, Nicolas ; Thiéry, Nicolas M..
We introduce deformations of the space of (multi-diagonal) harmonic polynomials for any finite complex reflection group of the form W=G(m,p,n), and give supporting evidence that this space seems to always be isomorphic, as a graded W-module, to the undeformed version.

Enumerating projective reflection groups

Biagioli, Riccardo ; Caselli, Fabrizio.
Projective reflection groups have been recently defined by the second author. They include a special class of groups denoted G(r,p,s,n) which contains all classical Weyl groups and more generally all the complex reflection groups of type G(r,p,n). In this paper we define some statistics analogous to […]

Finite Eulerian posets which are binomial or Sheffer

Bidkhori, Hoda.
In this paper we study finite Eulerian posets which are binomial or Sheffer. These important classes of posets are related to the theory of generating functions and to geometry. The results of this paper are organized as follows: (1) We completely determine the structure of Eulerian binomial posets […]

Rational smoothness and affine Schubert varieties of type A

Billey, Sara ; Crites, Andrew.
The study of Schubert varieties in G/B has led to numerous advances in algebraic combinatorics and algebraic geometry. These varieties are indexed by elements of the corresponding Weyl group, an affine Weyl group, or one of their parabolic quotients. Often times, the goal is to determine which of […]

A tight colored Tverberg theorem for maps to manifolds (extended abstract)

Blagojević, Pavle V. M. ; Matschke, Benjamin ; Ziegler, Günter M..
Any continuous map of an $N$-dimensional simplex $Δ _N$ with colored vertices to a $d$-dimensional manifold $M$ must map $r$ points from disjoint rainbow faces of $Δ _N$ to the same point in $M$, assuming that $N≥(r-1)(d+1)$, no $r$ vertices of $Δ _N$ get the same color, and our proof needs that $r$ […]

Shortest path poset of Bruhat intervals

Blanco, Saúl A..
Let $[u,v]$ be a Bruhat interval and $B(u,v)$ be its corresponding Bruhat graph. The combinatorial and topological structure of the longest $u-v$ paths of $B(u,v)$ has been extensively studied and is well-known. Nevertheless, not much is known of the remaining paths. Here we describe combinatorial […]

Relative Node Polynomials for Plane Curves

Block, Florian.
We generalize the recent work of Fomin and Mikhalkin on polynomial formulas for Severi degrees. The degree of the Severi variety of plane curves of degree d and δ nodes is given by a polynomial in d, provided δ is fixed and d is large enough. We extend this result to generalized Severi varieties […]

The # product in combinatorial Hopf algebras

Aval, Jean-Christophe ; Novelli, Jean-Christophe ; Thibon, Jean-Yves.
We show that the # product of binary trees introduced by Aval and Viennot (2008) is in fact defined at the level of the free associative algebra, and can be extended to most of the classical combinatorial Hopf algebras.

Lagrange's Theorem for Hopf Monoids in Species

Aguiar, Marcelo ; Lauve, Aaron.
We prove Lagrange's theorem for Hopf monoids in the category of connected species. We deduce necessary conditions for a given subspecies $\textrm{k}$ of a Hopf monoid $\textrm{h}$ to be a Hopf submonoid: each of the generating series of $\textrm{k}$ must divide the corresponding generating series of […]

Primitive orthogonal idempotents for R-trivial monoids

Berg, Chris ; Bergeron, Nantel ; Bhargava, Sandeep ; Saliola, Franco.
We construct a recursive formula for a complete system of primitive orthogonal idempotents for any R-trivial monoid. This uses the newly proved equivalence between the notions of R-trivial monoid and weakly ordered monoid.

Polytopes from Subgraph Statistics

Engström, Alexander ; Norén, Patrik.
We study polytopes that are convex hulls of vectors of subgraph densities. Many graph theoretical questions can be expressed in terms of these polytopes, and statisticians use them to understand exponential random graph models. Relations among their Ehrhart polynomials are described, their duals are […]

Polynomial functions on Young diagrams arising from bipartite graphs

Dolęga, Maciej ; Sniady, Piotr.
We study the class of functions on the set of (generalized) Young diagrams arising as the number of embeddings of bipartite graphs. We give a criterion for checking when such a function is a polynomial function on Young diagrams (in the sense of Kerov and Olshanski) in terms of combinatorial […]

Statistics on staircase tableaux, eulerian and mahonian statistics

Corteel, Sylvie ; Dasse-Hartaut, Sandrine.
We give a simple bijection between some staircase tableaux and tables of inversion. Some nice properties of the bijection allows us to define some q-Eulerian polynomials related to the staircase tableaux. We also give a combinatorial interpretation of these q-Eulerian polynomials in terms of […]

Dual combinatorics of zonal polynomials

Féray, Valentin ; Sniady, Piotr.
In this paper we establish a new combinatorial formula for zonal polynomials in terms of power-sums. The proof relies on the sign-reversing involution principle. We deduce from it formulas for zonal characters, which are defined as suitably normalized coefficients in the expansion of zonal […]

Path tableaux and combinatorial interpretations of immanants for class functions on $S_n$

Clearman, Sam ; Shelton, Brittany ; Skandera, Mark.
Let $χ ^λ$ be the irreducible $S_n$-character corresponding to the partition $λ$ of $n$, equivalently, the preimage of the Schur function $s_λ$ under the Frobenius characteristic map. Let $\phi ^λ$ be the function $S_n →ℂ$ which is the preimage of the monomial symmetric function $m_λ$ under the […]

Partition and composition matrices: two matrix analogues of set partitions

Claesson, Anders ; Dukes, Mark ; Kubitzke, Martina.
This paper introduces two matrix analogues for set partitions; partition and composition matrices. These two analogues are the natural result of lifting the mapping between ascent sequences and integer matrices given in Dukes & Parviainen (2010). We prove that partition matrices are in one-to-one […]

Arc Spaces and Rogers-Ramanujan Identities

Bruschek, Clemens ; Mourtada, Hussein ; Schepers, Jan.
Arc spaces have been introduced in algebraic geometry as a tool to study singularities but they show strong connections with combinatorics as well. Exploiting these relations we obtain a new approach to the classical Rogers-Ramanujan Identities. The linking object is the Hilbert-Poincaré series of […]

The Shi arrangement and the Ish arrangement

Armstrong, Drew ; Rhoades, Brendon.
This paper is about two arrangements of hyperplanes. The first — the Shi arrangement — was introduced by Jian-Yi Shi to describe the Kazhdan-Lusztig cells in the affine Weyl group of type A. The second — the Ish arrangement — was recently defined by the first author who used the two arrangements […]

Hyperplane Arrangements and Diagonal Harmonics

Armstrong, Drew.
In 2003, Haglund's bounce statistic gave the first combinatorial interpretation of the q,t-Catalan numbers and the Hilbert series of diagonal harmonics. In this paper we propose a new combinatorial interpretation in terms of the affine Weyl group of type A. In particular, we define two statistics on […]

Gelfand―Tsetlin Polytopes and Feigin―Fourier―Littelmann―Vinberg Polytopes as Marked Poset Polytopes

Ardila, Federico ; Bliem, Thomas ; Salazar, Dido.
Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P […]

Allowed patterns of β -shifts

Elizalde, Sergi.
For a real number $β >1$, we say that a permutation $π$ of length $n$ is allowed (or realized) by the $β$-shift if there is some $x∈[0,1]$ such that the relative order of the sequence $x,f(x),\ldots,f^n-1(x)$, where $f(x)$ is the fractional part of $βx$, is the same as that of the entries of $π$ . […]

Powers of the Vandermonde determinant, Schur functions, and the dimension game

Ballantine, Cristina.
Since every even power of the Vandermonde determinant is a symmetric polynomial, we want to understand its decomposition in terms of the basis of Schur functions. We investigate several combinatorial properties of the coefficients in the decomposition. In particular, I will give a recursive approach […]

The topology of restricted partition posets

Ehrenborg, Richard ; Jung, JiYoon.
For each composition $\vec{c}$ we show that the order complex of the poset of pointed set partitions $Π ^• _{\vec{c}}$ is a wedge of $β\vec{c}$ spheres of the same dimensions, where $β\vec{c}$ is the number of permutations with descent composition ^$\vec{c}$. Furthermore, the action of the symmetric […]

Tree-like tableaux

Aval, Jean-Christophe ; Boussicault, Adrien ; Nadeau, Philippe.
In this work we introduce and study tree-like tableaux, which are certain fillings of Ferrers diagrams in simple bijection with permutation tableaux and alternative tableaux. We exhibit an elementary insertion procedure on our tableaux which gives a clear proof that tableaux of size n are counted by […]

Asymptotics of several-partition Hurwitz numbers

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

Generalized triangulations, pipe dreams, and simplicial spheres

Serrano, Luis ; Stump, Christian.
We exhibit a canonical connection between maximal $(0,1)$-fillings of a moon polyomino avoiding north-east chains of a given length and reduced pipe dreams of a certain permutation. Following this approach we show that the simplicial complex of such maximal fillings is a vertex-decomposable and thus […]

A $q$-analog of Ljunggren's binomial congruence

Straub, Armin.
We prove a $q$-analog of a classical binomial congruence due to Ljunggren which states that $\binom{ap}{bp} \equiv \binom{a}{b}$ modulo $p^3$ for primes $p \geq 5$. This congruence subsumes and builds on earlier congruences by Babbage, Wolstenholme and Glaisher for which we recall existing […]

Supercharacters, symmetric functions in noncommuting variables (extended abstract)

Aguiar, Marcelo ; André, Carlos ; Benedetti, Carolina ; Bergeron, Nantel ; Chen, Zhi ; Diaconis, Persi ; Hendrickson, Anders ; Hsiao, Samuel ; Isaacs, I. Martin ; Jedwab, Andrea et al.
We identify two seemingly disparate structures: supercharacters, a useful way of doing Fourier analysis on the group of unipotent uppertriangular matrices with coefficients in a finite field, and the ring of symmetric functions in noncommuting variables. Each is a Hopf algebra and the two are […]

The equivariant topology of stable Kneser graphs

Schultz, Carsten.
Schrijver introduced the stable Kneser graph $SG_{n,k}, n \geq 1, k \geq 0$. This graph is a vertex critical graph with chromatic number $k+2$, its vertices are certain subsets of a set of cardinality $m=2n+k$. Björner and de Longueville have shown that its box complex is homotopy equivalent to a […]

Philippe Flajolet, the Father of Analytic Combinatorics

Salvy, Bruno ; Sedgewick, Bob ; Soria, Michèle ; Szpankowski, Wojtek ; Vallée, Brigitte.
Philippe Flajolet, mathematician and computer scientist extraordinaire, suddenly passed away on March 22, 2011, at the prime of his career. He is celebrated for opening new lines of research in analysis of algo- rithms, developing powerful new methods, and solving difficult open problems. His […]

Bifurcations in Boolean Networks

Kuhlman, Chris,  ; Mortveit, Henning,  ; Murrugarra, David ; Kumar, Anil, .
This paper characterizes the attractor structure of synchronous and asynchronous Boolean networks induced by bi-threshold functions. Bi-threshold functions are generalizations of standard threshold functions and have separate threshold values for the transitions $0 \rightarrow $1 (up-threshold) and […]

Demazure crystals and the energy function

Schilling, Anne ; Tingley, Peter.
There is a close connection between Demazure crystals and tensor products of Kirillov–Reshetikhin crystals. For example, certain Demazure crystals are isomorphic as classical crystals to tensor products of Kirillov–Reshetikhin crystals via a canonically chosen isomorphism. Here we show that this […]

Representations on Hessenberg Varieties and Young's Rule

Teff, Nicholas.
We combinatorially construct the complex cohomology (equivariant and ordinary) of a family of algebraic varieties called regular semisimple Hessenberg varieties. This construction is purely in terms of the Bruhat order on the symmetric group. From this a representation of the symmetric group on the […]

Noncommutative Symmetric Hall-Littlewood Polynomials

Tevlin, Lenny.
Noncommutative symmetric functions have many properties analogous to those of classical (commutative) symmetric functions. For instance, ribbon Schur functions (analogs of the classical Schur basis) expand positively in noncommutative monomial basis. More of the classical properties extend to […]

Maximal 0-1-fillings of moon polyominoes with restricted chain lengths and rc-graphs

Rubey, Martin.
We show that maximal 0-1-fillings of moon polynomials, with restricted chain lengths, can be identified with certain rc-graphs, also known as pipe dreams. In particular, this exhibits a connection between maximal 0-1-fillings of Ferrers shapes and Schubert polynomials. Moreover, it entails a […]

Local extrema in random permutations and the structure of longest alternating subsequences

Romik, Dan.
Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and […]

On the monotone hook hafnian conjecture

Visontai, Mirkó.
We investigate a conjecture of Haglund that asserts that certain graph polynomials have only real roots. We prove a multivariate generalization of this conjecture for the special case of threshold graphs.

Projective subdynamics and universal shifts

Guillon, Pierre.
We study the projective subdynamics of two-dimensional shifts of finite type, which is the set of one-dimensional configurations that appear as columns in them. We prove that a large class of one-dimensional shifts can be obtained as such, namely the effective subshifts which contain […]

Conservation Laws and Invariant Measures in Surjective Cellular Automata

Kari, Jarkko ; Taati, Siamak.
We discuss a close link between two seemingly different topics studied in the cellular automata literature: additive conservation laws and invariant probability measures. We provide an elementary proof of a simple correspondence between invariant full-support Bernoulli measures and interaction-free […]

Product decomposition for surjective 2-block NCCA

García-Ramos, Felipe.
In this paper we define products of one-dimensional Number Conserving Cellular Automata (NCCA) and show that surjective NCCA with 2 blocks (i.e radius 1/2) can always be represented as products of shifts and identites. In particular, this shows that surjective 2-block NCCA are injective.

NOCAS : A Nonlinear Cellular Automata Based Stream Cipher

Karmakar, Sandip ; Chowdhury, Dipanwita Roy.
LFSR and NFSR are the basic building blocks in almost all the state of the art stream ciphers like Trivium and Grain-128. However, a number of attacks are mounted on these type of ciphers. Cellular Automata (CA) has recently been chosen as a suitable structure for crypto-primitives. In this work, a […]

The structure of communication problems in cellular automata

Briceño, Raimundo ; Meunier, Pierre-Etienne.
Studying cellular automata with methods from communication complexity appears to be a promising approach. In the past, interesting connections between communication complexity and intrinsic universality in cellular automata were shown. One of the last extensions of this theory was its generalization […]

A fixed point theorem for Boolean networks expressed in terms of forbidden subnetworks

Richard, Adrien.
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 […]

Selfsimilarity, Simulation and Spacetime Symmetries

Nesme, Vincent ; Theyssier, Guillaume.
We study intrinsic simulations between cellular automata and introduce a new necessary condition for a CA to simulate another one. Although expressed for general CA, this condition is targeted towards surjective CA and especially linear ones. Following the approach introduced by the first author in […]

Asymptotic distribution of entry times in a cellular automaton with annihilating particles

Kůrka, Petr ; Formenti, Enrico ; Dennunzio, Alberto.
This work considers a cellular automaton (CA) with two particles: a stationary particle $1$ and left-going one $øverline{1}$. When a $øverline{1}$ encounters a $1$, both particles annihilate. We derive asymptotic distribution of appearence of particles at a given site when the CA is initialized with […]

On the set of Fixed Points of the Parallel Symmetric Sand Pile Model

Perrot, Kévin ; Phan, Thi Ha Duong ; Pham, Trung Van.
Sand Pile Models are discrete dynamical systems emphasizing the phenomenon of $\textit{Self-Organized Criticality}$. From a configuration composed of a finite number of stacked grains, we apply on every possible positions (in parallel) two grain moving transition rules. The transition rules permit […]

Orbits of the Bernoulli measure in single-transition asynchronous cellular automata

Fukś, Henryk ; Skelton, Andrew.
We study iterations of the Bernoulli measure under nearest-neighbour asynchronous binary cellular automata (CA) with a single transition. For these CA, we show that a coarse-level description of the orbit of the Bernoulli measure can be obtained, that is, one can explicitly compute measures of short […]

Block-sequential update schedules and Boolean automata circuits

Goles, Eric ; Noual, Mathilde.
Our work is set in the framework of complex dynamical systems and, more precisely, that of Boolean automata networks modeling regulation networks. We study how the choice of an update schedule impacts on the dynamics of such a network. To do this, we explain how studying the dynamics of any network […]

The Size of One-Way Cellular Automata

Kutrib, Martin ; Lefèvre, Jonas ; Malcher, Andreas.
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 […]

60/102 Null Boundary Cellular Automata based expander graphs

Cho, Sung-Jin ; Choi, Un-Sook ; Kim, Han-Doo ; Hwang, Yoon-Hee ; Kim, Jin-Gyoung.
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 […]

The fractal structure of cellular automata on abelian groups

Gütschow, Johannes ; Nesme, Vincent ; Werner, Reinhard F..
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 […]

A weakly universal cellular automaton in the hyperbolic $3D$ space with three states

Margenstern, Maurice.
In this paper, we significantly improve a previous result by the same author showing the existence of a weakly universal cellular automaton with five states living in the hyperbolic $3D$-space. Here, we get such a cellular automaton with three states only.

On the complexity of enumerating possible dynamics of sparsely connected Boolean network automata with simple update rules

Tošić, Predrag T..
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 […]

Probabilistic initial value problem for cellular automaton rule 172

Fuks, Henryk.
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 […]

Faster Methods for Identifying Nontrivial Energy Conservation Functions for Cellular Automata

Baird, Leemon ; Fagin, Barry.
The biggest obstacle to the efficient discovery of conserved energy functions for cellular auotmata is the elimination of the trivial functions from the solution space. Once this is accomplished, the identification of nontrivial conserved functions can be accomplished computationally through […]

Minimal Recurrent Configurations of Chip Firing Games and Directed Acyclic Graphs

Schulz, Matthias.
We discuss a very close relation between minimal recurrent configurations of Chip Firing Games and Directed Acyclic Graphs and demonstrate the usefulness of this relation by giving a lower bound for the number of minimal recurrent configurations of the Abelian Sandpile Model as well as a lower bound […]

Phase transitions in Proof Theory

Gordeev, Lev ; Weiermann, Andreas.
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.

Nonzero coefficients in restrictions and tensor products of supercharacters of $U_n(q)$ (extended abstract)

Lewis, Stephen ; Thiem, Nathaniel.
The standard supercharacter theory of the finite unipotent upper-triangular matrices $U_n(q)$ gives rise to a beautiful combinatorics based on set partitions. As with the representation theory of the symmetric group, embeddings of $U_m(q) \subseteq U_n(q)$ for $m \leq n$ lead to branching rules. […]

The stability of the Kronecker product of Schur functions

Briand, Emmanuel ; Orellana, Rosa ; Rosas, Mercedes.
In the late 1930's Murnaghan discovered the existence of a stabilization phenomenon for the Kronecker product of Schur functions. For $n$ large enough, the values of the Kronecker coefficients appearing in the product of two Schur functions of degree $n$ do not depend on the first part of the […]

Viewing counting polynomials as Hilbert functions via Ehrhart theory

Breuer, Felix ; Dall, Aaron.
Steingrímsson (2001) showed that the chromatic polynomial of a graph is the Hilbert function of a relative Stanley-Reisner ideal. We approach this result from the point of view of Ehrhart theory and give a sufficient criterion for when the Ehrhart polynomial of a given relative polytopal complex is […]

Words and Noncommutative Invariants of the Hyperoctahedral Group

Bergeron-Brlek, Anouk.
Let $\mathcal{B}_n$ be the hyperoctahedral group acting on a complex vector space $\mathcal{V}$. We present a combinatorial method to decompose the tensor algebra $T(\mathcal{V})$ on $\mathcal{V}$ into simple modules via certain words in a particular Cayley graph of $\mathcal{B}_n$. We then give […]

A unified bijective method for maps: application to two classes with boundaries

Bernardi, Olivier ; Fusy, Eric.
Based on a construction of the first author, we present a general bijection between certain decorated plane trees and certain orientations of planar maps with no counterclockwise circuit. Many natural classes of maps (e.g. Eulerian maps, simple triangulations,...) are in bijection with a subset of […]

Combinatorial aspects of Escher tilings

Massé, Alexandre Blondin ; Brlek, Srecko ; Labbé, Sébastien.
In the late 30's, Maurits Cornelis Escher astonished the artistic world by producing some puzzling drawings. In particular, the tesselations of the plane obtained by using a single tile appear to be a major concern in his work, drawing attention from the mathematical community. Since a tile in the […]

An Algebraic Analogue of a Formula of Knuth

Levine, Lionel.
We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph $G$ and its directed line graph $\mathcal{L} G$. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case […]

QSym over Sym has a stable basis

Lauve, Aaron ; Mason, Sarah K.
We prove that the subset of quasisymmetric polynomials conjectured by Bergeron and Reutenauer to be a basis for the coinvariant space of quasisymmetric polynomials is indeed a basis. This provides the first constructive proof of the Garsia―Wallach result stating that quasisymmetric polynomials form […]

Equivalence Relations of Permutations Generated by Constrained Transpositions

Linton, Stephen ; Propp, James ; Roby, Tom ; West, Julian.
We consider a large family of equivalence relations on permutations in $S_n$ that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of […]

Three notions of tropical rank for symmetric matrices

Cartwright, Dustin ; Chan, Melody.
We introduce and study three different notions of tropical rank for symmetric matrices and dissimilarity matrices in terms of minimal decompositions into rank 1 symmetric matrices, star tree matrices, and tree matrices. Our results provide a close study of the tropical secant sets of certain nice […]

Models and refined models for involutory reflection groups and classical Weyl groups

Caselli, Fabrizio ; Fulci, Roberta.
A finite subgroup $G$ of $GL(n,\mathbb{C})$ is involutory if the sum of the dimensions of its irreducible complex representations is given by the number of absolute involutions in the group, i.e. elements $g \in G$ such that $g \bar{g}=1$, where the bar denotes complex conjugation. A uniform […]

On $\gamma$-vectors satisfying the Kruskal-Katona inequalities

Nevo, E. ; Petersen, T. K..
We present examples of flag homology spheres whose $\gamma$-vectors satisfy the Kruskal-Katona inequalities. This includes several families of well-studied simplicial complexes, including Coxeter complexes and the simplicial complexes dual to the associahedron and to the cyclohedron. In these cases, […]

A preorder-free construction of the Kazhdan-Lusztig representations of Hecke algebras $H_n(q)$ of symmetric groups

Buehrle, Charles ; Skandera, Mark.
We use a quantum analog of the polynomial ring $\mathbb{Z}[x_{1,1},\ldots, x_{n,n}]$ to modify the Kazhdan-Lusztig construction of irreducible $H_n(q)$-modules. This modified construction produces exactly the same matrices as the original construction in [$\textit{Invent. Math.}$ $\textbf{53}$ […]

On $k$-crossings and $k$-nestings of permutations

Burrill, Sophie ; Mishna, Marni ; Post, Jacob.
We introduce $k$-crossings and $k$-nestings of permutations. We show that the crossing number and the nesting number of permutations have a symmetric joint distribution. As a corollary, the number of $k$-noncrossing permutations is equal to the number of $k$-nonnesting permutations. We also provide […]

Crystals from categorified quantum groups

Lauda, Aaron D. ; Vazirani, Monica.
We study the crystal structure on categories of graded modules over algebras which categorify the negative half of the quantum Kac-Moody algebra associated to a symmetrizable Cartan data. We identify this crystal with Kashiwara's crystal for the corresponding negative half of the quantum Kac-Moody […]

On the diagonal ideal of $(\mathbb{C}^2)^n$ and $q,t$-Catalan numbers

Lee, Kyungyong ; Li, Li.
Let $I_n$ be the (big) diagonal ideal of $(\mathbb{C}^2)^n$. Haiman proved that the $q,t$-Catalan number is the Hilbert series of the graded vector space $M_n=\bigoplus_{d_1,d_2}(M_n)_{d_1,d_2}$ spanned by a minimal set of generators for $I_n$. We give simple upper bounds on $\textrm{dim} […]

Extended Abstract for Enumerating Pattern Avoidance for Affine Permutations

Crites, Andrew.
In this paper we study pattern avoidance for affine permutations. In particular, we show that for a given pattern $p$, there are only finitely many affine permutations in $\widetilde{S}_n$ that avoid $p$ if and only if $p$ avoids the pattern $321$. We then count the number of affine permutations […]

Chamber Structure For Double Hurwitz Numbers

Cavalieri, Renzo ; JOHNSON, Paul ; Markwig, Hannah.
Double Hurwitz numbers count covers of the sphere by genus $g$ curves with assigned ramification profiles over $0$ and $\infty$, and simple ramification over a fixed branch divisor. Goulden, Jackson and Vakil (2005) have shown double Hurwitz numbers are piecewise polynomial in the orders of […]

Random Walks in the Plane

Borwein, Jonathan M. ; Nuyens, Dirk ; Straub, Armin ; Wan, James.
We study the expected distance of a two-dimensional walk in the plane with unit steps in random directions. A series evaluation and recursions are obtained making it possible to explicitly formulate this distance for small number of steps. Formulae for all the moments of a 2-step and a 3-step walk […]

Descent polynomials for permutations with bounded drop size

Chung, Fan ; Claesson, Anders ; Dukes, Mark ; Graham, Ronald.
Motivated by juggling sequences and bubble sort, we examine permutations on the set${1, 2, \ldots, n}$ with $d$ descents and maximum drop size $k$. We give explicit formulas for enumerating such permutations for given integers $k$ and $d$. We also derive the related generating functions and prove […]

The biHecke monoid of a finite Coxeter group

Hivert, Florent ; Schilling, Anne ; Thiéry, Nicolas M..
For any finite Coxeter group $W$, we introduce two new objects: its cutting poset and its biHecke monoid. The cutting poset, constructed using a generalization of the notion of blocks in permutation matrices, almost forms a lattice on $W$. The construction of the biHecke monoid relies on the usual […]

Computing Node Polynomials for Plane Curves

Block, Florian.
According to the Göttsche conjecture (now a theorem), the degree $N^{d, \delta}$ of the Severi variety of plane curves of degree $d$ with $\delta$ nodes is given by a polynomial in $d$, provided $d$ is large enough. These "node polynomials'' $N_{\delta} (d)$ were determined by Vainsencher and […]

The expansion of Hall-Littlewood functions in the dual Grothendieck polynomial basis

Bandlow, Jason ; Morse, Jennifer.
A combinatorial expansion of the Hall-Littlewood functions into the Schur basis of symmetric functions was first given by Lascoux and Schützenberger, with their discovery of the charge statistic. A combinatorial expansion of stable Grassmannian Grothendieck polynomials into monomials was first given […]

Counting unicellular maps on non-orientable surfaces

Bernardi, Olivier ; Chapuy, Guillaume.
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 […]

Pattern avoidance in partial permutations (extended abstract)

Claesson, Anders ; Jelínek, Vít ; Jelínková, Eva ; Kitaev, Sergey.
Motivated by the concept of partial words, we introduce an analogous concept of partial permutations. A $\textit{partial permutation of length n with k holes}$ is a sequence of symbols $\pi = \pi_1 \pi_2 \cdots \pi_n$ in which each of the symbols from the set $\{1,2,\ldots,n-k\}$ appears exactly […]

A canonical basis for Garsia-Procesi modules

Blasiak, Jonah.
We identify a subalgebra $\widehat{\mathscr{H}}^+_n$ of the extended affine Hecke algebra $\widehat{\mathscr{H}}_n$ of type $A$. The subalgebra $\widehat{\mathscr{H}}^+_n$ is a u-analogue of the monoid algebra of $\mathcal{S}_n ⋉ℤ_≥0^n$ and inherits a canonical basis from that of […]

The Frobenius Complex

Clark, Eric ; Ehrenborg, Richard.
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 […]

$n!$ matchings, $n!$ posets (extended abstract)

Claesson, Anders ; Linusson, Svante.
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. […]

Toric Ideals of Flow Polytopes

Lenz, Matthias.
We show that toric ideals of flow polytopes are generated in degree $3$. This was conjectured by Diaconis and Eriksson for the special case of the Birkhoff polytope. Our proof uses a hyperplane subdivision method developed by Haase and Paffenholz. It is known that reduced revlex Gröbner bases of the […]

Boolean complexes and boolean numbers

Tenner, Bridget Eileen.
The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is […]

Bruhat order, rationally smooth Schubert varieties, and hyperplane arrangements

Oh, Suho ; Yoo, Hwanchul.
We link Schubert varieties in the generalized flag manifolds with hyperplane arrangements. For an element of a Weyl group, we construct a certain graphical hyperplane arrangement. We show that the generating function for regions of this arrangement coincides with the Poincaré polynomial of the […]

A unification of permutation patterns related to Schubert varieties

Úlfarsson, Henning A..
We prove new connections between permutation patterns and singularities of Schubert varieties, by giving a new characterization of factorial and Gorenstein varieties in terms of so called bivincular patterns. These are generalizations of classical patterns where conditions are placed on the location […]

Schubert complexes and degeneracy loci

Sam, Steven V.
The classical Thom―Porteous formula expresses the homology class of the degeneracy locus of a generic map between two vector bundles as an alternating sum of Schur polynomials. A proof of this formula was given by Pragacz by expressing this alternating sum as the Euler characteristic of a Schur […]

The Hodge Structure of the Coloring Complex of a Hypergraph (Extended Abstract)

Rundell, Sarah C ; Long, Jane H.
Let $G$ be a simple graph with $n$ vertices. The coloring complex$ Δ (G)$ was defined by Steingrímsson, and the homology of $Δ (G)$ was shown to be nonzero only in dimension $n-3$ by Jonsson. Hanlon recently showed that the Eulerian idempotents provide a decomposition of the homology group […]

Bijective enumeration of permutations starting with a longest increasing subsequence

Panova, Greta.
We prove a formula for the number of permutations in $S_n$ such that their first $n-k$ entries are increasing and their longest increasing subsequence has length $n-k$. This formula first appeared as a consequence of character polynomial calculations in recent work of Adriano Garsia and Alain […]

The cluster and dual canonical bases of Z [x_11, ..., x_33] are equal

Rhoades, Brendon.
The polynomial ring $\mathbb{Z}[x_{11}, . . . , x_{33}]$ has a basis called the dual canonical basis whose quantization facilitates the study of representations of the quantum group $U_q(\mathfrak{sl}3(\mathbb{C}))$. On the other hand, $\mathbb{Z}[x_{11}, . . . , x_{33}]$ inherits a basis from the […]

Crossings and nestings in set partitions of classical types

Rubey, Martin ; Stump, Christian.
In this extended abstract, we investigate bijections on various classes of set partitions of classical types that preserve openers and closers. On the one hand we present bijections for types $B$ and $C$ that interchange crossings and nestings, which generalize a construction by Kasraoui and Zeng […]

Cyclic sieving for longest reduced words in the hyperoctahedral group

Petersen, T. K. ; Serrano, L..
We show that the set $R(w_0)$ of reduced expressions for the longest element in the hyperoctahedral group exhibits the cyclic sieving phenomenon. More specifically, $R(w_0)$ possesses a natural cyclic action given by moving the first letter of a word to the end, and we show that the orbit structure […]

Counting RNA pseudoknotted structures (extended abstract)

Saule, Cédric ; Regnier, Mireille ; Steyaert, Jean-Marc ; Denise, Alain.
In 2004, Condon and coauthors gave a hierarchical classification of exact RNA structure prediction algorithms according to the generality of structure classes that they handle. We complete this classification by adding two recent prediction algorithms. More importantly, we precisely quantify the […]

Denominator formulas for Lie superalgebras (extended abstract)

Kac, Victor ; Möseneder Frajria, Pierluigi ; Papi, Paolo.
We provide formulas for the Weyl-Kac denominator and superdenominator of a basic classical Lie superalgebra for a distinguished set of positive roots. \par

Balanced binary trees in the Tamari lattice

Giraudo, Samuele.
We show that the set of balanced binary trees is closed by interval in the Tamari lattice. We establish that the intervals $[T_0, T_1]$ where $T_0$ and $T_1$ are balanced trees are isomorphic as posets to a hypercube. We introduce tree patterns and synchronous grammars to get a functional equation […]

Chain enumeration of k-divisible noncrossing partitions of classical types

Kim, Jang Soo.
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 […]

A Combinatorial Formula for Orthogonal Idempotents in the $0$-Hecke Algebra of $S_N$

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

The Möbius function of separable permutations (extended abstract)

Jelínek, Vít ; Jelínková, Eva ; Steingrímsson, Einar.
A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. Using the notion of separating tree, we give a computationally efficient formula for the Möbius function of an interval $(q,p)$ in the […]

Tropical secant graphs of monomial curves

Cueto, María Angélica ; Lin, Shaowei.
We construct and study an embedded weighted balanced graph in $\mathbb{R}^{n+1}$ parametrized by a strictly increasing sequence of $n$ coprime numbers $\{ i_1, \ldots, i_n\}$, called the $\textit{tropical secant surface graph}$. We identify it with the tropicalization of a surface in […]

Linear coefficients of Kerov's polynomials: bijective proof and refinement of Zagier's result

Féray, Valentin ; Vassilieva, Ekaterina A..
We look at the number of permutations $\beta$ of $[N]$ with $m$ cycles such that $(1 2 \ldots N) \beta^{-1}$ is a long cycle. These numbers appear as coefficients of linear monomials in Kerov's and Stanley's character polynomials. D. Zagier, using algebraic methods, found an unexpected connection […]

Word equations in a uniquely divisible group

Hillar, Christopher J. ; Levine, Lionel ; Rhea, Darren.
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 […]

Constant term evaluation for summation of C-finite sequences

Hou, Qing-Hu ; Xin, Guoce.
Based on constant term evaluation, we present a new method to compute a closed form of the summation $∑_k=0^n-1 ∏_j=1^r F_j(a_jn+b_jk+c_j)$, where ${F_j(k)} are $C$-finite sequences and $a_j$ and $a_j+b_j$ are nonnegative integers. Our algorithm is much faster than that of Greene and Wilf.

Enumeration of inscribed polyominos

Goupil, Alain ; Cloutier, Hugo ; Nouboud, Fathallah.
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 […]

Affine structures and a tableau model for $E_6$ crystals

Jones, Brant ; Schilling, Anne.
We provide the unique affine crystal structure for type $E_6^{(1)}$ Kirillov―Reshetikhin crystals corresponding to the multiples of fundamental weights $s\Lambda _1, s\Lambda _2$, and $s\Lambda _6$ for all $s≥ 1$ (in Bourbaki's labeling of the Dynkin nodes, where 2 is the adjoint node). Our methods […]

A Closed Character Formula for Symmetric Powers of Irreducible Representations

Kousidis, Stavros.
We prove a closed character formula for the symmetric powers $S^N V(λ )$ of a fixed irreducible representation $V(λ )$ of a complex semi-simple Lie algebra $\mathfrak{g}$ by means of partial fraction decomposition. The formula involves rational functions in rank of $\mathfrak{g}$ many variables […]

Enumerating (2+2)-free posets by the number of minimal elements and other statistics

Kitaev, Sergey ; Remmel, Jeffrey.
A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. In a recent paper, Bousquet-Mélou et al. found, using so called ascent sequences, the generating function for the number of (2+2)-free posets: $P(t)=∑_n≥ […]

Combinatorial formulas for double parabolic R-polynomials

Lambright, Justin ; Skandera, Mark.
The well-known R-polynomials in ℤ[q], which appear in Hecke algebra computations, are closely related to certain modified R-polynomials in ℕ[q] whose coefficients have simple combinatorial interpretations. We generalize this second family of polynomials, providing combinatorial interpretations for […]

Compositions and samples of geometric random variables with constrained multiplicities

Archibald, Margaret ; Knopfmacher, Arnold ; Mansour, Toufik.
We investigate the probability that a random composition (ordered partition) of the positive integer $n$ has no parts occurring exactly $j$ times, where $j$ belongs to a specified finite $\textit{`forbidden set'}$ $A$ of multiplicities. This probability is also studied in the related case of samples […]

The Homology of the Real Complement of a $k$-parabolic Subspace Arrangement

Severs, Christopher ; White, Jacob A..
The $k$-parabolic subspace arrangement, introduced by Barcelo, Severs and White, is a generalization of the well known $k$-equal arrangements of type-$A$ and type-$B$. In this paper we use the discrete Morse theory of Forman to study the homology of the complements of $k$-parabolic subspace […]

Pattern avoidance in alternating permutations and tableaux (extended abstract)

Lewis, Joel Brewster.
We give bijective proofs of pattern-avoidance results for a class of permutations generalizing alternating permutations. The bijections employed include a modified form of the RSK insertion algorithm and recursive bijections based on generating trees. As special cases, we show that the sets […]

On extensions of the Newton-Raphson iterative scheme to arbitrary orders

Labelle, Gilbert.
The classical quadratically convergent Newton-Raphson iterative scheme for successive approximations of a root of an equation $f(t)=0$ has been extended in various ways by different authors, going from cubical convergence to convergence of arbitrary orders. We introduce two such extensions, using […]

A note on moments of derivatives of characteristic polynomials

Dehaye, Paul-Olivier.
We present a simple technique to compute moments of derivatives of unitary characteristic polynomials. The first part of the technique relies on an idea of Bump and Gamburd: it uses orthonormality of Schur functions over unitary groups to compute matrix averages of characteristic polynomials. In […]

$f$-vectors of subdivided simplicial complexes (extended abstract)

Delucchi, Emanuele ; Pixton, Aaron ; Sabalka, Lucas.
We take a geometric point of view on the recent result by Brenti and Welker, who showed that the roots of the $f$-polynomials of successive barycentric subdivisions of a finite simplicial complex $X$ converge to fixed values depending only on the dimension of $X$. We show that these numbers are […]

A Pieri rule for skew shapes

Assaf, Sami H. ; McNamara, Peter R. W..
The Pieri rule expresses the product of a Schur function and a single row Schur function in terms of Schur functions. We extend the classical Pieri rule by expressing the product of a skew Schur function and a single row Schur function in terms of skew Schur functions. Like the classical rule, our […]

The spectrum of an asymmetric annihilation process

Ayyer, Arvind ; Strehl, Volker.
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 […]

Weakly directed self-avoiding walks

Bacher, Axel ; Bousquet-Mélou, Mireille.
We define a new family of self-avoiding walks (SAW) on the square lattice, called $\textit{weakly directed walks}$. These walks have a simple characterization in terms of the irreducible bridges that compose them. We determine their generating function. This series has a complex singularity […]

Involutions of the Symmetric Group and Congruence B-Orbits (Extended Abstract)

Bagno, Eli ; Cherniavsky, Yonah.
We study the poset of Borel congruence classes of symmetric matrices ordered by containment of closures. We give a combinatorial description of this poset and calculate its rank function. We discuss the relation between this poset and the Bruhat poset of involutions of the symmetric group. Also we […]

Zonotopes, toric arrangements, and generalized Tutte polynomials

Moci, Luca.
We introduce a multiplicity Tutte polynomial $M(x,y)$, which generalizes the ordinary one and has applications to zonotopes and toric arrangements. We prove that $M(x,y)$ satisfies a deletion-restriction recurrence and has positive coefficients. The characteristic polynomial and the Poincaré […]

Harmonics for deformed Steenrod operators (Extended Abstract)

Bergeron, François ; Garsia, Adriano ; Wallach, Nolan.
We explore in this paper the spaces of common zeros of several deformations of Steenrod operators. Proofs are omitted in view of pages limitation for the extended abstract. \par

Unitary Matrix Integrals, Primitive Factorizations, and Jucys-Murphy Elements

Matsumoto, Sho ; Novak, Jonathan.
A factorization of a permutation into transpositions is called "primitive'' if its factors are weakly ordered.We discuss the problem of enumerating primitive factorizations of permutations, and its place in the hierarchy of previously studied factorization problems. Several formulas enumerating […]

On formulas for moments of the Wishart distributions as weighted generating functions of matchings

Numata, Yasuhide ; Kuriki, Satoshi.
We consider the real and complex noncentral Wishart distributions. The moments of these distributions are shown to be expressed as weighted generating functions of graphs associated with the Wishart distributions. We give some bijections between sets of graphs related to moments of the real Wishart […]

Fully Packed Loop configurations in a triangle and Littlewood Richardson coefficients

Nadeau, Philippe.
We are interested in Fully Packed Loops in a triangle (TFPLs), as introduced by Caselli at al. and studied by Thapper. We show that for Fully Packed Loops with a fixed link pattern (refined FPL), there exist linear recurrence relations with coefficients computed from TFPL configurations. We then […]

Ordered increasing $k$-trees: Introduction and analysis of a preferential attachment network model

Panholzer, Alois ; Seitz, Georg.
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 […]

The height of scaled attachment random recursive trees

Devroye, Luc ; Fawzi, Omar ; Fraiman, Nicolas.
We study depth properties of a general class of random recursive trees where each node $n$ attaches to the random node $\lfloor nX_n \rfloor$ and $X_0, \ldots , X_n$ is a sequence of i.i.d. random variables taking values in $[0,1)$. We call such trees scaled attachment random recursive trees […]

Stochastic Analysis of the $k$-Server Problem on the Circle

Anagnostopoulos, Aris ; Dombry, Clément ; Guillotin-Plantard, Nadine ; Kontoyiannis, Ioannis ; Upfal, Eli.
We consider a stochastic version of the $k$-server problem in which $k$ servers move on a circle to satisfy stochastically generated requests. The requests are independent and identically distributed according to an arbitrary distribution on a circle, which is either discrete or continuous. The cost […]

Geometric Bucket Trees: Analysis of Linear Bucket Tree

Jacquet, Philippe ; Muhlethaler, Paul.
We analyse the average number of buckets in a Linear Bucket tree created by $n$ points uniformly dispatched on an interval of length $y$. A new bucket is created when a point does not fall in an existing bucket. The bucket is the interval of length 2 centered on the point. We illustrate this concept […]

A symbolic method to compute the probability distribution of the number of pattern occurences in random texts generated by stochastic 0L-systems

Loi, Cedric ; Cournède, Paul-Henry ; Françon, Jean.
The analysis of pattern occurrences has numerous applications, in particular in biology. In this article, a symbolic method is proposed to compute the distribution associated to the number of occurences of a specific pattern in a random text generated by a stochastic 0L-system. To that purpose, a […]

The number of Euler tours of a random $d$-in/$d$-out graph

Creed, Páidí ; Cryan, Mary.
In this paper we obtain the expectation and variance of the number of Euler tours of a random $d$-in/$d$-out directed graph, for $d \geq 2$. We use this to obtain the asymptotic distribution and prove a concentration result. We are then able to show that a very simple approach for uniform sampling […]

Partial Quicksort and Quickpartitionsort

Martínez, Conrado ; Rösler, Uwe.
Partial Quicksort sorts the $l$ smallest elements in a list of length $n$. We provide a complete running time analysis for this combination of Find and Quicksort. Further we give some optimal adapted versions, called Partition Quicksort, with an asymptotic running time $c_1l\ln l+c_2l+n+o(n)$. The […]

An optimal cardinality estimation algorithm based on order statistics and its full analysis

Lumbroso, Jérémie.
Building on the ideas of Flajolet and Martin (1985), Alon et al. (1987), Bar-Yossef et al. (2002), Giroire (2005), we develop a new algorithm for cardinality estimation, based on order statistics which, according to Chassaing and Gerin (2006), is optimal among similar algorithms. This algorithm has […]

The degree distribution in unlabelled $2$-connected graph families

Kraus, Veronika.
We study the random variable $X_n^k$, counting the number of vertices of degree $k$ in a randomly chosen $2$-connected graph of given families. We prove a central limit theorem for $X_n^k$ with expected value $\mathbb{E}X_n^k \sim \mu_kn$ and variance $\mathbb{V}X_n^k \sim \sigma_k^2n$, both […]

No Shannon effect on probability distributions on Boolean functions induced by random expressions

Genitrini, Antoine ; Gittenberger, Bernhard.
The Shannon effect states that "almost all'' Boolean functions have a complexity close to the maximal possible for the uniform probability distribution. In this paper we use some probability distributions on functions, induced by random expressions, and prove that this model does not exhibit the […]

Counting Markov Types

Jacquet, Philippe ; Knessl, Charles ; Szpankowski, Wojciech.
The method of types is one of the most popular techniques in information theory and combinatorics. Two sequences of equal length have the same type if they have identical empirical distributions. In this paper, we focus on Markov types, that is, sequences generated by a Markov source (of order one). […]

Dynamic Threshold Strategy for Universal Best Choice Problem

Kozik, Jakub.
We propose a new strategy for universal best choice problem for partially ordered sets. We present its partial analysis which is sufficient to prove that the probability of success with this strategy is asymptotically strictly greater than 1/4, which is the value of the best universal strategy known […]

Almost sure asymptotics for the random binary search tree

Roberts, Matthew, .
We consider a (random permutation model) binary search tree with $n$ nodes and give asymptotics on the $\log$ $\log$ scale for the height $H_n$ and saturation level $h_n$ of the tree as $n \to \infty$, both almost surely and in probability. We then consider the number $F_n$ of particles at level […]

Occupancy distributions in Markov chains via Doeblin's ergodicity coefficient

Chestnut, Stephen ; Lladser, Manuel E..
We state and prove new properties about Doeblin's ergodicity coefficient for finite Markov chains. We show that this coefficient satisfies a sub-multiplicative type inequality (analogous to the Markov-Dobrushin's ergodicity coefficient), and provide a novel but elementary proof of Doeblin's […]

Random Generation Using Binomial Approximations

Gouyou-Beauchamps, Dominique ; Nicaud, Cyril.
Generalizing an idea used by Alonso to generate uniformly at random Motzkin words, we outline an approach to build efficient random generators using binomial distributions and rejection algorithms. As an application of this method, we present random generators, both efficient and easy to implement, […]

The Bernoulli sieve: an overview

Gnedin, Alexander ; Iksanov, Alexander ; Marynych, Alexander.
The Bernoulli sieve is a version of the classical balls-in-boxes occupancy scheme, in which random frequencies of infinitely many boxes are produced by a multiplicative random walk, also known as the residual allocation model or stick-breaking. We give an overview of the limit theorems concerning […]

Asymptotic Rational Approximation To Pi: Solution of an "Unsolved Problem'' Posed By Herbert Wilf

Ward, Mark Daniel.
The webpage of Herbert Wilf describes eight Unsolved Problems. Here, we completely resolve the third of these eight problems. The task seems innocent: find the first term of the asymptotic behavior of the coefficients of an ordinary generating function, whose coefficients naturally yield rational […]

On unary nodes in tries

Wagner, Stephan.
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 […]

The total Steiner $k$-distance for $b$-ary recursive trees and linear recursive trees

Munsonius, Götz Olaf.
We prove a limit theorem for the total Steiner $k$-distance of a random $b$-ary recursive tree with weighted edges. The total Steiner $k$-distance is the sum of all Steiner $k$-distances in a tree and it generalises the Wiener index. The limit theorem is obtained by using a limit theorem in the […]

Digital Trees and Memoryless Sources: from Arithmetics to Analysis

Flajolet, Philippe ; Roux, Mathieu ; Vallée, Brigitte.
Digital trees, also known as $\textit{"tries''}$, are fundamental to a number of algorithmic schemes, including radix-based searching and sorting, lossless text compression, dynamic hashing algorithms, communication protocols of the tree or stack type, distributed leader election, and so on. This […]

Asymptotics for Walks in a Weyl chamber of Type $B$ (extended abstract)

Feierl, Thomas.
We consider lattice walks in $\mathbb{R}^k$ confined to the region $0 < x_1 < x_2 \ldots < x_k$ with fixed (but arbitrary) starting and end points. The walks are required to be "reflectable", that is, we assume that the number of paths can be counted using the reflection principle. The main result […]

On the diameter of random planar graphs

Chapuy, Guillaume ; Fusy, Eric ; Gimenez, Omer ; Noy, Marc.
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 […]

Square root singularities of infinite systems of functional equations

Morgenbesser, Johannes F..
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 […]

Random sampling of lattice paths with constraints, via transportation

Gerin, Lucas.
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 […]

A Note on Invariant Random Variables

Cichoń, Jacek ; Klonowski, Marek.
In this paper we present a simple theory, based on the notion of group action on a set, which explains why processes of throwing random sets of points and throwing random lines are similar up to the second moment of counting functions connected with them. We also discuss other applications of this […]

Analyzing a Weighted Digital Sum Variant

Cheung, Y. K. ; Golin, Mordecai.
Consider the following weighted digital sum (WDS) variant: write integer $n$ as $n=2^{i_1} + 2^{i_2} + \cdots + 2^{i_k}$ with $i_1 > i_2 > \cdots > i_k \geq 0$ and set $W_M(n) := \sum_{t=1}^k t^M 2^{i_t}$. This type of weighted digital sum arises (when $M=1$) in the analysis of bottom-up mergesort […]

Renewal theory in analysis of tries and strings: Extended abstract

Janson, Svante.
We give a survey of a number of simple applications of renewal theory to problems on random strings, in particular to tries and Khodak and Tunstall codes.

The maximum of Brownian motion with parabolic drift (Extended abstract)

Janson, Svante ; Louchard, Guy ; Martin-Löf, Anders.
We study the maximum of a Brownian motion with a parabolic drift; this is a random variable that often occurs as a limit of the maximum of discrete processes whose expectations have a maximum at an interior point. This has some applications in algorithmic and data structures analysis. We give series […]

The analysis of a prioritised probabilistic algorithm to find large induced forests in regular graphs with large girth

Hoppen, Carlos.
The analysis of probabilistic algorithms has proved to be very successful for finding asymptotic bounds on parameters of random regular graphs. In this paper, we show that similar ideas may be used to obtain deterministic bounds for one such parameter in the case of regular graphs with large girth. […]

Multi-dimensional Boltzmann Sampling of Languages

Bodini, Olivier ; Ponty, Yann.
We address the uniform random generation of words from a context-free language (over an alphabet of size $k$), while constraining every letter to a targeted frequency of occurrence. Our approach consists in a multidimensional extension of Boltzmann samplers. We show that, under mostly […]

Cover time of a random graph with given degree sequence

Abdullah, Mohammed ; Cooper, Colin ; Frieze, Alan.
In this paper we establish the cover time of a random graph $G(\textbf{d})$ chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\textbf{d}$. We show that under certain restrictions on $\textbf{d}$, the cover time of $G(\textbf{d})$ is with high probability […]

Finding hidden cliques in linear time

Feige, Uriel ; Ron, Dorit.
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 […]

Asymptotics of Decomposable Combinatorial Structures of Alg-Log Type With Positive Log Exponent

Gao, Zhicheng ; Laferrière, David ; Panario, Daniel.
We consider the multiset construction of decomposable structures with component generating function $C(z)$ of alg-log type, $\textit{i.e.}$, $C(z) = (1-z)^{-\alpha} (\log \frac{1}{ 1-z})^{\beta}$. We provide asymptotic results for the number of labeled objects of size $n$ in the case when $\alpha$ […]

Distributional Convergence for the Number of Symbol Comparisons Used by QuickSort (Extended Abstract)

fill, james Allen.
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 […]

The distribution of the number of small cuts in a random planar triangulation

Gao, Zhicheng ; Schaeffer, Gilles.
We enumerate rooted 3-connected (2-connected) planar triangulations with respect to the vertices and 3-cuts (2-cuts). Consequently, we show that the distribution of the number of 3-cuts in a random rooted 3-connected planar triangulation with $n+3$ vertices is asymptotically normal with mean […]

The variance for partial match retrievals in $k$-dimensional bucket digital trees

Fuchs, Michael.
The variance of partial match queries in $k$-dimensional tries was investigated in a couple of papers in the mid-nineties, the resulting analysis being long and complicated. In this paper, we are going to re-derive these results with a much easier approach. Moreover, our approach works for […]

Induced acyclic subgraphs in random digraphs: Improved bounds

Dutta, Kunal ; Subramanian, C. R..
Given a simple directed graph $D = (V,A)$, let the size of the largest induced directed acyclic graph $\textit{(dag)}$ be denoted by $mas(D)$. Let $D \in \mathcal{D}(n,p)$ be a $\textit{random}$ instance, obtained by choosing each of the $\binom{n}{2}$ possible undirected edges independently with […]

Combinatorial aspects of pyramids of one-dimensional pieces of fixed integer length

Durhuus, Bergfinnur ; Eilers, Søren.
We consider pyramids made of one-dimensional pieces of fixed integer length $a$ and which may have pairwise overlaps of integer length from $1$ to $a$. We give a combinatorial proof that the number of pyramids of size $m$, i.e., consisting of $m$ pieces, equals $\binom{am-1}{m-1}$ for each $a \geq […]

Stochastic Flips on Dimer Tilings

Fernique, Thomas ; Regnault, Damien.
This paper introduces a Markov process inspired by the problem of quasicrystal growth. It acts over dimer tilings of the triangular grid by randomly performing local transformations, called $\textit{flips}$, which do not increase the number of identical adjacent tiles (this number can be thought as […]

Combinatorics of the PASEP partition function

Josuat-Vergès, Matthieu.
We consider a three-parameter PASEP model on $N$ sites. A closed formula for the partition function was obtained analytically by Blythe et al. We give a new formula which generalizes the one of Blythe et al, and is proved in two combinatorial ways. Moreover the first proof can be adapted to give the […]

Bounded discrete walks

Banderier, C. ; Nicodème, P..
This article tackles the enumeration and asymptotics of directed lattice paths (that are isomorphic to unidimensional paths) of bounded height (walks below one wall, or between two walls, for $\textit{any}$ finite set of jumps). Thus, for any lattice paths, we give the generating functions of […]

Valuative invariants for polymatroids

Derksen, Harm ; Fink, Alex.
Many important invariants for matroids and polymatroids, such as the Tutte polynomial, the Billera-Jia-Reiner quasi-symmetric function, and the invariant $\mathcal{G}$ introduced by the first author, are valuative. In this paper we construct the $\mathbb{Z}$-modules of all $\mathbb{Z}$-valued […]

Linear Systems on Tropical Curves

Haase, Christian ; Musiker, Gregg ; Yu, Josephine.
A tropical curve $\Gamma$ is a metric graph with possibly unbounded edges, and tropical rational functions are continuous piecewise linear functions with integer slopes. We define the complete linear system $|D|$ of a divisor $D$ on a tropical curve $\Gamma$ analogously to the classical counterpart. […]

An algorithm which generates linear extensions for a generalized Young diagram with uniform probability

Nakada, Kento ; Okamura, Shuji.
The purpose of this paper is to present an algorithm which generates linear extensions for a generalized Young diagram, in the sense of D. Peterson and R. A. Proctor, with uniform probability. This gives a proof of a D. Peterson's hook formula for the number of reduced decompositions of a given […]

Products of Geck-Rouquier conjugacy classes and the Hecke algebra of composed permutations

Méliot, Pierre-Loïc.
We show the $q$-analog of a well-known result of Farahat and Higman: in the center of the Iwahori-Hecke algebra $\mathscr{H}_{n,q}$, if $(a_{\lambda \mu}^ν (n,q))_ν$ is the set of structure constants involved in the product of two Geck-Rouquier conjugacy classes $\Gamma_{\lambda, n}$ and […]

Weighted branching formulas for the hook lengths

Ciocan-Fontanine, Ionuţ ; Konvalinka, Matjaž ; Pak, Igor.
The famous hook-length formula is a simple consequence of the branching rule for the hook lengths. While the Greene-Nijenhuis-Wilf probabilistic proof is the most famous proof of the rule, it is not completely combinatorial, and a simple bijection was an open problem for a long time. In this […]

A bijection between (bounded) dominant Shi regions and core partitions

Fishel, Susanna ; Vazirani, Monica.
It is well-known that Catalan numbers $C_n = \frac{1}{ n+1} \binom{2n}{n}$ count the number of dominant regions in the Shi arrangement of type $A$, and that they also count partitions which are both n-cores as well as $(n+1)$-cores. These concepts have natural extensions, which we call here the […]

Mixed Statistics on $01$-Fillings of Moon Polyominoes

Chen, William Y. C. ; Wang, Andrew Y. Z. ; Yan, Catherine H. ; Zhao, Alina F. Y..
We establish a stronger symmetry between the numbers of northeast and southeast chains in the context of $01$-fillings of moon polyominoes. Let $\mathcal{M}$ be a moon polyomino. Consider all the $01$-fillings of $\mathcal{M}$ in which every row has at most one $1$. We introduce four mixed […]

On joint distribution of adjacencies, descents and some Mahonian statistics

Burstein, Alexander.
We prove several conjectures of Eriksen regarding the joint distribution on permutations of the number of adjacencies (descents with consecutive values in consecutive positions), descents and some Mahonian statistics. We also prove Eriksen's conjecture that a certain bistatistic on Viennot's […]

Generalized Ehrhart polynomials

Chen, Sheng ; Li, Nan ; Sam, Steven V.
Let $P$ be a polytope with rational vertices. A classical theorem of Ehrhart states that the number of lattice points in the dilations $P(n) = nP$ is a quasi-polynomial in $n$. We generalize this theorem by allowing the vertices of $P(n)$ to be arbitrary rational functions in $n$. In this case we […]

Criteria for rational smoothness of some symmetric orbit closures

Hultman, Axel.
Let $G$ be a connected reductive linear algebraic group over $ℂ$ with an involution $θ$ . Denote by $K$ the subgroup of fixed points. In certain cases, the $K-orbits$ in the flag variety $G/B$ are indexed by the twisted identities $ι (θ ) = {θ (w^{-1})w | w∈W}$ in the Weyl group $W$. Under this […]

Skew Littlewood―Richardson rules from Hopf algebras

Lam, Thomas ; Lauve, Aaron ; Sottile, Frank.
We use Hopf algebras to prove a version of the Littlewood―Richardson rule for skew Schur functions, which implies a conjecture of Assaf and McNamara. We also establish skew Littlewood―Richardson rules for Schur $P-$ and $Q-$functions and noncommutative ribbon Schur functions, as well as skew Pieri […]

Generalized Energy Statistics and Kostka―Macdonald Polynomials

Kirillov, Anatol N. ; Sakamoto, Reiho.
We give an interpretation of the $t=1$ specialization of the modified Macdonald polynomial as a generating function of the energy statistics defined on the set of paths arising in the context of Box-Ball Systems (BBS-paths for short). We also introduce one parameter generalizations of the energy […]

The Geometry of Lecture Hall Partitions and Quadratic Permutation Statistics

Bright, Katie L. ; Savage, Carla D..
We take a geometric view of lecture hall partitions and anti-lecture hall compositions in order to settle some open questions about their enumeration. In the process, we discover an intrinsic connection between these families of partitions and certain quadratic permutation statistics. We define some […]

polymake and Lattice Polytopes

Joswig, Michael ; Müller, Benjamin ; Paffenholz, Andreas.
The $\mathtt{polymake}$ software system deals with convex polytopes and related objects from geometric combinatorics. This note reports on a new implementation of a subclass for lattice polytopes. The features displayed are enabled by recent changes to the $\mathtt{polymake}$ core, which will be […]

A further correspondence between $(bc,\bar{b})$-parking functions and $(bc,\bar{b})$-forests

Shin, Heesung ; Zeng, Jiang.
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 […]

Perfectness of Kirillov―Reshetikhin crystals for nonexceptional types

Fourier, Ghislain ; Okado, Masato ; Schilling, Anne.
For nonexceptional types, we prove a conjecture of Hatayama et al. about the prefectness of Kirillov―Reshetikhin crystals.

New Hopf Structures on Binary Trees

Forcey, Stefan ; Lauve, Aaron ; Sottile, Frank.
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 […]

Rationality, irrationality, and Wilf equivalence in generalized factor order

Kitaev, Sergey ; Liese, Jeffrey ; Remmel, Jeffrey ; Sagan, Bruce.
Let $P$ be a partially ordered set and consider the free monoid $P^{\ast}$ of all words over $P$. If $w,w' \in P^{\ast}$ then $w'$ is a factor of $w$ if there are words $u,v$ with $w=uw'v$. Define generalized factor order on $P^{\ast}$ by letting $u \leq w$ if there is a factor $w'$ of $w$ having […]

Linear time equivalence of Littlewood―Richardson coefficient symmetry maps

Azenhas, Olga ; Conflitti, Alessandro ; Mamede, Ricardo.
Benkart, Sottile, and Stroomer have completely characterized by Knuth and dual Knuth equivalence a bijective proof of the Littlewood―Richardson coefficient conjugation symmetry, i.e. $c_{\mu, \nu}^{\lambda} =c_{\mu^t,\nu^t}^{\lambda ^t}$. Tableau―switching provides an algorithm to produce such a […]

Enumeration of the distinct shuffles of permutations

Smith Barnes, Camillia.
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 […]

A Combinatorial Approach to Multiplicity-Free Richardson Subvarieties of the Grassmannian

Snider, Michelle.
We consider Buch's rule for K-theory of the Grassmannian, in the Schur multiplicity-free cases classified by Stembridge. Using a result of Knutson, one sees that Buch's coefficients are related to Möbius inversion. We give a direct combinatorial proof of this by considering the product expansion for […]

Shortest path poset of finite Coxeter groups

Blanco, Saúl A..
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$ […]

Automatic Classification of Restricted Lattice Walks

Bostan, Alin ; Kauers, Manuel.
We propose an $\textit{experimental mathematics approach}$ leading to the computer-driven $\textit{discovery}$ of various conjectures about structural properties of generating functions coming from enumeration of restricted lattice walks in 2D and in 3D.

Blocks in Constrained Random Graphs with Fixed Average Degree

Panagiotou, Konstantinos.
This work is devoted to the study of typical properties of random graphs from classes with structural constraints, like for example planar graphs, with the additional restriction that the average degree is fixed. More precisely, within a general analytic framework, we provide sharp concentration […]

k-Parabolic Subspace Arrangements

Severs, Christopher ; White, Jacob.
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 […]

Spanning forests, electrical networks, and a determinant identity

Teufl, Elmar ; Wagner, Stephan.
We aim to generalize a theorem on the number of rooted spanning forests of a highly symmetric graph to the case of asymmetric graphs. We show that this can be achieved by means of an identity between the minor determinants of a Laplace matrix, for which we provide two different (combinatorial as […]

Branching rules in the ring of superclass functions of unipotent upper-triangular matrices

Thiem, Nathaniel.
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 […]

On the 2-adic order of Stirling numbers of the second kind and their differences

Lengyel, Tamás.
Let $n$ and $k$ be positive integers, $d(k)$ and $\nu_2(k)$ denote the number of ones in the binary representation of $k$ and the highest power of two dividing $k$, respectively. De Wannemacker recently proved for the Stirling numbers of the second kind that $\nu_2(S(2^n,k))=d(k)-1, 1\leq k \leq […]

Combinatorial Formulas for Macdonald and Hall-Littlewood Polynomials

Lenart, Cristian.
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 […]

Growth function for a class of monoids

Albenque, Marie ; Nadeau, Philippe.
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 […]

Counting Quiver Representations over Finite Fields Via Graph Enumeration

Helleloid, Geir ; Rodriguez-Villegas, Fernando.
Let $\Gamma$ be a quiver on $n$ vertices $v_1, v_2, \ldots , v_n$ with $g_{ij}$ edges between $v_i$ and $v_j$, and let $\boldsymbol{\alpha} \in \mathbb{N}^n$. Hua gave a formula for $A_{\Gamma}(\boldsymbol{\alpha}, q)$, the number of isomorphism classes of absolutely indecomposable representations […]

Enumeration of alternating sign matrices of even size (quasi)-invariant under a quarter-turn rotation

Aval, Jean-Christophe ; Duchon, Philippe.
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.

On wiring and tiling diagrams related to bases of tropical Plücker functions

Danilov, Vladimir I. ; Karzanov, Alexander V. ; Koshevoy, Gleb A..
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 […]

The absolute order on the hyperoctahedral group

Kallipoliti, Myrto.
The absolute order on the hyperoctahedral group $B_n$ is investigated. It is shown that every closed interval in this order is shellable, those closed intervals which are lattices are characterized and their zeta polynomials are computed. Moreover, using the notion of strong constructibility, it is […]

Words and polynomial invariants of finite groups in non-commutative variables

Bergeron-Brlek, Anouk ; Hohlweg, Christophe ; Zabrocki, Mike.
Let $V$ be a complex vector space with basis $\{x_1,x_2,\ldots,x_n\}$ and $G$ be a finite subgroup of $GL(V)$. The tensor algebra $T(V)$ over the complex is isomorphic to the polynomials in the non-commutative variables $x_1, x_2, \ldots, x_n$ with complex coefficients. We want to give a […]

$m$-noncrossing partitions and $m$-clusters

Bakke Buan, Aslak ; Reiten, Idun ; Thomas, Hugh.
Let $W$ be a finite crystallographic reflection group, with root system $\Phi$. Associated to $W$ there is a positive integer, the generalized Catalan number, which counts the clusters in the associated cluster algebra, the noncrossing partitions for $W$, and several other interesting sets. […]

The Ladder Crystal

Berg, Chris.
In this paper, we introduce a new model of the crystal $B(\Lambda _0)$ of $\widehat{\mathfrak{sl}_{\ell}}$. We briefly describe some of the properties of this crystal and compare it to the combinatorial model of Misra and Miwa.

The $q=-1$ phenomenon for bounded (plane) partitions via homology concentration

Hersh, P. ; Shareshian, J. ; Stanton, D..
Algebraic complexes whose "faces'' are indexed by partitions and plane partitions are introduced, and their homology is proven to be concentrated in even dimensions with homology basis indexed by fixed points of an involution, thereby explaining topologically two quite important instances of […]

Combinatorics of Positroids

Oh, Suho.
Recently Postnikov gave a combinatorial description of the cells in a totally-nonnegative Grassmannian. These cells correspond to a special class of matroids called positroids. There are many interesting combinatorial objects associated to a positroid. We introduce some recent results, including the […]

Unital versions of the higher order peak algebras

Aguiar, Marcelo ; Novelli, Jean-Christophe ; Thibon, Jean-Yves.
We construct unital extensions of the higher order peak algebras defined by Krob and the third author in [Ann. Comb. 9 (2005), 411―430], and show that they can be obtained as homomorphic images of certain subalgebras of the Mantaci-Reutenauer algebras of type $B$. This generalizes a result of […]

A kicking basis for the two column Garsia-Haiman modules

Assaf, Sami ; Garsia, Adriano.
In the early 1990s, Garsia and Haiman conjectured that the dimension of the Garsia-Haiman module $R_{\mu}$ is $n!$, and they showed that the resolution of this conjecture implies the Macdonald Positivity Conjecture. Haiman proved these conjectures in 2001 using algebraic geometry, but the question […]

The Hiring Problem and Permutations

Archibald, Margaret ; Martínez, Conrado.
The $\textit{hiring problem}$ has been recently introduced by Broder et al. in last year's ACM-SIAM Symp. on Discrete Algorithms (SODA 2008), as a simple model for decision making under uncertainty. Candidates are interviewed in a sequential fashion, each one endowed with a quality score, and […]

An Edge-Signed Generalization of Chordal Graphs, Free Multiplicities on Braid Arrangements, and Their Characterizations

Abe, Takuro ; Nuida, Koji ; Numata, Yasuhide.
In this article, we propose a generalization of the notion of chordal graphs to signed graphs, which is based on the existence of a perfect elimination ordering for a chordal graph. We give a special kind of filtrations of the generalized chordal graphs, and show a characterization of those graphs. […]

Colored Tutte polynomials and composite knots

Hetyei, Gábor ; Diao, Yuanan ; Hinson, Kenneth.
Surveying the results of three recent papers and some currently ongoing research, we show how a generalization of Brylawski's tensor product formula to colored graphs may be used to compute the Jones polynomial of some fairly complicated knots and, in the future, even virtual knots.

Median clouds and a fast transposition median solver

Eriksen, Niklas.
The median problem seeks a permutation whose total distance to a given set of permutations (the base set) is minimal. This is an important problem in comparative genomics and has been studied for several distance measures such as reversals. The transposition distance is less relevant biologically, […]

Enumeration of derangements with descents in prescribed positions

Eriksen, Niklas ; Freij, Ragnar ; Wästlund, Johan.
We enumerate derangements with descents in prescribed positions. A generating function was given by Guo-Niu Han and Guoce Xin in 2007. We give a combinatorial proof of this result, and derive several explicit formulas. To this end, we consider fixed point $\lambda$-coloured permutations, which are […]

Brauer-Schur functions

Aokage, Kazuya.
A new class of functions is studied. We define the Brauer-Schur functions $B^{(p)}_{\lambda}$ for a prime number $p$, and investigate their properties. We construct a basis for the space of symmetric functions, which consists of products of $p$-Brauer-Schur functions and Schur functions. We will see […]

Type B plactic relations for $r$-domino tableaux

Taşkın, Müge.
The recent work of Bonnafé et al. (2007) shows through two conjectures that $r$-domino tableaux have an important role in Kazhdan-Lusztig theory of type $B$ with unequal parameters. In this paper we provide plactic relations on signed permutations which determine whether given two signed […]

Bijections between noncrossing and nonnesting partitions for classical reflection groups

Fink, Alex ; Giraldo, Benjamin Iriarte.
We present $\textit{type preserving}$ bijections between noncrossing and nonnesting partitions for all classical reflection groups, answering a question of Athanasiadis and Reiner. The bijections for the abstract Coxeter types $B$, $C$ and $D$ are new in the literature. To find them we define, for […]

Application of graph combinatorics to rational identities of type $A^\ast$

Boussicault, Adrien ; Féray, Valentin.
To a word $w$, we associate the rational function $\Psi_w = \prod (x_{w_i} - x_{w_{i+1}})^{-1}$. The main object, introduced by C. Greene to generalize identities linked to Murnaghan-Nakayama rule, is a sum of its images by certain permutations of the variables. The sets of permutations that we […]

Bounds of asymptotic occurrence rates of some patterns in binary words related to integer-valued logistic maps

Nuida, Koji.
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 […]

Matrix Ansatz, lattice paths and rook placements

Corteel, S. ; Josuat-Vergès, M. ; Prellberg, T. ; Rubey, M..
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 […]

Characters of symmetric groups in terms of free cumulants and Frobenius coordinates

Dolega, Maciej ; Féray, Valentin ; Sniady, Piotr.
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 […]

A new combinatorial identity for unicellular maps, via a direct bijective approach.

Chapuy, Guillaume.
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 […]

On the Monotone Column Permanent conjecture

Haglund, James ; Visontai, Mirkó.
We discuss some recent progress on the Monotone Column Permanent (MCP) conjecture. We use a general method for proving that a univariate polynomial has real roots only, namely by showing that a corresponding multivariate polynomial is stable. Recent connections between stability of polynomials and […]

Riffle shuffles of a deck with repeated cards

Assaf, Sami ; Diaconis, Persi ; Soundararajan, K..
We study the Gilbert-Shannon-Reeds model for riffle shuffles and ask 'How many times must a deck of cards be shuffled for the deck to be in close to random order?'. In 1992, Bayer and Diaconis gave a solution which gives exact and asymptotic results for all decks of practical interest, e.g. a deck […]

Matroid Polytopes and Their Volumes

Ardila, Federico ; Benedetti, Carolina ; Doker, Jeffrey.
We express the matroid polytope $P_M$ of a matroid $M$ as a signed Minkowski sum of simplices, and obtain a formula for the volume of $P_M$. This gives a combinatorial expression for the degree of an arbitrary torus orbit closure in the Grassmannian $Gr_{k,n}$. We then derive analogous results for […]

Indecomposable permutations with a given number of cycles

Cori, Robert ; Mathieu, Claire.
A permutation $a_1a_2 \ldots a_n$ is $\textit{indecomposable}$ if there does not exist $p \lt n$ such that $a_1a_2 \ldots a_p$ is a permutation of $\{ 1,2, \ldots ,p\}$. We compute the asymptotic probability that a permutation of $\mathbb{S}_n$ with $m$ cycles is indecomposable as $n$ goes to […]

A preorder-free construction of the Kazhdan-Lusztig representations of $S_n$, with connections to the Clausen representations

Buehrle, Charles ; Skandera, Mark.
We use the polynomial ring $\mathbb{C}[x_{1,1},\ldots,x_{n,n}]$ to modify the Kazhdan-Lusztig construction of irreducible $S_n$-modules. This modified construction produces exactly the same matrices as the original construction in [$\textit{Invent. Math}$ $\mathbf{53}$ (1979)], but does not employ […]

Universal cycles for permutation classes

Albert, Michael ; West, Julian.
We define a universal cycle for a class of $n$-permutations as a cyclic word in which each element of the class occurs exactly once as an $n$-factor. We give a general result for cyclically closed classes, and then survey the situation when the class is defined as the avoidance class of a set of […]

Quasipolynomial formulas for the Kronecker coefficients indexed by two two―row shapes (extended abstract)

Briand, Emmanuel ; Orellana, Rosa ; Rosas, Mercedes.
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 […]

Combinatorial formulas for ⅃-coordinates in a totally nonnegative Grassmannian, extended abstract, extended abstract

Talaska, Kelli.
Postnikov constructed a decomposition of a totally nonnegative Grassmannian $(Gr _{kn})_≥0$ into positroid cells. We provide combinatorial formulas that allow one to decide which cell a given point in $(Gr _{kn})_≥0$ belongs to and to determine affine coordinates of the point within this cell. This […]

Unlabeled $(2+2)$-free posets, ascent sequences and pattern avoiding permutations

Bousquet-Mélou, Mireille ; Claesson, Anders ; Dukes, Mark ; Kitaev, Sergey.
We present statistic-preserving bijections between four classes of combinatorial objects. Two of them, the class of unlabeled $(\textrm{2+2})$-free posets and a certain class of chord diagrams (or involutions), already appeared in the literature, but were apparently not known to be equinumerous. The […]

The poset perspective on alternating sign matrices

Striker, Jessica.
Alternating sign matrices (ASMs) are square matrices with entries 0, 1, or -1 whose rows and columns sum to 1 and whose nonzero entries alternate in sign. We put ASMs into a larger context by studying the order ideals of subposets of a certain poset, proving that they are in bijection with a variety […]

The shifted plactic monoid (extended abstract)

Serrano, Luis.
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 […]

A max-flow algorithm for positivity of Littlewood-Richardson coefficients

Bürgisser, Peter ; Ikenmeyer, Christian.
Littlewood-Richardson coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the general linear group $\mathrm{GL}(n,\mathbb{C})$. They have a wide variety of interpretations in combinatorics, representation theory and geometry. Mulmuley and […]

Combinatorial invariant theory of projective reflection groups

Caselli, Fabrizio.
We introduce the class of projective reflection groups which includes all complex reflection groups. We show that several aspects involving the combinatorics and the representation theory of complex reflection groups find a natural description in this wider setting.

$k$-distant crossings and nestings of matchings and partitions

Drake, Dan ; Kim, Jang Soo.
We define and consider $k$-distant crossings and nestings for matchings and set partitions, which are a variation of crossings and nestings in which the distance between vertices is important. By modifying an involution of Kasraoui and Zeng (Electronic J. Combinatorics 2006, research paper 33), we […]

A promotion operator on rigged configurations

Wang, Qiang.
In a recent paper, Schilling proposed an operator $øverline{\mathrm{pr}}$ on unrestricted rigged configurations $RC$, and conjectured it to be the promotion operator of the type $A$ crystal formed by $RC$. In this paper we announce a proof for this conjecture.

Noncrossing partitions and the shard intersection order

Reading, Nathan.
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 […]

Refinements of the Littlewood-Richardson rule

Haglund, J. ; Luoto, K. ; Mason, S. ; van Willigenburg, S..
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 […]

Permutations realized by shifts

Elizalde, Sergi.
A permutation $\pi$ is realized by the shift on $N$ symbols if there is an infinite word on an $N$-letter alphabet whose successive left shifts by one position are lexicographically in the same relative order as $\pi$. The set of realized permutations is closed under consecutive pattern containment. […]

Chip-Firing And A Devil's Staircase

Levine, Lionel.
The devil's staircase ― a continuous function on the unit interval $[0,1]$ which is not constant, yet is locally constant on an open dense set ― is the sort of exotic creature a combinatorialist might never expect to encounter in "real life.'' We show how a devil's staircase arises from the […]

Record statistics in integer compositions

Knopfmacher, Arnold ; Mansour, Toufik.
A $\textit{composition}$ $\sigma =a_1 a_2 \ldots a_m$ of $n$ is an ordered collection of positive integers whose sum is $n$. An element $a_i$ in $\sigma$ is a strong (weak) $\textit{record}$ if $a_i> a_j (a_i \geq a_j)$ for all $j=1,2,\ldots,i-1$. Furthermore, the position of this record is $i$. We […]

Geometry and complexity of O'Hara's algorithm

Konvalinka, Matjaž ; Pak, Igor.
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 […]

Cluster algebras of unpunctured surfaces and snake graphs

Musiker, Gregg ; Schiffler, Ralf.
We study cluster algebras with principal coefficient systems that are associated to unpunctured surfaces. We give a direct formula for the Laurent polynomial expansion of cluster variables in these cluster algebras in terms of perfect matchings of a certain graph $G_{T,\gamma}$ that is constructed […]

A bijection between noncrossing and nonnesting partitions of types A and B

Mamede, Ricardo.
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$, […]

$q$-Hook formula of Gansner type for a generalized Young diagram

Nakada, Kento.
The purpose of this paper is to present the $q$-hook formula of Gansner type for a generalized Young diagram in the sense of D. Peterson and R. A. Proctor. This gives a far-reaching generalization of a hook length formula due to J. S. Frame, G. de B. Robinson, and R. M. Thrall. Furthurmore, we give […]

Another bijection between $2$-triangulations and pairs of non-crossing Dyck paths

Nicolás, Carlos M..
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 […]

Triangulations of root polytopes and reduced forms (Extended abstract)

Mészáros, Karola.
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 […]

Bijective Enumeration of Bicolored Maps of Given Vertex Degree Distribution

Morales, Alejandro ; Vassilieva, Ekaterina.
We derive a new formula for the number of factorizations of a full cycle into an ordered product of two permutations of given cycle types. For the first time, a purely combinatorial argument involving a bijective description of bicolored maps of specified vertex degree distribution is used. All the […]

Election algorithms with random delays in trees

Marckert, Jean-François ; Saheb-Djahromi, Nasser ; Zemmari, Akka.
The election is a classical problem in distributed algorithmic. It aims to design and to analyze a distributed algorithm choosing a node in a graph, here, in a tree. In this paper, a class of randomized algorithms for the election is studied. The election amounts to removing leaves one by one until […]

Hopf algebras and the logarithm of the S-transform in free probability ― Extended abstract

Mastnak, Mitja ; Nica, Alexandru.
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.

The Discrete Fundamental Group of the Associahedron

Severs, Christopher ; White, Jacob.
The associahedron is an object that has been well studied and has numerous applications, particularly in the theory of operads, the study of non-crossing partitions, lattice theory and more recently in the study of cluster algebras. We approach the associahedron from the point of view of discrete […]

Macdonald polynomials at $t=q^k$

Luque, Jean-Gabriel.
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 […]

On $k$-simplexes in $(2k-1)$-dimensional vector spaces over finite fields

Vinh, Le Anh.
We show that if the cardinality of a subset of the $(2k-1)$-dimensional vector space over a finite field with $q$ elements is $\gg q^{2k-1-\frac{1}{ 2k}}$, then it contains a positive proportional of all $k$-simplexes up to congruence.

An immanant formulation of the dual canonical basis of the quantum polynomial ring

Skandera, Mark ; Lambright, Justin.
We show that dual canonical basis elements of the quantum polynomial ring in $n^2$ variables can be expressed as specializations of dual canonical basis elements of $0$-weight spaces of other quantum polynomial rings. Our results rely upon the natural appearance in the quantum polynomial ring of […]

Combinatorial Formula for the Hilbert Series of bigraded $S_n$-modules

Yoo, Meesue.
We introduce a combinatorial way of calculating the Hilbert series of bigraded $S_n$-modules as a weighted sum over standard Young tableaux in the hook shape case. This method is based on Macdonald formula for Hall-Littlewood polynomial and extends the result of $A$. Garsia and $C$. Procesi for the […]

Infinite log-concavity: developments and conjectures

McNamara, Peter R. W. ; Sagan, Bruce E..
Given a sequence $(a_k)=a_0,a_1,a_2,\ldots$ of real numbers, define a new sequence $\mathcal{L}(a_k)=(b_k)$ where $b_k=a_k^2-a_{k-1}a_{k+1}$. So $(a_k)$ is log-concave if and only if $(b_k)$ is a nonnegative sequence. Call $(a_k)$ $\textit{infinitely log-concave}$ if $\mathcal{L}^i(a_k)$ is […]

Permutations with Kazhdan-Lusztig polynomial $ P_id,w(q)=1+q^h$

Woo, Alexander.
Using resolutions of singularities introduced by Cortez and a method for calculating Kazhdan-Lusztig polynomials due to Polo, we prove the conjecture of Billey and Braden characterizing permutations w with Kazhdan-Lusztig polynomial$ P_id,w(q)=1+q^h$ for some $h$.

On undecidability of equicontinuity classification for cellular automata

,  ; Formenti, Enrico ; Varouchas, Georges.
Equicontinuity classification is a popular classification of cellular automata based on their dynamical behavior. In this paper we prove that most of its classes are undecidable.

Number conserving cellular automata: new results on decidability and dynamics

,  ; Formenti, Enrico ; Grange, Aristide ; Róka, Zsuzsanna.
This paper is a survey on our recent results about number conserving cellular automata. First, we prove the linear time decidability of the property of number conservation. The sequel focuses on dynamical evolutions of number conserving cellular automata.

Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

Barrett, Christopher L. ; Hunt, Harry,  ; Marathe, Madhav V. ; Ravi, S. S. ; Rosenkrantz, Daniel J. ; Stearns, Richard E..
A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was introduced in [BR99] as a formal model for analyzing simulation systems. Here, we address the complexity of two basic problems and their generalizations for SDSs.Given an SDS $\mathcal{S}$ and a […]

Optimal Nonlinear Prediction of Random Fields on Networks

Shalizi, Cosma Rohilla.
It is increasingly common to encounter time-varying random fields on networks (metabolic networks, sensor arrays, distributed computing, etc.).This paper considers the problem of optimal, nonlinear prediction of these fields, showing from an information-theoretic perspective that it is formally […]

Cellular Automata for Simulating Molecular Self-Assembly

Nilsson, Martin ; Rasmussen, Steen.
We present a lattice gas technique for simulating molecular self-assembly of amphiphilic polymers in aqueous environments. Water molecules, hydrocarbons tail-groups and amphiphilic head-groups are explicitly represented on a three dimensional discrete lattice. Molecules move on the lattice […]

Results and conjectures on the Sandpile Identity on a lattice

Dartois, Arnaud ; Magnien, Clémence.
In this paper we study the identity of the Abelian Sandpile Model on a rectangular lattice.This configuration can be computed with the burning algorithm, which, starting from the empty lattice, computes a sequence of configurations, the last of which is the identity.We extend this algorithm to an […]

Formalizing the transformations of a cognitive universe

Lafaye de Micheaux, N. ; López, G. ; Vitiello, P. ; Beauvois, J. L..
In an effort to continue the pioneering work of Harary in USA and Flament in France, we have undertaken to develop, on an experimental basis, a formalized theory of systems of beliefs and their modifications. This theory uses the psycho-social concepts of theories of cognitive consistency and of the […]

Experimental study of Elementary Cellular Automata dynamics using the density parameter

Fatès, Nazim, .
Classifying cellular automata in order to capture the notion of chaos algorithmically is a challenging problem than can be tackled in many ways.We here give a classification based on the computation of a macroscopic parameter, the $d$-spectrum, and show how our classifying scheme can be used to […]

Dynamics of the Picking transformation on integer partitions

Phan, Thi Ha Duong ; Thierry, Eric.
This paper studies a conservative transformation defined on families of finite sets. It consists in removing one element from each set and adding a new set composed of the removed elements. This transformation is conservative in the sense that the union of all sets of the family always remains the […]

A symbolic projection of Langton's Ant

Gajardo, Anahi.
The Langton's ant is studied from the point of view of topological dynamical systems. A new approach which associate a subshift to the system is proposed.The transition rule is generalized to the family of bi-regular graphs $\Gamma(k,d)$ and the dependence of the dynamical system on $k$ and $d$ is […]

A Reciprocity Theorem for Monomer-Dimer Coverings

Anzalone, Nick ; Baldwin, John ; Bronshtein, Ilya ; Petersen, Kyle, .
The problem of counting monomer-dimer coverings of a lattice is a longstanding problem in statistical mechanics.It has only been exactly solved for the special case of dimer coverings in two dimensions ([Ka61], [TF61]). In earlier work, Stanley [St85] proved a reciprocity principle governing the […]

Evidence for intermittency in a granular medium: experiments and simulations.

Schmick, Malte ; Markus, Mario.
We present the first experimental demonstration of intermittency in a granular medium. The medium consists of magnets embedded within spheres. These spheres are placed in a horizontal Petri dish where they roll by virtue of an alternating, homogenous magnetic field. Due to collisions with the wall, […]

Enumeration of convex polyominoes using the ECO method

Del Lungo, A. ; Duchi, E. ; Frosini, A. ; Rinaldi, S..
ECO is a method for the enumeration of classes of combinatorial objects based on recursive constructions of such classes. In the first part of this paper we present a construction for the class of convex polyominoes based on the ECO method. Then we translate this construction into a succession rule. […]

Tiling a Rectangle with Polyominoes

Bodini, Olivier.
A polycube in dimension $d$ is a finite union of unit $d$-cubes whose vertices are on knots of the lattice $\mathbb{Z}^d$. We show that, for each family of polycubes $E$, there exists a finite set $F$ of bricks (parallelepiped rectangles) such that the bricks which can be tiled by $E$ are exactly […]

Cellular Lines: An Introduction

Geer, Panama ; McLaughlin, Harry W. ; Unsworth, Keith.
This paper provides a definition of a cellular line in a cellular array that is independent of the notion of a line in $\mathfrak{R}^2$.It also presents a way of determining whether or not a cell set is a cellular line.Brief statements about existence, uniqueness, and properties of cellular lines […]

Tiling the Line with Triples

Meyerowitz, Aaron.
It is known the one dimensional prototile $0,a,a+b$ and its reflection $0,b,a+b$ always tile some interval. The subject has not received a great deal of further attention, although many interesting questions exist. All the information about tilings can be encoded in a finite digraph $D_{ab}$. We […]

Characterization of Lattices Induced by (extended) Chip Firing Games

Magnien, Clémence ; Phan, Ha Duong ; Vuillon, Laurent.
The Chip Firing Game (CFG) is a discrete dynamical model used in physics, computer science and economics. It is known that the set of configurationsreachable from an initial configuration (this set is called the \textitconfiguration space) can be ordered as a lattice. We first present a structural […]

On the Toppling of a Sand Pile

Novelli, Jean-Christophe ; Rossin, Dominique.
In this paper, we provide the first study of the sand pile model SPM(0) where we assume that all the grains are numbered with a distinct integer.We obtain a lower bound on the number of terminal sand piles by establishing a bijection between a subset of these sand piles and the set of shifted Young […]

Tilings of a Domain on a Hexagon Mesh with Balanced 3-Tiles

Radenne, Gilles.
In this article, we study the question of tilings on a hexagon mesh with balanced 3-tiles. This problem has been studied by Conway and Lagarias in [CL90], by studying the tiling groups, in fact a group containing the tiling-groups, and their Cayley graphs. We will use two different approaches. The […]

Megamaps: Construction and Examples

Zvonkin, Alexander.
We consider the usual model of hypermaps or, equivalently, bipartite maps, represented by pairs of permutations that act transitively on a set of edges E. The specific feature of our construction is the fact that the elements of E are themselves (or are labelled by) rather complicated combinatorial […]

The Chip Firing Game and Matroid Complexes

Merino, Criel.
In this paper we construct from a cographic matroid M, a pure multicomplex whose degree sequence is the h―vector of the the matroid complex of M. This result provesa conjecture of Richard Stanley [Sta96] in the particular case of cographic matroids. We also prove that the multicomplexes constructed […]

Gardens of Eden and Fixed Points in Sequential Dynamical Systems

Barrett, Christopher ,  ; Hunt, Marry,  ; Marathe, Madhav,  ; Ravi, S.,  ; Rosenkrantz, Daniel,  ; Stearns, Richard,  ; Tosic, Predrag, .
A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was proposed in [BMR99,BR99] as an abstract model of computer simulations. Here, we address some questions concerning two special types of the SDS configurations, namely Garden of Eden and Fixed Point […]

Tilings, Quasicrystals, Discrete Planes, Generalized Substitutions, and Multidimensional Continued Fractions

Arnoux, Pierre ; Berthe, Valerie ; Ei, Hiromi ; Ito, Shunji.
The aim of this paper is to give an overview of recent results about tilings, discrete approximations of lines and planes, and Markov partitions for toral automorphisms.The main tool is a generalization of the notion of substitution. The simplest examples which correspond to algebraic parameters, […]

Periodic Patterns in Orbits of Certain Linear Cellular Automata

Barbé, André ; Haeseler, Fritz, .
We discuss certain linear cellular automata whose cells take values in a finite field. We investigate the periodic behavior of the verticals of an orbit of the cellular automaton and establish that there exists, depending on the characteristic of the field, a universal behavior for the evolution of […]

Larger than Life: Digital Creatures in a Family of Two-Dimensional Cellular Automata

Evans, Kellie M..
We introduce the Larger than Life family of two-dimensional two-state cellular automata that generalize certain nearest neighbor outer totalistic cellular automaton rules to large neighborhoods. We describe linear and quadratic rescalings of John Conway's celebrated Game of Life to these large […]

A Poset Classifying Non-Commutative Term Orders

Snellman, Jan.
We study a poset $\Re$ on the free monoid (X*) on a countable alphabet X.This poset is determined by the fact that its total extensions are precisely the standard term orders on X*. We also investigate the poset classifying degree-compatible standard term orders, and the poset classifying sorted […]

Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis

Thiéry, Nicolas, .
We present a characteristic-free algorithm for computing minimal generating sets of invariant rings of permutation groups. We circumvent the main weaknesses of the usual approaches (using classical Gröbner basis inside the full polynomial ring, or pure linear algebra inside the invariant ring) by […]

On Minimal Strings Containing the Elements of S_n by Decimation

Erra, Robert ; Lygeros, Nik ; Stewart, Nigel.
The permutations by decimation problem is thought to be applicable to computer graphics, and raises interesting theoretical questions in combinatory theory.We present the results of some theoretical and practical investigation into this problem.We show that sequences of this form are $O(n^2)$ in […]

A Bijection for Directed-Convex Polyominoes

Del Lungo, Alberto ; Mirolli, Massimo ; Pinzani, Renzo ; Rinaldi, Simone.
In this paper we consider two classes of lattice paths on the plane which use \textitnorth, \textiteast, \textitsouth,and \textitwest unitary steps, beginningand ending at (0,0).We enumerate them according to the number ofsteps by means of bijective arguments; in particular, we apply the cycle […]

Mixing Times of Plane Random Rhombus Tilings

Destainville, Nicolas.
We address the question of single flip discrete dynamics in sets of two-dimensional random rhombus tilings with fixed polygonal boundaries. Single flips are local rearrangements of tiles which enable to sample the configuration sets of tilings via Markov chains. We determine the convergence rates of […]

Pseudo-Permutations II: Geometry and Representation Theory

Boulier, François ; Hivert, Florent ; Krob, Daniel ; Novelli, Jean-Christophe.
In this paper, we provide the second part of the study of the pseudo-permutations. We first derive a complete analysis of the pseudo-permutations, based on hyperplane arrangements, generalizing the usual way of translating the permutations. We then study the module of the pseudo-permutations over […]

New Bounds for Hypercube Slicing Numbers

Emamy-Khansary, M. Reza ; Ziegler, Martin.
What is the maximum number of edges of the d-dimensional hypercube, denoted by S(d,k), that can be sliced by k hyperplanes? This question on combinatorial properties of Euclidean geometry arising from linear separability considerations in the theory of Perceptrons has become an issue on its own. We […]

Partitions of an Integer into Powers

Latapy, Matthieu.
In this paper, we use a simple discrete dynamical model to study partitions of integers into powers of another integer. We extend and generalize some known results about their enumeration and counting, and we give new structural results. In particular, we show that the set of these partitions can be […]

Performance Evaluation of Demodulation Methods: a Combinatorial Approach

Krob, Daniel ; Vassilieva, Ekaterina A..
This paper provides a combinatorial approach for analyzing the performance of demodulation methods used in GSM. We also show how to obtain combinatorially a nice specialization of an important performance evaluation formula, using its connection with a classical bijection of Knuth between pairs of […]

A Sequential Search Distribution: Proofreading, Russian Roulette, and the Incomplete q-Eulerian Polynomials

Herbranson, Travis ; Rawlings, Don.
The distribution for the number of searches needed to find k of n lost objects is expressed in terms of a refinement of the q-Eulerian polynomials, for which formulae are developed involving homogeneous symmetric polynomials. In the case when k=n and the find probability remains constant, relatively […]

The Many Faces of Alternating-Sign Matrices

Propp, James.
I give a survey of different combinatorial forms of alternating-sign matrices, starting with the original form introduced by Mills, Robbins and Rumsey as well as corner-sum matrices, height-function matrices, three-colorings, monotone triangles, tetrahedral order ideals, square ice, […]

An n-Dimensional Generalization of the Rhombus Tiling

Linde, Joakim ; Moore, Cristopher ; Nordahl, Mats G..
Several classic tilings, including rhombuses and dominoes, possess height functions which allow us to 1) prove ergodicity and polynomial mixing times for Markov chains based on local moves, 2) use coupling from the past to sample perfectly random tilings, 3) map the statistics of random tilings at […]

Representing Reversible Cellular Automata with Reversible Block Cellular Automata

Durand-Lose, Jérôme.
Cellular automata are mappings over infinite lattices such that each cell is updated according tothe states around it and a unique local function.Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in […]

Enumerating Triangulations of Convex Polytopes

Bespamyatnikh, Sergei.
A triangulation of a finite point set A in $\mathbb{R}^d$ is a geometric simplicial complex which covers the convex hull of $A$ and whose vertices are points of $A$. We study the graph of triangulations whose vertices represent the triangulations and whose edges represent geometric bistellar flips. […]