Julien Courtiel - Personal webpage

Articles

2019, Next-toᵏ leading log expansions by chord diagrams, with Karen Yeats, (preprint) hal-02153783.
Abstract + a picture.

Click here to reduce.

Green functions in a quantum field theory can be expanded as bivariate series in the coupling and a scale parameter. The leading logs are given by the main diagonal of this expansion, i.e. the subseries where the coupling and the scale parameter appear to the same power; then the next-to leading logs are listed by the next diagonal of the expansion, where the power of the coupling is decremented by one, and so on. We give a general method for deriving explicit formulas and asymptotic estimates for any next-to k leading-log expansion for a large class of single scale Green functions. These Green functions are solutions to Dyson-Schwinger equations that are known by previous work to be expressible in terms of chord diagrams. We look in detail at the Green function for the fermion propagator in massless Yukawa theory as one example, and the Green function of the photon propagator in quantum electrodynamics as a second example, as well as giving general theorems. Our methods are combinatorial, but the consequences are physical, giving information on which terms dominate and on the dichotomy between gauge theories and other quantum field theories.
2018, Asymptotic Distribution of Parameters in Random Maps, with Olivier Bodini, Sergei Dovgal and Hsien-Kuei Hwang, Analysis of Algorithm 2018 (Uppsala, June 25-29), LIPICS 110, Paper 13, ArXiv:1802.07112.
Abstract + a picture.

Click here to reduce.

We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.
2018, Bijections for Weyl Chamber walks ending on an axis, using arc diagrams (long version), with Eric Fusy, Mathias Lepoutre and Marni Mishna, European Journal of Combinatorics Volume 69, March 2018, Pages 126-142, ArXiv:1611.04489.
Abstract + a picture.

Click here to reduce.

There are several examples of enumerative equivalences in the study of lattice walks where a trade-off appears between a stronger domain constraint and a stronger endpoint constraint. We present a strategy, based on arc diagrams, that gives a bijective explanation of this phenomenon for two kinds of 2D walks (simple walks and hesitating walks). For both step sets, on the one hand, the domain is the octant and the endpoint lies on the x-axis and on the other side, the domain is the quadrant and the endpoint is the origin. Our strategy for simple walks extends to any dimension and yields a new bijective connection between standard Young tableaux of height at most 2k and certain walks with prescribed endpoints in the k-dimensional Weyl chamber of type D.
2017, Terminal chords in connected chord diagrams, with Karen Yeats, Annales de l’Institut Henri Poincaré D, Volume 4, Issue 4, 2017, Pages 417-452, ArXiv:1603.08596.
Abstract + a picture.

Click here to reduce.

Rooted connected chord diagrams form a nice class of combinatorial objects. Recently they were shown to index solutions to certain Dyson-Schwinger equations in quantum field theory. Key to this indexing role are certain special chords which are called terminal chords. Terminal chords provide a number of combinatorially interesting parameters on rooted connected chord diagrams which have not been studied previously. Understanding these parameters better has implications for quantum field theory. Specifically, we show that the distributions of the number of terminal chords and the number of adjacent terminal chords are asymptotically Gaussian with logarithmic means, and we prove that the average index of the first terminal chord is 2n/3. Furthermore, we obtain a method to determine any next-to^i leading log expansion of the solution to these Dyson-Schwinger equations, and have asymptotic information about the coefficients of the log expansions.
2017, Connected chord diagrams and bridgeless maps, with Karen Yeats and Noam Zeilberger, submitted, ArXiv:1611.04611 (new version! more than 50 pages...).
Abstract + a picture.

Click here to reduce.

We present a surprisingly new connection between two well-studied combinatorial classes: rooted connected chord diagrams on one hand, and rooted bridgeless combinatorial maps on the other hand.

We describe a bijection between these two classes, which naturally extends to indecomposable diagrams and general rooted maps. As an application, this bijection provides a simplifying framework for some technical quantum field theory work realized by some of the authors. Most notably, an important but technical parameter naturally translates to vertices at the level of maps. We also give a combinatorial proof to a formula which previously resulted from a technical recurrence, and with similar ideas we prove a conjecture of Hihn.

Independently, we revisit an equation due to Arquès and Béraud for the generating function counting rooted maps with respect to edges and vertices, giving a new bijective interpretation of this equation directly on indecomposable chord diagrams, which moreover can be specialized to connected diagrams and refined to incorporate the number of crossings. Finally, we explain how these results have a simple application to the combinatorics of lambda calculus, verifying the conjecture that a certain natural family of lambda terms is equinumerous with bridgeless maps.
2017, Weighted Lattice Walks and Universality Classes, with Stephen Melczer, Marni Mishna, and Kilian Raschel, Journal of Combinatorial Theory, Series A, Volume 369, Pages 1365-1393, ArXiv:1609.05839, hal:01368786.
Abstract + a picture.

Click here to reduce.

In this work we consider two different aspects of weighted walks in cones. To begin we examine a particular weighted model, known as the Gouyou-Beauchamps model. Using the theory of analytic combinatorics in several variables we obtain the asymptotic expansion of the total number of Gouyou-Beauchamps walks confined to the quarter plane. Our formulas are parametrized by weights and starting point, and we identify six different kinds of asymptotic regimes (called universality classes) which arise according to the values of the weights. The weights allowed in this model satisfy natural algebraic identities permitting an expression of the weighted generating function in terms of the generating function of unweighted walks on the same steps. The second part of this article explains these identities combinatorially for walks in arbitrary cones and dimensions, and provides a characterization of universality classes for general weighted walks. Furthermore, we describe an infinite set of models with non-D-finite generating function.
2016, Bijections for Weyl Chamber walks ending on an axis, using arc diagrams, with Eric Fusy, Mathias Lepoutre and Marni Mishna, submission for FPSAC 2017, ArXiv:1611.04489.
Abstract + a picture.

Click here to reduce.

There are several examples of enumerative equivalences in the study of lattice walks where a trade-off appears between a stronger domain constraint and a stronger endpoint constraint. We present a strategy, based on arc diagrams, that gives a bijective explanation of this phenomenon for two kinds of 2D walks (simple walks and hesitating walks). For both step sets, on the one hand, the domain is the octant and the endpoint lies on the x-axis and on the other side, the domain is the quadrant and the endpoint is the origin. Our strategy for simple walks extends to any dimension and yields a new bijective connection between standard Young tableaux of height at most 2k and certain walks with prescribed endpoints in the k-dimensional Weyl chamber of type D.
2016, An Unambiguous And Complete Dynamic Programming Algorithm For Tree Alignment, with Cedric Chauve and Yann Ponty, 3rd International Conference on Algorithms for Computational Biology (conference proceedings), hal:01088871, ArXiv:1505.05983.
Abstract + a picture.

Click here to reduce.

Pairwise ordered tree alignment are combinatorial objects that appear in RNA secondary structure comparison. However, the usual representation of tree alignments as supertrees is ambiguous, i.e. two distinct supertrees may induce identical sets of matches between identical pairs of trees. This ambiguity is uninformative, and detrimental to any probabilistic analysis. In this work, we consider tree alignments up to equivalence. Our first result is a precise asymptotic enumeration of tree alignments, obtained from a context-free grammar by mean of basic analytic combinatorics. Our second result focuses on alignments between two given ordered trees S and T. By refining our grammar to align specific trees, we obtain a decomposition scheme for the space of alignments, and use it to design an efficient dynamic programming algorithm for sampling alignments under the Gibbs-Boltzmann probability distribution. This generalizes existing tree alignment algorithms, and opens the door for a probabilistic analysis of the space of suboptimal RNA secondary structures alignments.
2016, Tableau sequences, open diagrams, and Baxter families, with Sophie Burrill, Eric Fusy, Stephen Melczer and Marni Mishna, European Journal of Combinatorics, Volume 58, November 2016, Pages 144–165, ArXiv:1506.03544.
Abstract + a picture.

Click here to reduce.

Walks on Young’s lattice of integer partitions encode many objects of algebraic and combinatorial interest. Chen et al. established connections between such walks and arc diagrams. We show that walks that start at the empty shape, end at a row shape, and only visit partitions of bounded height are in bijection with a new type of arc diagram — open diagrams. Remarkably, two subclasses of open diagrams are equinumerous with well known objects: standard Young tableaux of bounded height, and Baxter permutations. We give an explicit combinatorial bijection in the former case, and a generating function proof and new conjecture in the second case.
2015, Spanning forests in regular planar maps, with Mireille Bousquet-Mélou (long form), Journal of Combinatorial Theory, Series A, Volume 135, October 2015, Pages 1–59, ArXiv:1306.4536.
Abstract + a picture.

Click here to reduce.

We address the enumeration of p-valent planar maps equipped with a spanning forest, with a weight z per face and a weight u per connected component of the forest. Equivalently, we count p-valent maps equipped with a spanning tree, with a weight z per face and a weight μ:=u+1 per internally active edge, in the sense of Tutte; or the (dual) p-angulations equipped with a recurrent sandpile configuration, with a weight z per vertex and a variable μ:=u+1 that keeps track of the level of the configuration. This enumeration problem also corresponds to the limit q→0 of the q-state Potts model on p-angulations.
Our approach is purely combinatorial. The associated generating function, denoted F(z,u), is expressed in terms of a pair of series defined implicitly by a system involving doubly hypergeometric series. We derive from this system that F(z,u)F is differentially algebraic in z, that is, satisfies a differential equation in z with polynomial coefficients in z and u. This has recently been proved to hold for the more general Potts model on 3-valent maps, but via a much more involved and less combinatorial proof.
For u≥−1, we study the singularities of F(z,u) and the corresponding asymptotic behaviour of its nth coefficient. For u>0, we find the standard behaviour of planar maps, with a subexponential term in n^−5/2. At u=0 we witness a phase transition with a term n^−3. When u∈[−1,0), we obtain an extremely unusual behaviour in n^−3(ln n)^-2. To our knowledge, this is a new “universality class” for planar maps. We analyze the phase transition at u=0 in terms of the sandpile model on large maps, and find it to be of infinite order.
2014, A general notion of activity for the Tutte polynomial, preprint, hal:01088871, ArXiv:1412.2081.
Abstract + a picture.

Click here to reduce.

In the literature can be found several descriptions of the Tutte polynomial of graphs. Tutte defined it thanks to a notion of activity based on an ordering of the edges. Thereafter, Bernardi gave a non-equivalent notion of the activity where the graph is embedded in a surface. In this paper, we see that other notions of activity can thus be imagined and they can all be embodied in a same notion, the Δ-activity. We develop a short theory which sheds light on the connections between the different expressions of the Tutte polynomial.
2013, Spanning forests in regular planar maps, with Mireille Bousquet-Mélou, FPSAC 2013, Paris (France), DMTCS proc. (conference proceedings).
2012, Gerechte designs with rectangular regions, with E. R. Vaughan, Journal of Combinatorial Designs 20, February 2012, ArXiv:1104.0637.