Philippe Nadeau

We develop a quasisymmetric analogue of the theory of Schubert cycles, building off of our previous work on a quasisymmetric analogue of Schubert polynomials and divided differences. Our constructions result in a natural geometric interpretation for the ring of quasisymmetric coinvariants.

We give an elementary approach utilizing only the divided difference formalism for obtaining expansions of Schubert polynomials that are manifestly nonnegative, by studying solutions to the equation ∑Yi∂i=id on polynomials with no constant term. This in particular recovers the pipe dream and slide polynomial expansions. We also show that slide polynomials satisfy an analogue of the divided difference formalisms for Schubert polynomials and forest polynomials, which gives a simple method for extracting the coefficients of slide polynomials in the slide polynomial decomposition of an arbitrary polynomial.

We develop a quasisymmetric analogue of the combinatorial theory of Schubert polynomials and the associated divided difference operators. Our counterparts are "forest polynomials", and a new family of linear operators, whose theory of compositions is governed by forests and the "Thompson monoid". Our approach extends naturally to m-colored quasisymmetric functions. We then give several applications of our theory to fundamental quasisymmetric functions, the study of quasisymmetric coinvariant rings and their associated harmonics, and positivity results for various expansions. In particular we resolve a conjecture of Aval-Bergeron-Li regarding quasisymmetric harmonics.

There is a striking similarity between Macdonald's reduced word formula and the image of the Schubert class in the cohomology ring of the permutahedral variety Permn as computed by Klyachko. Toward understanding this better, we undertake an in-depth study of a q-deformation of the Sn-invariant part of the rational cohomology ring of Permn, which we call the q-Klyachko algebra. We uncover intimate links between expansions in the basis of squarefree monomials in this algebra and various notions in algebraic combinatorics, thereby connecting seemingly unrelated results by finding a common ground to study them.

Our main results are as follows. 1) A q-analog of divided symmetrization (q-DS) using Yang-Baxter elements in the Hecke algebra. It is a linear form that picks up coefficients in the squarefree basis. 2) A relation between q-DS and the ideal of quasisymmetric polynomials involving work of Aval--Bergeron--Bergeron. 3) A family of polynomials in q with nonnegative integral coefficients that specialize to Postnikov's mixed Eulerian numbers when q=1. We refer to these new polynomials as remixed Eulerian numbers. For q>0, their normalized versions occur as probabilities in the internal diffusion limited aggregation (IDLA) stochastic process. 4) A lift of Macdonald's reduced word identity in the q-Klyachko algebra. 5) The Schubert expansion of the Chow class of the standard split Deligne--Lusztig variety in type A, when q is a prime power.

We introduce a simple bijection between Tamari intervals and the blossoming trees (Poulalhon and Schaeffer, 2006) encoding planar triangulations, using a new meandering representation of such trees. Its specializations to the families of synchronized, Kreweras, new/modern, and infinitely modern intervals give a combinatorial proof of the counting formula for each family. Compared to (Bernardi and Bonichon, 2009), our bijection behaves well with the duality of Tamari intervals, enabling also the counting of self-dual intervals.

We establish Guay-Paquet's unpublished linear relation between certain chromatic symmetric functions by relating his algebra on paths to the q-Klyachko algebra. The coefficients in this relations are q-hit polynomials, and they come up naturally in our setup as connected remixed Eulerian numbers, in contrast to the computational approach of Colmenarejo-Morales-Panova. As Guay-Paquet's algebra is a down-up algebra, we are able to harness algebraic results in the context of the latter and establish results of a combinatorial flavour. In particular we resolve a conjecture of Colmenarejo-Morales-Panova on chromatic symmetric functions. This concerns the abelian case of the Stanley-Stembridge conjecture, which we briefly survey.

We study a basis of the polynomial ring that we call forest polynomials. This family of polynomials is indexed by a combinatorial structure called indexed forests and permits several definitions, one of which involves flagged P-partitions. As such, these polynomials have a positive expansion in the basis of slide polynomials. By a novel insertion procedure that may be viewed as a generalization of the Sylvester correspondence we establish that Schubert polynomials decompose positively in terms of forest polynomials. Our insertion procedure involves a correspondence on words which allows us to show that forest polynomials multiply positively. We proceed to show that forest polynomials are a particularly convenient basis in regards to studying the quotient of the polynomial ring modulo the ideal of positive degree quasisymmetric polynomials. This aspect allows us to give a manifestly nonnegative integral description for the Schubert class expansion of the cohomology class of the permutahedral variety in terms of a parking procedure. We study the associated combinatorics in depth and introduce a multivariate extension of mixed Eulerian numbers.

We provide a combinatorial interpretation of the symmetric function $\Theta_{e_k}\Theta_{e_l}\nabla e_{n-k-l}\right|_{t=0}$ in terms of segmented Smirnov words. The motivation for this work is the study of a diagonal coinvariant ring with one set of commuting and two sets of anti-commuting variables, whose Frobenius characteristic is conjectured to be the symmetric function in question. Furthermore, this function is related to the Delta conjectures. Our work is a step towards a unified formulation of the two versions, as we prove a unified Delta theorem at $t=0$.

Stanley's theory of (P,ω)-partitions is a standard tool in combinatorics. It can be extended to allow for the presence of a restriction, that is a given maximal value for partitions at each vertex of the poset, as was shown by Assaf and Bergeron. Here we present a variation on their approach, which applies more generally. The enumerative side of the theory is more naturally expressed in terms of back stable quasisymmetric functions. We study the space of such functions, following the work of Lam, Lee and Shimozono on back stable symmetric functions. As applications we describe a new basis for the ring of polynomials that we call forest polynomials. Additionally we give a signed multiplicity-free expansion for any monomial expressed in the basis of slide polynomials.

The Wiener index of a finite graph G is the sum over all pairs (p, q) of vertices of G of the distance between p and q. When P is a finite poset, we define its Wiener index as the Wiener index of the graph of its Hasse diagram. In this paper, we find exact expressions for the Wiener indices of the distributive lattices of order ideals in minuscule posets. For infinite families of such posets, we also provide results on the asymptotic distribution of the distance between two random order ideals.

The dual braid monoid was introduced by Bessis in his work on complex reflection arrangements. The goal of this work is to show that Koszul duality provides a nice interplay between the dual braid monoid and the cluster complex introduced by Fomin and Zelevinsky. Firstly, we prove koszulity of the dual braid monoid algebra, by building explicitly the minimal free resolution of the ground field. This is done explicitly using some chains complexes defined in terms of the positive part of the cluster complex. Secondly, we derive various properties of the quadratic dual algebra. We show that it is naturally graded by the noncrossing partition lattice. We get an explicit basis, naturally indexed by positive faces of the cluster complex. Moreover, we find the structure constants via a geometric rule in terms of the cluster fan. Eventually, we realize this dual algebra as a quotient of a Nichols algebra. This latter fact makes a connection with results of Zhang, who used the same algebra to compute the homology of Milnor fibers of reflection arrangements.

Remixed Eulerian numbers are a polynomial q-deformation of Postnikov's mixed Eulerian numbers. They arose naturally in previous work by the authors concerning the permutahedral variety and subsume well-known families of polynomials such as q-binomial coefficients and Garsia--Remmel's q-hit numbers. We study their combinatorics in more depth. As polynomials in q, they are shown to be symmetric and unimodal. By interpreting them as computing success probabilities in a simple probabilistic process we arrive at a combinatorial interpretation involving weighted trees. By decomposing the permutahedron into certain combinatorial cubes, we obtain a second combinatorial interpretation. At q=1, the former recovers Postnikov's interpretation whereas the latter recovers Liu's interpretation, both of which were obtained via methods different from ours.

We compute the expansion of the cohomology class of the permutahedral variety in the basis of Schubert classes. The resulting structure constants aw are expressed as a sum of normalized mixed Eulerian numbers indexed naturally by reduced words of w. The description implies that the aw are positive for all permutations w in S_n of length n−1, thereby answering a question of Harada, Horiguchi, Masuda and Park. We use the same expression to establish the invariance of aw under taking inverses and conjugation by the longest word, and subsequently establish an intriguing cyclic sum rule for the numbers. We then move toward a deeper combinatorial understanding for the a_w by exploiting in addition the relation to Postnikov's divided symmetrization. Finally, we are able to give a combinatorial interpretation for a_w when w is vexillary, in terms of certain tableau descents. It is based in part on a relation between the numbers a_w and principal specializations of Schubert polynomials. Along the way, we prove results and raise questions of independent interest about the combinatorics of permutations, Schubert polynomials and related objects.

We define a new disordered asymmetric simple exclusion process (ASEP) with two species of particles, on a two-dimensional toroidal lattice. The dynamics is controlled by first-class particles, which only move horizontally, with forward and backward hopping rates pi and qi respectively if the first-class particle is on row i. The motion of second-class particles depends on the relative position of these with respect to first-class particles, and can be both horizontal and vertical. We show that the stationary weight of any configuration is proportional to a monomial in the pi's and qi's. Our process projects to the disordered ASEP on a ring, and so explains combinatorially the stationary distribution of the latter first derived by Evans (Europhysics Letters, 1996). We compute the partition function, as well as densities and currents in the stationary state. We observe a novel mechanism we call the Scott Russell phenomenon: the current of second-class particles in the vertical direction is the same as that of first-class particles in the horizontal direction.

Motivated by a question in Schubert calculus, we study various aspects of the divided symmetrization operator, which was introduced by Postnikov in the context of volume polynomials of permutahedra. Divided symmetrization is a linear form which acts on the space of polynomials in n indeterminates of degree n−1. Our main results are related to quasisymmetric polynomials: First, we show that divided symmetrization applied to a quasisymmetric polynomial in m indeterminates has a natural interpretation. Then, that the divided symmetrization of any polynomial can be naturally computed with respect to a direct sum decomposition due to Aval-Bergeron-Bergeron, involving the ideal generated by positive degree quasisymmetric polynomials in n indeterminates. Several examples with a strong combinatorial flavor are given.

We study the Schur polynomial expansion of a family of symmetric polynomials related to the refined enumeration of alternating sign matrices with respect to their inversion number, complementary inversion number and the position of the unique 1 in the top row. We prove that the expansion can be expressed as a sum over totally symmetric plane partitions and we are also able to determine the coefficients. This establishes a new connection between alternating sign matrices and a class of plane partitions, thereby complementing the fact that alternating sign matrices are equinumerous with totally symmetric self-complementary plane partitions as well as with descending plane partitions. As a by-product we obtain an interesting map from totally symmetric plane partitions to Dyck paths. The proof is based on a new, quite general antisymmetrizer-to-determinant formula.

For a fixed integer k, we consider the set of noncrossing partitions, where both the block sizes and the difference between adjacent elements in a block is 1 mod k. We show that these k-indivisible noncrossing partitions can be recovered in the setting of subgroups of the symmetric group generated by (k+1)-cycles, and that the poset of k-indivisible noncrossing partitions under refinement order has many beautiful enumerative and structural properties. We encounter k-parking functions and some special Cambrian lattices on the way, and show that a special class of lattice paths constitutes a nonnesting analogue.

Let G be a graph, and let χG be its chromatic polynomial. For any non-negative integers i, j, we give an interpretation for the evaluation χG⁽ⁱ⁾(-j) in terms of acyclic orientations. This recovers the classical interpretations due to Stanley and to Green and Zaslavsky respectively in the cases i = 0 and j = 0. We also give symmetric function refinements of our interpretations, and some extensions. The proofs use heap theory in the spirit of a 1999 paper of Gessel.

We investigate the poset structure on the alternating group which arises when the latter is generated by 3-cycles. We study intervals in this poset and give several enumerative results, as well as a complete description of the orbits of the Hurwitz action on maximal chains. Our motivating example is the well-studied absolute order arising when the symmetric group is generated by transpositions, i.e. 2-cycles, and we compare our results to this case along the way. In particular, noncrossing partitions arise naturally in both settings.

We study 321-avoiding affine permutations, and prove a formula for their enumeration with respect to the inversion number by using a combinatorial approach. This is done in two different ways, both related to Viennot's theory of heaps. First, we encode these permutations using certain heaps of monomers and dimers. This method specializes to the case of affine involutions. For the second proof, we introduce periodic parallelogram polyominoes, which are new combinatorial objects of independent interest. We enumerate them by extending the approach of Bousquet-Mélou and Viennot used for classical parallelogram polyominoes. We finally establish a connection between these new objects and 321-avoiding affine permutations.

An element w of a Coxeter group W is said to be fully commutative, if any reduced expression of w can be obtained from any other by transposing adjacent pairs of generators. These elements were described in 1996 by Stembridge in the case of finite irreducible groups, and more recently by Biagioli, Jouhet and Nadeau (BJN) in the affine cases. We focus here on the length enumeration of these elements. Using a recursive description, BJN established for the associated generating functions systems of non-linear q-equations. Here, we show that an alternative recursive description leads to explicit expressions for these generating functions.

We obtain an alternative combinatorial description of Igusa's cubical categories of noncrossing partitions, using various classes of trees. We also count the morphisms in these categories, according to the ranks of the source and target objects.

In a Coxeter group W, an element is fully commutative if any two of its reduced expressions can be linked by a series of commutation of adjacent letters. These elements have particularly nice combinatorial properties, and also index a basis of the generalized Temperley--Lieb algebra attached to W.
We give two results about the sequence counting these elements with respect to their Coxeter length. First we prove that it always satisfies a linear recurrence with constant coefficients, by showing that reduced expressions of fully commutative elements form a regular language. Then we classify those groups W for which the sequence is ultimately periodic, extending a result of Stembridge. These results are applied to the growth of generalized Temperley--Lieb algebras.

In this article, we introduce and investigate a class of finite deterministic automata that all recognize the language of reduced words of a finitely generated Coxeter system (W,S). The definition of these automata is straightforward as it only requires the notion of weak order on (W,S) and the related notion of Garside shadows in (W,S), an analog of the notion of a Garside family. Then we discuss the relations between this class of automata and the canonical automaton built from Brink and Howlett's small roots. We end this article by providing partial positive answers to two conjectures: (1) the automata associated to the smallest Garside shadow is minimal; (2) the canonical automaton is minimal if and only if the support of all small roots is spherical, i.e., the corresponding root system is finite.

In [1], the authors consider a random walk in Z ^K+1 with the constraint that each coordinate of the walk is at distance one from the following one. A functional central limit theorem for the first coordinate is proved and the limit variance is explicited. In this paper, we study an extended version of this model by conditioning the extremal coordinates to be at some fixed distance at every time. We prove a functional central limit theorem for this random walk. Using combinatorial tools, we give a precise formula of the variance and compare it with the one obtained in [1]

An element of a Coxeter group W is called fully commutative if any two of its reduced decompositions can be related by a series of transpositions of adjacent commuting generators. In the preprint "Fully commutative elements in finite and affine Coxeter groups" (arXiv:1402.2166), R. Biagioli and the authors proved among other things that, for each irreducible affine Coxeter group, the sequence counting fully commutative elements with respect to length is ultimately periodic. In the present work, we study this sequence in its periodic part for each of these groups, and in particular we determine the minimal period. We also observe that in type A affine we get an instance of the cyclic sieving phenomenon.

An element of a Coxeter group W is fully commutative if any two of its reduced decompositions are related by a series of transpositions of adjacent commuting generators. These elements were extensively studied by Stembridge, in particular in the finite case. They index naturally a basis of the generalized Temperley--Lieb algebra. In this work we deal with any finite or affine Coxeter group W, and we give explicit descriptions of fully commutative elements. Using our characterizations we then enumerate these elements according to their Coxeter length, and find in particular that the corrresponding growth sequence is ultimately periodic in each type. When the sequence is infinite, this implies that the associated Temperley--Lieb algebra has linear growth.

An element of a Coxeter group WW is fully commutative if any two of its reduced decompositions are related by a series of transpositions of adjacent commuting generators. In the present work, we focus on fully commutative involutions, which are characterized in terms of Viennot’s heaps. By encoding the latter by Dyck-type lattice walks, we enumerate fully commutative involutions according to their length, for all classical finite and affine Coxeter groups. In the finite cases, we also find explicit expressions for their generating functions with respect to the major index. Finally in affine type AA, we connect our results to Fan–Green’s cell structure of the corresponding Temperley–Lieb algebra.

Triangular fully packed loop configurations (TFPLs) emerged as auxiliary objects in the study of fully packed loop configurations on a square (FPLs) corresponding to link patterns with a large number of nested arches. Wieland gyration, on the other hand, was invented to show the rotational invariance of the numbers Aπ of FPLs corresponding to a given link pattern π. The focus of this article is the definition and study of Wieland gyration on TFPLs. We show that the repeated application of this gyration eventually leads to a configuration that is left invariant. We also provide a characterization of such stable configurations. Finally we apply our gyration to the study of TFPL configurations, in particular giving new and simple proofs of several results.

Fully Packed Loop configurations in a triangle (TFPLs) first appeared in the study of ordinary Fully Packed Loop configurations (FPLs) on the square grid where they were used to show that the number of FPLs with a given link pattern that has m nested arches is a polynomial function in m. It soon turned out that TFPLs possess a number of other nice properties. For instance, they can be seen as a generalized model of Littlewood-Richardson coefficients. We start our article by introducing oriented versions of TFPLs; their main advantage in comparison with ordinary TFPLs is that they involve only local constraints. Three main contributions are provided. Firstly, we show that the number of ordinary TFPLs can be extracted from a weighted enumeration of oriented TFPLs and thus it suffices to consider the latter. Secondly, we decompose oriented TFPLs into two matchings and use a classical bijection to obtain two families of nonintersecting lattice paths (path tangles). This point of view turns out to be extremely useful for giving easy proofs of previously known conditions on the boundary of TFPLs necessary for them to exist. One example is the inequality d(u)+d(v)<=d(w) where u,v,w are 01-words that encode the boundary conditions of ordinary TFPLs and d(u) is the number of cells in the Ferrers diagram associated with u. In the third part we consider TFPLs with d(w)- d(u)-d(v)=0,1; in the first case their numbers are given by Littlewood-Richardson coefficients, but also in the second case we provide formulas that are in terms of Littlewood-Richardson coefficients. The proofs of these formulas are of a purely combinatorial nature.

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 tree-like tableaux of size n are counted by n! and which moreover respects most of the well-known statistics studied originally on alternative and permutation tableaux. Our insertion procedure allows to define in particular two simple new bijections between tree-like tableaux and permutations: the first one is conceived specifically to respect the generalized pattern 2-31, while the second one respects the underlying tree of a tree-like tableau.

Fully Packed Loop configurations (FPLs) are certain configurations on the square grid, naturally refined according to certain link patterns. If $A_X$ is the number of FPLs with link pattern $X$, the Razumov--Stroganov correspondence provides relations between numbers $A_X$ relative to a given grid size. In another line of research, if $X\cup p$ denotes $X$ with $p$ additional nested arches, then $A_{X\cup p}$ was shown to be polynomial in $p$: the proof gives rise to certain configurations of FPLs in a triangle (TFPLs). In this work we investigate these TFPL configurations and their relation to FPLs. We prove certain properties of TFPLs, and enumerate them under special boundary conditions. From this study we deduce a class of linear relations, conjectured by Thapper, between quantities $A_X$ relative to different grid sizes, relations which thus differ from the Razumov--Stroganov ones.

In this work we continue our study of Fully Packed Loop (FPL) configurations in a triangle. These are certain subgraphs on a triangular subset of the square lattice, which first arose in the study of the usual FPL configurations on a square grid. We show that, in a special case, the enumeration of these FPLs in a triangle is given by Littlewood-Richardson coefficients. The proof consists of a bijection with Knutson-Tao puzzles.

We give an extension of the famous Schensted correspondence to the case of ribbon tableaux, where ribbons are allowed to be of different sizes. This is done by extending Fomin’s growth diagram approach of the classical correspondence, in particular by allowing signs in the enumeration. As an application, we give in particular a combinatorial proof, based on the Murnaghan–Nakayama rule, for the evaluation of the column sums of the character table of the symmetric group.

In this paper we study alternative tableaux introduced by Viennot. These tableaux are in simple bijection with permutation tableaux, defined previously by Postnikov. We exhibit a simple recursive structure for alternative tableaux. From this decomposition, we can easily deduce a number of enumerative results. We also give bijections between these tableaux and certain classes of labeled trees. Finally, we exhibit a bijection with permutations, and relate it to some other bijections that already appeared in the literature.

We are interested in the enumeration of Fully Packed Loop configurations on a grid with a given noncrossing matching. By the recently proved Razumov--Stroganov conjecture, these quantities also appear as groundstate components in the Completely Packed Loop model. When considering matchings with p nested arches, these numbers are known to be polynomials in p. In this article, we present several conjectures about these polynomials: in particular, we describe all real roots, certain values of these polynomials, and conjecture that the coefficients are positive. The conjectures, which are of a combinatorial nature, are supported by strong numerical evidence and the proofs of several special cases. We also give a version of the conjectures when an extra parameter tau is added to the equations defining the groundstate of the Completely Packed Loop model.

A well-labelled positive path of size n is a pair (p,\sigma) made of a word p=p1p2...pn-1 on the alphabet {-1,0,+1} such that \sum_{i=1}^j pi >= 0 for all j=1,...,n-1, together with a permutation \sigma=\sigma1\sigma2...\sigman of {1,...,n} such that pi=-1 implies \sigmai<\sigmai+1, while pi=1 implies \sigmai> \sigmai+1. We establish a bijection between well-labelled positive paths of size n and matchings (i.e., fixed-point free involutions) on {1,...,2n}. This proves that the number of well-labelled positive paths is (2n-1)!!=(2n-1).(2n-3)...3.1.

Well-labelled positive paths appeared recently in the author's article "Partition function of a freely-jointed chain in a half-space" [in preparation] as a useful tool for studying a polytope \Pin related to the space of configurations of the freely-jointed chain (of length n) in a half-space. The polytope \Pin consists of points (x1,...,xn) in [-1,1]n such that \sum_{i=1}^j xi >= 0 for all j=1,...,n, and it was shown that well-labelled positive paths of size n are in bijection with a collection of subpolytopes partitioning \Pin. Given that the volume of each subpolytope is 1/n!, our results prove combinatorially that the volume of \Pin is (2n-1)!!/n!.

Our bijection has other enumerative corollaries in terms of up-down sequences of permutations. Indeed, by specialising our bijection, we prove that the number of permutations of size n such that each prefix has no more ascents than descents is [(n-1)!!]2 if n is even and n!!(n-2)!! if n is odd.

In this article we study a class of monoids that includes Garside monoids, and give a simple combinatorial proof of a formula for the formal sum of all elements of the monoid. This leads to a formula for the growth function of the monoid in the homogeneous case, and can also be lifted to a resolution of the monoid algebra.

These results are then applied to known monoids related to Coxeter systems: we give the growth function of the Artin-Tits monoids, and do the same for the dual braid monoids. In this last case we show that the monoid algebras of the dual braid monoids of type A and B are Koszul algebras.

There are several automatic tools available for the symbolic analysis of security protocols. The models underlying these tools differ in many aspects. Some of the differences have already been formally related to each other in the literature, such as difference in protocol execution models or definitions of security properties. However, there is an important difference between analysis tools that has not been investigated in depth before: the explored state space. Some tools explore all possible behaviors, whereas others explore strict subsets, often by using so-called scenarios.

We identify several types of state space explored by protocol analysis tools, and relate them to each other. We find previously unreported differences between the various approaches. Using combinatorial results, we determine the requirements for emulating one type of state space by combinations of another type.

We apply our study of state space relations in a performance comparison of several well-known automatic tools for security protocol analysis. We model a set of protocols and their properties as homogeneously as possible for each tool. We analyze the performance of the tools over comparable state spaces. This work enables us to effectively compare these automatic tools, i.e., using the same protocol description and exploring the same state space. We also propose some explanations for our experimental results, leading to a better understanding of the tools

Remark: as this abstract suggests, the results of this article are quite far from my usual research themes. My contributions to this article are a nice application of Pólya-Redfield enumeration, and some necessary effort to understand the work of my coauthors.

We prove a conjecture of Desrosiers, Lapointe and Mathieu [Adv. Math. 212, 2007, p.361--388] giving a closed form formula for the norm of the Jack polynomials in superspace with respect to a certain scalar product. The proof is mainly combinatorial and relies on the explicit expression in terms of admissible tableaux of the non-symmetric Jack polynomials. In the final step of the proof appears an identity on weighted sums of partitions that we demonstrate using the methods of Gessel-Viennot.

In this paper we propose two bijections between permutation tableaux and permutations. These bijections show how natural statistics on the tableaux are equidistributed to classical statistics on permutations: descents, RL-minima and pattern enumerations. We then use those bijections to define subclasses of permutation tableaux that are in bijection with set partitions.

Sergey Fomin defined a very general setting of dual graded graphs that extends the classical Schensted correspondence to a much wider class of objects. His approach is bijective and also has an algebraic side inspired by the works of Stanley on differential posets. In this work we present a possible extension of Fomin's work through the signed enumeration of ribbon tableaux, where ribbons are not constrained.

We study walks in the plane $ \mathbb{Z}^2$, with steps in a given finite set $\mathcal{S}$, which start from the origin but otherwise never hit the half-line $\mathcal{H}=\{(k,0),k\leq 0\}$. These walks on the slit plane have received some attention these last few years, since in particular their enumeration leads to simple closed formulas; but only one bijection has been found so far, in the case of the square lattice, and in this work we give bijections extending this to other set steps.

Let $p=p(S)$ be the smallest possible abscissa x such that there is a walk on the slit plane ending at $(x,0)$. Suppose that $|j|\leq 1$ for each step $(i,j)\in\mathcal{S} $. The main result of this paper is the construction of a length preserving bijection between S-walks on the slit plane with a marked step ending at $(p,0)$, and a certain class of walks on the plane whose enumeration is much simpler. This allows us to interpret combinatorially previously known enumerations, and to give many new ones.

We enumerate walks in the plane $\mathbb{R}^2$, with steps East and North, that stop as soon as they reach a given line; these walks are counted according to the distance of the line to the origin, and we study the asymptotic behavior when the line has a fixed slope and moves away from the origin. When the line has a rational slope, we study a more general class of walks, and give exact as well as asymptotic enumerative results; for this, we define a nice bijection from our walks to words of a rational language. For a general slope, asymptotic results are obtained; in this case, the method employed leads us to find asymptotic results for a wider class of walks in $\mathbb{R}^m$.

We show that the number of fully packed loop configurations corresponding to a matching with m nested arches is polynomial in m if m is large enough, thus essentially proving two conjectures by Zuber [Electronic J. Combin. 11 (2004), Article #R13].