Proceedings

Sign variation, the Grassmannian, and total positivity

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)

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

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

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

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}$

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

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$

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

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)

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

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

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

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)

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

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

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

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

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

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$

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)

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 […]

Bruhat interval polytopes

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

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

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

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

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

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)

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)

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 ?

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

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

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

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

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$

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 […]

Cycles and sorting index for matchings and restricted permutations

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

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

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

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

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

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

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

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 […]

Generalized monotone triangles

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

\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

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

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

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

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

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

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

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^*$

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

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

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

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

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

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

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

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 […]

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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 […]

Joint String Complexity for Markov Sources

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

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

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)

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

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

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

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

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)

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

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

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

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

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

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

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

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

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 […]

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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)

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)

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 […]

Counting Shi regions with a fixed separating wall

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

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)

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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$

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 […]

Enumeration of inscribed polyominos

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

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

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 […]

Square root singularities of infinite systems of functional equations

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

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

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

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

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)

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

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

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

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

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

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)

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

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

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

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 Formulas for Macdonald and Hall-Littlewood Polynomials

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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$

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

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

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

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.

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

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

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

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

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

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

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)

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

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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$

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

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

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

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

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$

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

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

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.

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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