Réflexions

Philippe Nadeau

I am a CNRS researcher at the Institut Camille Jordan of the Université Lyon 1, in the Combinatorics and Number Theory team.


My main research interests are bijective and enumerative combinatorics, and I have a strong interest for problems in algebraic combinatorics.


Email address: .



NEW WEBPAGE AT THIS ADDRESS


Publications

  1. Signed enumeration of ribbon tableaux: an approach through growth diagrams
    with Dominique Gouyou-Beauchamps. Journal of Algebraic Combinatorics, to appear.
    Description Down arrow

    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.

  2. The Structure of Alternative Tableaux
    Journal of Combinatorial Theory, series A, Volume 118, Issue 5, July 2011, Pages 1638-1660.
    arXiv version
    Description Down arrow

    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.

  3. On some polynomials enumerating Fully Packed Loop configurations
    with Tiago Fonseca. Advances in Applied Mathematics, Volume 47, Issue 3, September 2011, Pages 434-462.
    arXiv version
    Description Down arrow

    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.

  4. A Bijection Between Well-Labelled Positive Paths and Matchings
    with Olivier Bernardi and Bertrand Duplantier, Séminaire Lotharingien de Combinatoire (2010), volume 63, Article B63e.
    Description Down arrow

    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.

  5. Fully Packed Loop configurations in a triangle and Littlewood-Richardson coefficients
    DMTCS, proceedings of FPSAC 2010, San Francisco.
    Description Down arrow

    We are interested in Fully Packed Loops in a triangle (TFPLs), as introduced by Caselli at al. and studied by Thapper. We show that for Fully Packed Loops with a fixed link pattern (refined FPL), there exist linear recurrence relations with coefficients computed from TFPL configurations. We then give constraints and enumeration results for certain classes of TFPL configurations. For special boundary conditions, we show that TFPLs are counted by the famous Littlewood-- Richardson coefficients.

  6. Growth function for a class of monoids
    with Marie Albenque, FPSAC 2009, Linz.
    Description Down arrow

    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.

  7. Comparing State Spaces in Automatic Security Protocol Verification
    with Cas Cremers and Pascal Lafourcade, Lecture Notes in Computer Science 5458, pages 70-94.
    Description Down arrow

    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.

  8. A normalization formula for the Jack polynomials in superspace and an identity on partitions
    with Luc Lapointe and Yvan Le Borgne, Electronic Journal of Combinatorics, volume 16(1), Article #R70.
    Description Down arrow

    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.

  9. Bijections for permutation tableaux
    with Sylvie Corteel, European Journal of Combinatorics, volume 30(1), 2009, pages 295--310.
    Description Down arrow

    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.

  10. Growth diagrams, Ribbon tableaux and the Involution principle
    with Dominique Gouyou-Beauchamps, FPSAC 2007, Tianjin.
    Description Down arrow

    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.

  11. A General Bijection for Walks on the Slit Plane
    FPSAC 2006, San Diego.
    Description Down arrow

    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.

  12. Enumeration of Walks Reaching a Line
    EUROCOMB 2005.
    Description Down arrow

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

  13. On the Number of Fully Packed Loop Configurations with a Fixed Associated Matching
    with Fabrizio Caselli, Bodo Lass, and Christian Krattenthaler, Electronic Journal of Combinatorics, volume 11(2), Article #R16, 41 pp.
    Description Down arrow

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

Preprints

  1. Fully Packed Loop Configurations in a Triangle
    Description Down arrow

    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.

  2. Fully Packed Loop Configurations in a Triangle and Littlewood-Richardson coefficients
    Description Down arrow

    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.

In preparation

  1. Fully Packed Loop Configurations in a Triangle: matchings, paths and puzzles,
    with Ilse Fischer.

Talks

Selection of more or less recent talks.

Teaching experience

I was a teaching assistant at the University of Vienna in 2010--2011, at Orsay University from 2003 to 2006, and then at Paris 7 University in 2006--2007, in the following courses of the Bachelor in Computer Science:


2010--2011 Introduction to mathematics First year
2006--2007 Introduction to the C language Master in Statistics
Programming in the UNIX System First year
2005--2006 Initiation to Computer Science First year
Imperative programming First year
2004--2005 Functional Programming First year
Combinatorics for Computer Science Second year
2003--2004 Mathematics for Computer Science Third Year
Combinatorics for Computer Science Second year

I also gave oral exams in Mathematics to students of classes préparatoires in Paris, at the Lycée Saint-Louis in 2002--2003 and at the Lycée Fénelon in 2006--2007.