Search

We consider planar bipartite maps which are both tight, i.e. without vertices of degree $1$, and $2b$-irreducible, i.e. such that each cycle has length at least $2b$ and such that any cycle of length exactly $2b$ is the contour of a face. It was shown by Budd that the number $\mathcal N_n^{(b)}$ of such maps made out of a fixed set of $n$ faces with prescribed even degrees is a polynomial in both $b$ and the face degrees. In this paper, we give an explicit expression for $\mathcal N_n^{(b)}$ by a direct bijective approach based on the so-called slice decomposition. More precisely, we decompose any of the maps at hand into a collection of $2b$-irreducible tight slices and a suitable two-face map. We show how to bijectively encode each $2b$-irreducible slice via a $b$-decorated tree drawn on its derived map, and how to enumerate collections thereof. We then discuss the polynomial counting of two-face maps, and show how to combine it with the former enumeration to obtain $\mathcal N_n^{(b)}$., Comment: 54 pages, 21 figures

We consider maps with tight boundaries, i.e. maps whose boundaries have minimal length in their homotopy class, and discuss the properties of their generating functions $T^{(g)}_{\ell_1,\ldots,\ell_n}$ for fixed genus $g$ and prescribed boundary lengths $\ell_1,\ldots,\ell_n$, with a control on the degrees of inner faces. We find that these series appear as coefficients in the expansion of $\omega^{(g)}_n(z_1,\ldots,z_n)$, a fundamental quantity in the Eynard-Orantin theory of topological recursion, thereby providing a combinatorial interpretation of the Zhukovsky transformation used in this context. This interpretation results from the so-called trumpet decomposition of maps with arbitrary boundaries. In the planar bipartite case, we obtain a fully explicit formula for $T^{(0)}_{2\ell_1,\ldots,2\ell_n}$ from the Collet-Fusy formula. We also find recursion relations satisfied by $T^{(g)}_{\ell_1,\ldots,\ell_n}$, which consist in adding an extra tight boundary, keeping the genus $g$ fixed. Building on a result of Norbury and Scott, we show that $T^{(g)}_{\ell_1,\ldots,\ell_n}$ is equal to a parity-dependent quasi-polynomial in $\ell_1^2,\ldots,\ell_n^2$ times a simple power of the basic generating function $R$. In passing, we provide a bijective derivation in the case $(g,n)=(0,3)$, generalizing a recent construction of ours to the non bipartite case., Comment: 62 pages, 7 figures

We introduce multicritical Schur measures, which are probability laws on integer partitions which give rise to non-generic fluctuations at their edge. They are in the same universality classes as one-dimensional momentum-space models of free fermions in flat confining potentials, studied by Le Doussal, Majumdar and Schehr. These universality classes involve critical exponents of the form 1/(2m+1), with m a positive integer, and asymptotic distributions given by Fredholm determinants constructed from higher order Airy kernels, extending the generic Tracy-Widom GUE distribution recovered for m=1. We also compute limit shapes for the multicritical Schur measures, discuss the finite temperature setting, and exhibit an exact mapping to the multicritical unitary matrix models previously encountered by Periwal and Shevitz., Comment: 50 pages, 8 figures, long version of arXiv:2012.01995 [math.CO]; v2: minor corrections; v3: final version

Some fifty years ago, in her seminal PhD thesis, Odile Macchi introduced permanental and determinantal point processes. Her initial motivation was to provide models for the set of detection times in fundamental bosonic or fermionic optical experiments, respectively. After two rather quiet decades, these point processes have quickly become standard examples of point processes with nontrivial, yet tractable, correlation structures. In particular, determinantal point processes have been since the 1990s a technical workhorse in random matrix theory and combinatorics, and a standard model for repulsive point patterns in machine learning and spatial statistics since the 2010s. Meanwhile, our ability to experimentally probe the correlations between detection events in bosonic and fermionic optics has progressed tremendously. In Part I of this survey, we provide a modern introduction to the concepts in Macchi's thesis and their physical motivation, under the combined eye of mathematicians, physicists, and signal processers. Our objective is to provide a shared basis of knowledge for later cross-disciplinary work on point processes in quantum optics, and reconnect with the physical roots of permanental and determinantal point processes., Comment: Disclaimer: this is Part I of a cross-disciplinary survey that is work in progress, all comments are welcome

A tight map is a map with some of its vertices marked, such that every vertex of degree $1$ is marked. We give an explicit formula for the number $N_{0,n}(d_1,\ldots,d_n)$ of planar tight maps with $n$ labeled faces of prescribed degrees $d_1,\ldots,d_n$, where a marked vertex is seen as a face of degree $0$. It is a quasi-polynomial in $(d_1,\ldots,d_n)$, as shown previously by Norbury. Our derivation is bijective and based on the slice decomposition of planar maps. In the non-bipartite case, we also rely on enumeration results for two-type forests. We discuss the connection with the enumeration of non necessarily tight maps. In particular, we provide a generalization of Tutte's classical slicings formula to all non-bipartite maps., Comment: 70 pages, 19 figures (accepted version ; changes since v1: one extra figure and several small improvements/corrections)

We consider planar maps with three boundaries, colloquially called pairs of pants. In the case of bipartite maps with controlled face degrees, a simple expression for their generating function was found by Eynard and proved bijectively by Collet and Fusy. In this paper, we obtain an even simpler formula for \emph{tight} pairs of pants, namely for maps whose boundaries have minimal length in their homotopy class. We follow a bijective approach based on the slice decomposition, which we extend by introducing new fundamental building blocks called bigeodesic triangles and diangles, and by working on the universal cover of the triply punctured sphere. We also discuss the statistics of the lengths of minimal separating loops in (non necessarily tight) pairs of pants and annuli, and their asymptotics in the large volume limit., Comment: 76 pages, 29 figures, final version

A planar hypermap with a boundary is defined as a planar map with a boundary, endowed with a proper bicoloring of the inner faces. The boundary is said alternating if the colors of the incident inner faces alternate along its contour. In this paper we consider the problem of counting planar hypermaps with an alternating boundary, according to the perimeter and to the degree distribution of innerfaces of each color. The problem is translated into a functional equation with a catalytic variable determining the corresponding generating function. In the case of constellations - hypermaps whose all inner faces of a given color have degree $m\geq 2$, and whose all other inner faces have a degree multiple of $m$ - we completely solve the functional equation, and show that the generating function is algebraic and admits an explicit rational parametrization. We finally specialize to the case of Eulerian triangulations - hypermaps whose all inner faces have degree $3$ - and compute asymptotics which are needed in another work by the second author, to prove the convergence of rescaled planar Eulerian triangulations to the Brownian map., Comment: 20 pages, 5 figures. Final version appearing in EJC

We study two families of probability measures on integer partitions, which are Schur measures with parameters tuned in such a way that the edge fluctuations are characterized by a critical exponent different from the generic $1/3$. We find that the first part asymptotically follows a "higher-order analogue" of the Tracy-Widom GUE distribution, previously encountered by Le Doussal, Majumdar and Schehr in quantum statistical physics. We also compute limit shapes, and discuss an exact mapping between one of our families and the multicritical unitary matrix models introduced by Periwal and Shevitz., Comment: 12 pages, 3 figures (v2: minor modifications and clarifications). Extended abstract for FPSAC 2021

This habilitation thesis summarizes the research that I have carried out from 2005 to 2019. It is organized in four chapters. The first three deal with random planar maps. Chapter 1 is about their metric properties: from a general map-mobile bijection, we compute the three-point function of quadrangulations, before discussing the connection with continued fractions. Chapter 2 presents the slice decomposition, a unified bijective approach that applies notably to irreducible maps. Chapter 3 concerns the $O(n)$ loop model on planar maps: by a combinatorial decomposition, we obtain the phase diagram before studying loop nesting statistics. Chapter 4 deals with random partitions and Schur processes, from steep domino tilings to fermionic systems., Comment: Habilitation thesis, written in English except an introduction in French, 107 pages, many figures. Pages numbers differ from the printed copies given at the defence on 2 December 2019

We study edge asymptotics of poissonized Plancherel-type measures on skew Young diagrams (integer partitions). These measures can be seen as generalizations of those studied by Baik--Deift--Johansson and Baik--Rains in resolving Ulam's problem on longest increasing subsequences of random permutations and the last passage percolation (corner growth) discrete versions thereof. Moreover they interpolate between said measures and the uniform measure on partitions. In the new KPZ-like 1/3 exponent edge scaling limit with logarithmic corrections, we find new probability distributions generalizing the classical Tracy--Widom GUE, GOE and GSE distributions from the theory of random matrices., Comment: 12 pages, 2 figures. Extended abstract for FPSAC 2019

We revisit the periodic Schur process introduced by Borodin in 2007. Our contribution is threefold. First, we provide a new simpler derivation of its correlation functions via the free fermion formalism. In particular, we shall see that the process becomes determinantal by passing to the grand canonical ensemble, which gives a physical explanation to Borodin's "shift-mixing" trick. Second, we consider the edge scaling limit in the simplest nontrivial case, corresponding to a deformation of the poissonized Plancherel measure on partitions. We show that the edge behavior is described, in a certain crossover regime different from that for the bulk, by the universal finite-temperature Airy kernel, which was previously encountered by Johansson and Le Doussal et al. in other models, and whose extreme value statistics interpolates between the Tracy-Widom GUE and the Gumbel distributions. We also define and prove convergence for a stationary extension of our model. Finally, we compute the correlation functions for a variant of the periodic Schur process involving strict partitions, Schur's P and Q functions, and neutral fermions., Comment: 36 pages, 3 figures. v2: final version with several additions: two figures in introduction; some previously missing references; results on the edge behavior of the cylindric Plancherel measure outside the crossover regime, in particular in the nontrivial high temperature regime (see new Theorem 1.2, Proposition 5.2 and Appendix D)

We investigate the free boundary Schur process, a variant of the Schur process introduced by Okounkov and Reshetikhin, where we allow the first and the last partitions to be arbitrary (instead of empty in the original setting). The pfaffian Schur process, previously studied by several authors, is recovered when just one of the boundary partitions is left free. We compute the correlation functions of the process in all generality via the free fermion formalism, which we extend with the thorough treatment of "free boundary states". For the case of one free boundary, our approach yields a new proof that the process is pfaffian. For the case of two free boundaries, we find that the process is not pfaffian, but a closely related process is. We also study three different applications of the Schur process with one free boundary: fluctuations of symmetrized last passage percolation models, limit shapes and processes for symmetric plane partitions, and for plane overpartitions., Comment: 58 pages, 17 figures (v3: final version, with fewer pages than v2 to comply with journal requirements. In particular Theorems 2.2 and 2.5 are now stated under slightly more restrictive assumptions to simplify presentation. Added Remarks 2.11, 2.12, 5.14 and 6.9 about the transition from pfaffian to determinantal in the bulk.)

In the O(n) loop model on random planar maps, we study the depth - in terms of the number of levels of nesting - of the loop configuration, by means of analytic combinatorics. We focus on the 'refined' generating series of pointed disks or cylinders, which keep track of the number of loops separating the marked point from the boundary (for disks), or the two boundaries (for cylinders). For the general O(n) loop model, we show that these generating series satisfy functional relations obtained by a modification of those satisfied by the unrefined generating series. In a more specific O(n) model where loops cross only triangles and have a bending energy, we explicitly compute the refined generating series. We analyse their non generic critical behavior in the dense and dilute phases, and obtain the large deviations function of the nesting distribution, which is expected to be universal. Using the framework of Liouville quantum gravity (LQG), we show that a rigorous functional KPZ relation can be applied to the multifractal spectrum of extreme nesting in the conformal loop ensemble (CLE) in the Euclidean unit disk, as obtained by Miller, Watson and Wilson, or to its natural generalisation to the Riemann sphere. It allows us to recover the large deviations results obtained for the critical O(n) random planar map models. This offers, at the refined level of large deviations theory, a rigorous check of the fundamental fact that the universal scaling limits of random planar map models as weighted by partition functions of critical statistical models are given by LQG random surfaces decorated by independent CLEs., Comment: 105 pages, 11 figures. v2: minor text and abstract edits, references added. v4: revised and expanded, including justification of delta analyticity. v5: final version

We introduce a general model of dimer coverings of certain plane bipartite graphs, which we call rail yard graphs (RYG). The transfer matrices used to compute the partition function are shown to be isomorphic to certain operators arising in the so-called boson-fermion correspondence. This allows to reformulate the RYG dimer model as a Schur process, i.e. as a random sequence of integer partitions subject to some interlacing conditions. Beyond the computation of the partition function, we provide an explicit expression for all correlation functions or, equivalently, for the inverse Kasteleyn matrix of the RYG dimer model. This expression, which is amenable to asymptotic analysis, follows from an exact combinatorial description of the operators localizing dimers in the transfer-matrix formalism, and then a suitable application of Wick's theorem. Plane partitions, domino tilings of the Aztec diamond, pyramid partitions, and steep tilings arise as particular cases of the RYG dimer model. For the Aztec diamond, we provide new derivations of the edge-probability generating function, of the biased creation rate, of the inverse Kasteleyn matrix and of the arctic circle theorem., Comment: 44 pages, 17 figures, improved the discussion of the case of the Aztec diamond in new section 6

Building on previous work by four of us (ABCN), we consider further generalizations of Warrington's juggling Markov chains. We first introduce "multispecies" juggling, which consist in having balls of different weights: when a ball is thrown it can possibly bump into a lighter ball that is then sent to a higher position, where it can in turn bump an even lighter ball, etc. We both study the case where the number of balls of each species is conserved and the case where the juggler sends back a ball of the species of its choice. In this latter case, we actually discuss three models: add-drop, annihilation and overwriting. The first two are generalisations of models presented in (ABCN) while the third one is new and its Markov chain has the ultra fast convergence property. We finally consider the case of several jugglers exchanging balls. In all models, we give explicit product formulas for the stationary probability and closed form expressions for the normalisation factor if known., Comment: 25 pages, 9 figures (v3: final version, several typos and figures fixed)

We describe random generation algorithms for a large class of random combinatorial objects called Schur processes, which are sequences of random (integer) partitions subject to certain interlacing conditions. This class contains several fundamental combinatorial objects as special cases, such as plane partitions, tilings of Aztec diamonds, pyramid partitions and more generally steep domino tilings of the plane. Our algorithm, which is of polynomial complexity, is both exact (i.e. the output follows exactly the target probability law, which is either Boltzmann or uniform in our case), and entropy optimal (i.e. it reads a minimal number of random bits as an input). The algorithm encompasses previous growth procedures for special Schur processes related to the primal and dual RSK algorithm, as well as the famous domino shuffling algorithm for domino tilings of the Aztec diamond. It can be easily adapted to deal with symmetric Schur processes and general Schur processes involving infinitely many parameters. It is more concrete and easier to implement than Borodin's algorithm, and it is entropy optimal. At a technical level, it relies on unified bijective proofs of the different types of Cauchy and Littlewood identities for Schur functions, and on an adaptation of Fomin's growth diagram description of the RSK algorithm to that setting. Simulations performed with this algorithm suggest interesting limit shape phenomena for the corresponding tiling models, some of which are new., Comment: 26 pages, 19 figures (v3: final version, corrected a few misprints present in v2)

We introduce a family of domino tilings that includes tilings of the Aztec diamond and pyramid partitions as special cases. These tilings live in a strip of $\mathbb{Z}^2$ of the form $1 \leq x-y \leq 2\ell$ for some integer $\ell \geq 1$, and are parametrized by a binary word $w\in\{+,-\}^{2\ell}$ that encodes some periodicity conditions at infinity. Aztec diamond and pyramid partitions correspond respectively to $w=(+-)^\ell$ and to the limit case $w=+^\infty-^\infty$. For each word $w$ and for different types of boundary conditions, we obtain a nice product formula for the generating function of the associated tilings with respect to the number of flips, that admits a natural multivariate generalization. The main tools are a bijective correspondence with sequences of interlaced partitions and the vertex operator formalism (which we slightly extend in order to handle Littlewood-type identities). In probabilistic terms our tilings map to Schur processes of different types (standard, Pfaffian and periodic). We also introduce a more general model that interpolates between domino tilings and plane partitions., Comment: 36 pages, 22 figures (v3: final accepted version with new Figure 6, new improved proof of Proposition 11)

We consider refined versions of Markov chains related to juggling introduced by Warrington. We further generalize the construction to juggling with arbitrary heights as well as infinitely many balls, which are expressed more succinctly in terms of Markov chains on integer partitions. In all cases, we give explicit product formulas for the stationary probabilities. The normalization factor in one case can be explicitly written as a homogeneous symmetric polynomial. We also refine and generalize enriched Markov chains on set partitions. Lastly, we prove that in one case, the stationary distribution is attained in bounded time., Comment: 28 pages, 5 figures, final version

We consider the problem of computing the distance-dependent two-point function of general planar maps and hypermaps, i.e. the problem of counting such maps with two marked points at a prescribed distance. The maps considered here may have faces of arbitrarily large degree, which requires new bijections to be tackled. We obtain exact expressions for the following cases: general and bipartite maps counted by their number of edges, 3-hypermaps and 3-constellations counted by their number of dark faces, and finally general and bipartite maps counted by both their number of edges and their number of faces., Comment: 32 pages, 17 figures

We study a one-dimensional totally asymmetric simple exclusion process with one special site from which particles fly to any empty site (not just to the neighboring site). The system attains a non-trivial stationary state with density profile varying over the spatial extent of the system. The density profile undergoes a non-equilibrium phase transition when the average density passes through the critical value 1-1/[4(1-ln 2)]=0.185277..., viz. in addition to the discontinuity in the vicinity of the special site, a shock wave is formed in the bulk of the system when the density exceeds the critical density., Comment: Published version (v2)

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 multicontinued fractions and generalized Hankel determinants. As an application, we provide a combinatorial derivation of the generating function of Eulerian triangulations with two points at a prescribed distance., Comment: 12 pages, 4 figures