Scaling and local limits of Baxter permutations through coalescent-walk processes
Jacopo Borga Mickaël Maazoun
math.PR math.CO



ON LOGARITHMIC HÖLDER CONTINUITY OF MAPPINGS ON THE
BOUNDARY
    EVGENY SEVOST'YANOV

    December 30, 2023
=============================================================





Baxter permutations, plane bipolar orientations, and a specific family of walks in the non-negative quadrant are well-known to be related to each other through several bijections. We introduce a further new family of discrete objects, called coalescent-walk processes, that are fundamental for our results. We relate these new objects with the other previously mentioned families introducing some new bijections. 

We prove joint Benjamini–Schramm convergence (both in the annealed and quenched sense) for uniform objects in the four families. Furthermore, we explicitly construct a new fractal random measure of the unit square,
called the coalescent Baxter permuton and we show that it is the scaling limit (in the permuton sense) of uniform Baxter permutations. 

To prove the latter result, we study the scaling limit of the associated random coalescent-walk processes. We show that they converge in law to a continuous random coalescent-walk process encoded by a perturbed version of the Tanaka stochastic differential equation. This result has
connections (to be explored in future projects) with the results of 
Gwynne, Holden, Sun (2016) on scaling limits (in the Peanosphere topology) of plane bipolar triangulations. 

We further prove some results that relate the limiting objects of the four families to each other, both in the local and scaling limit case.








§ INTRODUCTION AND MAIN RESULTS

Baxter permutations were introduced by Glen Baxter in 1964 <cit.> to study fixed points of commuting functions.
Baxter permutations are permutations avoiding the two vincular patterns 2[.5pt][1pt]413 and 3[.5pt][1pt]142, i.e. permutations σ such that there are no indices i < j < k such that σ(j+1) < σ(i) < σ(k) < σ(j) or σ(j) < σ(k) < σ(i) < σ(j+1).


In the last 30 years, several bijections between Baxter permutations, plane bipolar orientations and certain walks in the plane[We refer to <ref> for a precise definition of all these objects.] have been discovered. These relations between discrete objects of different nature are a beautiful piece of combinatorics[Quoting the abstract of <cit.>.] that we aim at investigating from a more probabilistic point of view in this extended abstract.
The goal of our work is to explore local and scaling limits of these objects and to study the relations between their limits. Indeed, since these objects are related by several bijections at the discrete level, we expect that most of the relations among them also hold in the “limiting discrete and continuous worlds”. 

We mention that some limits of these objects (and related ones) were previously investigated. 
Dokos and Pak <cit.> explored the expected limit shape of doubly alternating Baxter
permutations, i.e. Baxter permutations σ such that σ and σ^-1 are alternating. In their article they claimed that “it would be interesting to compute the limit shape of random Baxter permutations”. One of the main goals of our work is to answer this question by proving permuton convergence for uniform Baxter permutations (see <ref> below).
For plane walks (i.e. walks in ^2) conditioned to stay in a cone, we mention the remarkable works of Denisov and Wachtel <cit.> and Duraj and Wachtel <cit.> where they proved (together with many other results) convergence towards Brownian meanders or excursions in cones.
This allowed Kenyon, Miller, Sheffield and
Wilson <cit.> to show that the quadrant walks encoding uniformly random plane bipolar orientations (see <ref> for more details) converge to a Brownian excursion of correlation -1/2 in the quarter-plane. This is interpreted as Peanosphere convergence of the maps decorated by the Peano curve (see <ref> for further details) to a √(4/3)-Liouville Quantum Gravity (LQG) surface decorated by an independent SLE_12. This result was then significantly strengthened by Gwynne, Holden and Sun <cit.> who proved joint convergence for the map and its dual, in the setting of infinite-volume triangulations.
In proving <ref> we extend some of the methods and results of <cit.>, with a key difference in the way limiting objects are defined. We discuss this in more precise terms at the end of this introduction.

So far we have considered three families of objects: Baxter permutations (denoted by 𝒫); walks in the non-negative quadrant (𝒲) starting on the y-axis and ending on the x-axis, with some specific admissible increments defined in the forthcoming <ref>; and plane bipolar orientations (𝒪). For our purposes, specifically for the proof of the permuton convergence, we introduce in <ref> a fourth family of objects called coalescent-walk processes (𝒞).


We denote by 𝒲_n the subset of 𝒲 consisting of quadrant walks of size n (and similarly 𝒞_n,𝒫_n,𝒪_n for the other three families).
We will present four size-preserving bijections
(denoted using two letters that refer to the domain and co-domain)
between these four families, summarized in the following diagram:

    𝒲r   𝒞d
    𝒪ur   𝒫 ,

where the mapping  was introduced in <cit.> and  in <cit.>; the others are new.
Our first result is the following:
 
	The diagram in <ref> commutes.
	In particular, ∘:𝒲→𝒫 is a size-preserving bijection.


Our second result deals with local limits, more precisely Benjamini–Schramm limits. Informally, Benjamini–Schramm convergence for discrete objects looks at the convergence of the neighborhoods (of any fixed size) of a uniformly distinguished point of the object (called root).
In order to properly define the Benjamini–Schramm convergence for the four families, we need to present the respective local topologies. We defer this task to the complete version of this abstract, here we just mention that the local topology for graphs (and so plane bipolar orientations) was introduced by Benjamini and Schramm <cit.> while the local topology for permutations was introduced by the first author <cit.>. Local topologies for plane walks and coalescent-walk processes can be defined in a similar way. 
We denote by _∙  the completion of the space of rooted walks _n≥ 1𝒲_n × [n]  with respect to the metric defining the local topology. The spaces _∙, _∙, _∙ are defined likewise from 𝒞,𝒫, 𝒪.



We define below the candidate limiting objects. As a matter of fact, a formal definition requires an extension of the mappings in <ref> to infinite-volume objects (for the mappings  and ^-1 also an extension to walks that are not conditioned in the quadrant). We do not present all the details of such extensions, but they can be easily guessed from our description of the mappings ,, and  given in <ref>.

Let ν denote the probability distribution on ^2 given by:

    ν = 1/2δ_(+1,-1) + ∑_i,j≥ 0 2^-i-j-3δ_(-i,j),  where δ denotes the Dirac measure,

and let[Here and throughout the paper we denote random quantities using bold characters.] W̅ = (X̅,Y̅) = (W̅_t)_t∈ be a bidirectional random plane walk with step distribution ν, with value (0,0) at time 0.
Let Z̅ = (W̅) be the corresponding infinite coalescent-walk process, σ̅ = (Z̅) the corresponding infinite permutation on  (in this context, an infinite permutation is a total order of ), and m̅ = ^-1(W̅) the corresponding infinite map. 


 For every n∈_>0, let W_n, Z_n, σ_n, and m_n denote uniform objects of size n in 𝒲_n, 𝒞_n, 𝒫_n, and 𝒪_n respectively, related by the bijections of <ref>.
For every n∈_>0, let i_n be an independently chosen uniform index of [n]. Then we have joint convergence in distribution in the space _∙×_∙×_∙×_∙:
		
    (( W_n,  i_n), ( Z_n,  i_n), (σ_n,  i_n), ( m_n,  i_n))  (W̅,Z̅,σ̅,m̅).




	We give a few comments on this result.
	
		
  * The mapping ^-1 naturally endows the map m_n with an edge labeling and the root i_n of m_n is chosen according to this labeling.
		
  * We can also prove a quenched version of the above result (of annealed type) for all the four objects (not presented in this extended abstract). It entails (see <cit.>) that consecutive pattern densities of σ_n jointly converge in distribution.
		
  * The fact that the four convergences are joint follows from the fact that the extensions of the mappings in <ref> to infinite-volume objects are a.s. continuous.
		
  * The annealed Benjamini-Schramm convergence for  bipolar orientations to the so-called Uniform Infinite Bipolar Map was already proved in <cit.>.
	


Our third (and main) result is a scaling limit result for Baxter permutations (see <ref> for some simulations), in the framework of permutons developed by <cit.>.
A permuton μ is a Borel probability measure on the unit square [0,1]^2 with uniform marginals, that is 
μ( [0,1] × [a,b] ) = μ( [a,b] × [0,1] ) = b-a,
for all 0 ≤ a ≤ b≤ 1. Any permutation σ of size n ≥ 1 may be interpreted as the permuton μ_σ given by the sum of Lebesgue area measures

    μ_σ(A)= n ∑_i=1^n ([(i-1)/n, i/n]×[(σ(i)-1)/n,σ(i)/n]∩ A),

for all Borel measurable sets A of [0,1]^2.
Let ℳ be the set of permutons. As for general probability measure, we say that a sequence of (deterministic) permutons (μ_n)_n converges weakly to μ (simply denoted μ_n →μ) if 
∫_[0,1]^2 f dμ_n →∫_[0,1]^2 f dμ,
for every (bounded and) continuous function f: [0,1]^2 →ℝ. With this topology, ℳ is compact.
Convergence for random permutations is defined as follows:


	We say that a random permutation σ_n converges in distribution to a random permuton μ as n →∞ if the random permuton μ_σ_n converges in distribution to μ with respect to the weak topology.  

Random permuton convergence entails joint convergence in distribution of all (classical) pattern densities (see <cit.>). The study of permuton limits, as well as other scaling limits of permutations, is a rapidly developing field in discrete probability theory, see for instance <cit.>. Our main result is the following:


	
	Let σ_n be a uniform Baxter permutation of size n. There exists a random permuton μ_B such that
	μ_σ_nd⟶μ_B.


An explicit construction of the limiting permuton μ_B, called the coalescent Baxter permuton, is given in <ref>. The proof of <ref> is based on a result on scaling limits of the coalescent-walk processes Z_n, which appears to be of independent interest, and is discussed in <ref>. 
In particular, the convergence of uniform Baxter permutations is joint[We leave a proper claim of joint convergence to the full version of this paper. However the joint distribution of the scaling limits is the one presented in <ref>.] with that of the conditioned versions of W_n and Z_n presented in <ref>.



We finally discuss the relations with the work of Gwynne, Holden and Sun <cit.>. They show that for infinite-volume bipolar oriented triangulations, the explorations of the two tree/dual tree pairs of the map and its dual converge jointly. The limit is the pair of planar Brownian motions which encode the same √(4/3)-LQG surface decorated by both an SLE_12 curve and the “dual” SLE_12 curve, traveling in a direction perpendicular (in the sense of imaginary geometry) to the original curve. As shown below (<ref>), the bijection of <cit.> between plane bipolar orientations and Baxter permutations can be rewritten in terms of the interaction of these two tree/dual tree pairs, which explains the connection between our work and the one of <cit.>.

We prove <ref> by extending some of their constructions to finite-volume general maps, which allows us to provide an analog of their result (that are restricted to triangulations) for general plane bipolar orientations in finite volume, jointly with the convergences above[Not presented in this extended abstract.]. 
More precisely, the coalescent-walk process defined in <ref> is an extension of the random walk 𝒳 defined in <cit.>. The fact that it encodes the spanning tree of the dual map (<ref>) is a version of <cit.>, albeit we present it differently.
Our main technical ingredient is the convergence of the coalescent-walk process driven by a random plane walk of <ref>. It corresponds to <cit.>.
The way the limiting object (the right-hand side of <ref>) is defined is however very different, and the proofs differ as a consequence. In our case, it comes from a stochastic differential equation (<ref>), for which existence and uniqueness are known from the literature <cit.>. In their case, it is built using imaginary geometry, and characterized by its excursion decomposition. These are nonetheless two descriptions of the same object, providing an SDE formulation of an intricate imaginary geometry coupling. We wish to explore consequences of this in further works.



Outline of the extended abstract. The remainder of the abstract is organized as follows. In <ref> we present the objects and the mappings involved in the diagram in <ref>. Moreover, we sketch the proof of <ref>. <ref> is devoted to developing the theory for the proof of <ref>. In particular, in <ref> we present the aforementioned results for scaling limits of coalescent-walk processes, and in <ref> we give an explicit construction of the limiting permuton for Baxter permutations. Finally, in <ref> we prove our main technical ingredient (<ref>), and in <ref> we finish the proof of <ref>. Note that we leave the proof of <ref> out of this abstract.




§ BIPOLAR ORIENTATIONS, WALKS IN THE NON-NEGATIVE QUADRANT, BAXTER PERMUTATIONS AND COALESCENT-WALK PROCESSES




 §.§ Plane bipolar orientations
 
We recall that a planar map is a connected graph embedded in the plane with no edge-crossings, considered up to continuous deformation. A map has vertices, edges, and faces, the latter being the connected components of the plane remaining after deleting the edges. The outer face is unbounded, the inner faces are bounded. 

	A plane bipolar orientation (or simply bipolar orientation) is a planar map with oriented edges such that 
	
		
  * there are no oriented cycles;
		
  * there is exactly one vertex with only outgoing edges (the source, denoted s), and exactly one vertex with only incoming edges (the sink, denoted s'); all other vertices, called non-polar,  have both types of edges;
		
  * the source and the sink are both incident to the outer face.
	
	The size of a bipolar orientation m is its number of edges and will be denoted with |m|. 


Every bipolar orientation can be plotted in the plane in such a way that every edge is oriented from bottom to top (as done for example in <ref>). 


Given a bipolar orientation, an edge e from v to w is bordered, in the clockwise cyclic order, by its bottom vertex, its left face, its top vertex, its right face.
It is useful, for the consistency of definitions, to think of the external face as split in two (see <ref> for an example): the left external face, and the right external face. 

There is a natural notion of duality for a bipolar orientation m. It is the classical duality for (unoriented) maps where the orientation of a dual edge between two primal faces is from right to left. The primal right external face becomes the dual source, and the primal left external face becomes the dual sink. This map m^* is also a bipolar orientation (see <ref>). The map m^** is just the reversal of the map m: the source and sink are exchanged, and all edges are reversed. 

Given a bipolar orientation m, its down-right tree T(m) may be defined as a set of edges equipped with a parent relation, as follows.

	
  * The edges of T(m) are the edges of m.
	
  * Let e∈ m and v its bottom vertex.
	
		
  * If v is the source, then e has no parent edge in T(m) (it is grafted to the root of T(m));
		
  * if v is not the source, the parent edge of e in T(m) is the right-most incoming edge of v.
	 

The tree T(m) can be drawn on top of m: the root of T(m) corresponds to the source s of m, internal vertices of T(m) correspond to non-polar vertices of m, and leaves of T(m) are the midpoints of some edges of m.
Note that one can draw the trees T(m) and T(m^**) on the map m without any crossing (see the left-hand side of <ref> for an example).

We conclude this section recalling that the exploration of a tree T is the visit of its vertices (or its edges) following the contour of the tree in the clockwise order.





 §.§ Kenyon-Miller-Sheffield-Wilson bijection



We now present a bijection between bipolar orientations and some walks in the non-negative quadrant ℤ_≥ 0^2, introduced in <cit.> by Kenyon, Miller, Sheffield and Wilson.

Let m be a bipolar orientation. We consider the exploration of the tree T(m) (highlighted in green in the middle picture of <ref>) starting at the source s and ending at the last visit of the sink s'. Note that this path (when reversed) is also the exploration of the tree T(m^**) stopped at the last visit of the source s. This path, called interface path[The interface path goes sometimes under the name of Peano curve, see for instance <cit.>.] since it winds between the trees T(m) and T(m^**), identifies an ordering on the set E of edges of m since every edge of T(m) corresponds exactly to one edge of m (see the right-hand side of <ref> for an example). Let e_1,e_2,…,e_|m| be the edges of m listed according to this order. 



	Given a bipolar orientation m, the corresponding walk (m)=(W_t)_t∈ [|m|]=(X_t,Y_t)_t∈ [|m|] of size |m| in the non-negative quadrant ℤ_≥ 0^2 is defined as follows: for t∈ [|m|], let X_t be the distance in the tree T(m) between the bottom vertex of e_t and the root of T(m) (corresponding to the source s), and let Y_t be the distance in the tree T(m^**) between the top vertex of e_t and the root of T(m^**) (corresponding to the sink s').



	The walk (0,X_1+1,…,X_|m|+1) is the height process of the tree T(m). The walk (0,Y_|m|+1, Y_|m|-1+1,…, Y_1+1) is the height process of the tree T(m^**).



Suppose that the left external face has h+1 edges and the right external face has k+1 edges, for some h,k≥ 0. Then the walk (W_t)_1≤ t≤ |m| starts at (0,h), ends at (k,0), and stays in the non-negative quadrant ℤ_≥ 0^2.
We finally investigate the possible values for the increments of the walk, i.e. the values of W_t+1-W_t. 
We say that two edges of a tree are consecutive if one is the parent of the other.
We first highlight that the interface path of the map m has two different behaviors when following the edges e_t and e_t+1: 

	
  * either it is following two consecutive edges of T(m) (this is the case, for instance, of the edges e_3 and e_4 on the right-hand side of <ref>);
	
  * or it is first following e_t, then it is traversing a face of m, and finally is following e_t+1 (this is the case, for instance, of the edges e_5 and e_6 on the right-hand side of <ref>).

When the latter case happens, the interface path splits the boundary of the traversed face in two parts, a left and a right boundary.

Therefore the increments of the walk are either (+1,-1) (when e_t and e_t+1 are consecutive) or (-i,+j), for some i,j∈_≥ 0 (when, between e_t and e_t+1, the interface path is traversing a face with i+1 edges on the left boundary and j+1 edges on the right boundary). We denote by  the set of possible increments, that is 

    = {(+1,-1)}∪{(-i,j), i∈_≥ 0, j∈_≥ 0}.

We denote by 𝒲 the set of walks in the non-negative quadrant, starting at (0,h) and ending at (k,0) for some h≥ 0, k≥ 0, with increments in .

(<cit.>)
	The mapping :𝒪→𝒲 is a size-preserving bijection.



	We consider the map m in <ref>. The corresponding walk (m) is:
	
    ((0,2),(0,3),(0,3),(1,2),(2,1),(0,3),(1,2),(2,1),(3,0),(2,0)).







 §.§ Baxter permutations and bipolar orientations



In <cit.>, a bijection between Baxter permutations and bipolar orientations is given. We give here a slightly different formulation of this bijection (more convenient for our purposes) and then in <ref> we state that the two formulations are equivalent.

 
	Let m be a bipolar orientation of size n≥ 1. Recall that to every edge of the map m corresponds its dual edge in the dual map m^*. The Baxter permutation (m) associated with m is the only permutation π such that for every 1≤ i ≤ n, the i-th edge visited in the exploration of T(m) corresponds to the π(i)-th edge visited in the exploration of T(m^*). We say that this edge corresponds to the index i.

An example is given in <ref>. The following result proves that  is a bijection.
	



	
	The function :𝒪→𝒫 is equal to the function Ψ:𝒪→𝒫 defined in <cit.>. Therefore  is a size-preserving bijection.

The definition of Ψ is the same as that of , with T(m^*) replaced by T(m^-1), m^-1 denoting the symmetry of m along the vertical axis. So the proof (that we omit) amounts to showing that these two trees visit the edges of m in the same order[Actually they are related by a classic bijection between trees: the Lukasiewicz walk of T(m^*) is the reversal of the height function of T(m^-1).]. 



 §.§ Discrete coalescent-walk processes



Since the key ingredient for permuton convergence is the extraction of patterns (see <ref>), we introduce in this section a new tool in order to “extract patterns from the plane walk” that encodes a Baxter permutation, namely coalescent-walk processes. Then, in <ref>, we present a bijection between walks in the non-negative quadrant and a specific kind of coalescent-walk processes, and in <ref>,  we introduce a bijection between these coalescent-walk processes and Baxter permutations. Composing these two mappings we obtain another bijection between walks in the non-negative quadrant and Baxter permutations. Finally, in <ref> we complete the proof of <ref>.


	
	Let I be a (finite or infinite) interval of . We call coalescent-walk process over I a family {(Z^(t)_s)_s≥ t, s∈ I}_t∈ I of one-dimensional walks such that
	
		
  * the walk Z^(t) starts at zero at time t, i.e. Z^(t)_t = 0;
		
  * if Z^(t)_k≥ Z^(t')_k (resp. Z^(t)_k≤ Z^(t')_k) at some time k, then Z^(t)_k'≥ Z^(t')_k' (resp. Z^(t)_k'≤ Z^(t')_k') for every k'≥ k.
	


Note that, as a consequence, if Z^(t)_k= Z^(t')_k, at time k, then Z^(t)_k'=Z^(t')_k' for every k'≥ k. In this case, we say that Z^(t) and Z^(t') are coalescing and call coalescent point of Z^(t) and Z^(t') the point (ℓ,Z^(t)_ℓ) such that  ℓ=min{k≥max{t,t'}|Z^(t)_k=Z^(t')_k}. We denote by (I) the set of coalescent-walk processes over some interval I.





  §.§.§ The coalescent-walk process corresponding to a plane walk


We now introduce a particular family of coalescent-walk processes of interest for us.
Let I be a (finite or infinite) interval of . Recall the definition of  from <ref> page eq:admis_steps, and let _(I) be the set of plane walks of time space I (functions I→^2) with increments in .

Take W∈_(I) and denote W_t = (X_t,Y_t) for t∈ I.
From X and Y we construct the family of walks {Z^(t)}_t∈ I, called the coalescent-walk process associated with W, by

	
  * for t∈ I, Z^(t)_t=0;
	
  * for t∈ I and k∈ I∩[t+1,+∞),
	
    Z^(t)_k=Z^(t)_k-1+(Y_k-Y_k-1),      if   Z^(t)_k-1≥0,
    
    		Z^(t)_k-1-(X_k-X_k-1),     if   Z^(t)_k-1<0 and Z^(t)_k-1-(X_k-X_k-1)<0,
    
    		Y_k-Y_k-1,     if   Z^(t)_k-1<0 and Z^(t)_k-1-(X_k-X_k-1)≥0.


 
Let : _(I) →(I) map each W∈_(I) to the corresponding coalescent-walk process, i.e. (W)={Z^(t)}_t∈ I. We also set 𝒞_n = (𝒲_n) ⊂([n]) and 𝒞=∪_n∈_≥ 0𝒞_n.




We give a heuristic explanation of this construction in the following example.

	We consider the plane walk W=(W_t)_t∈ [10] starting at (0,0) on the left-hand side of <ref>. We plot in the second diagram of <ref> the walks Y in red and -X in blue. We now explain how we reconstruct the ten walks {Z^(t)}_1≤ t≤ 10 (in green on the right-hand side of <ref>). The walk Z^(t) starts at height zero at time t.
	Then, 
	
		
  * If Z^(t)_k-1 is non-negative (in particular at the starting point), then the increment Z^(t)_k-Z^(t)_k-1 is the same as the one of the red walk.
		
  * If Z^(t)_k-1 is negative, then the increment Z^(t)_k-Z^(t)_k-1 is the same as the one of the blue walk, as long as this increment keeps Z^(t)_k negative.
		
  * Now if at time k-1, Z^(t)_k-1 is negative but the blue increment would “force” it to cross (or touch) the x-axis (that is if X_k-X_k-1≤ Z^(t)_k-1<0), then Z^(t)_k is equal to Y_k-Y_k-1 (i.e. Z^(t) coalesces with Z^(k-1) at time k). For instance this is the case of the second increment of the walk Z^(7). 
	 
	
	



	The y-coordinates of the coalescent points of a coalescent-walk process in 𝒞(I) are non-negative. 






  §.§.§ The permutation associated with a coalescent-walk process


Given a coalescent-walk process Z = {Z^(t)}_t∈ I defined on a (finite or infinite) interval I, the relation ≤_Z on I defined as follows is a total order (we skip the proof of this fact): 

    i≤_Z j    {i<j  and  Z^(i)_j<0}  or  {j<i  and  Z^(j)_i≥0}  or  {i=j}.

This definition allows to associate a permutation to a coalescent-walk process.

Fix n∈_≥ 0. Let Z = {Z^(t)}_t∈ [n]∈𝒞_n be a coalescent-walk process over [n]. Denote (Z) the permutation σ∈_n such that for 1≤ i, j≤ n, 
	σ(i)≤σ(j)  i≤_Z j.


We have that pattern extraction in the permutation (Z) depends only on a finite number of trajectories, a key step towards proving permuton convergence.



	
	Let σ be a permutation obtained from a coalescent-walk process Z={Z^(t)}_t∈[n] via the map . Let I={i_1<…<i_k}⊂ [n]. Then[See <ref> for notation on patterns of permutations.] _I(σ)=π if the following condition holds: for all 1≤ℓ< s ≤ k, Z^(i_ℓ)_i_s≥ 0  π(s)<π(ℓ).


We end this section with the following observation. Note that given a coalescent-walk process on [n], the plane drawing of the trajectories {Z^(t)}_t∈ I identifies a natural tree structure (Z) as follows (see for instance the middle and right-hand side of <ref>):

	
  * vertices of (Z) correspond to points 1,…,n on the x-axis, plus a root.
	
  * Edges are portions of trajectories starting at the right of a vertex i and interrupted at the first encountered new vertex. Trajectories that do not encounter a new vertex before time n are connected to the root. The label i is also carried by the edge at the right of i.




	In the case where I=[n] for some n∈_≥ 0, the permutation π = (Z) is readily obtained from (Z): it is enough to label the points 1,…,n on the x-axis of the diagram of the colaescent-walk process Z (these labels are painted in purple in the middle picture of <ref>) according to the exploration process of (Z) and then to read these labels from left to right.






 §.§ From plane walks to Baxter permutations via coalescent-walk processes.



We sketch here the proof of <ref>.
The key ingredient is to show that the dual tree T(m^*) of a bipolar orientation can be recovered from its encoding plane walk by building the associated coalescent-walk process Z and looking at the corresponding tree (Z).
More precisely, let W = (W_t)_1≤ t≤ n =  (m) be the walk encoding a given bipolar orientation m, and Z = (W) be the corresponding coalescent-walk process. Then the following result, illustrated by an example in <ref>, holds.

 
		The tree (Z) is equal to the dual tree T(m^*) with edges labeled according to the order given by the exploration of T(m).

The proof requires a lot more notation so we skip it in this extended abstract.  <Ref> then follows immediately, by construction of (m) from T(m^*) and T(m) (<ref>) and of (Z) from (Z) (<ref>).






§ CONVERGENCE TO THE BAXTER PERMUTON

We start this section by representing a uniform random walk in 𝒲_n as a conditioned random walk.
For all n≥ 2, let ^A,_n be the set of plane walks (W_t)_0≤ t≤ n-1 of length n that stay in the non-negative quadrant, starting and ending at (0,0), with increments in A (defined in <ref>). Remark that for n≥ 1, the mapping ^A,_n+2→𝒲_n removing the first and the last step, i.e. W ↦ (W_t)_1≤ t ≤ n,
is a bijection. Recall also that W̅ denotes the walk defined below <ref>. An easy calculation then gives the following (observed also in <cit.>):


	Conditioning on {(W̅_t)_0≤ t≤n+1∈^A,_n+2}, the law of  (W̅_t)_0≤ t ≤ n+1 is the uniform distribution on ^A,_n+2, and the law of (W̅_t)_1≤ t ≤ n is the uniform distribution on 𝒲_n.


As we said in the introduction, a key result to prove <ref> is to determine the scaling limit of coalescent-walk processes encoded by uniform elements of 𝒲_n. Thanks to <ref> we can equivalently study coalescent-walk processes encoded by quadrant walks conditioned to start and end at (0,0). We will first deal with the unconditioned case (see <ref>) and then with the conditioned one (see <ref>).



 §.§ Scaling limits of coalescent-walk processes
 
We start by defining our continuous limiting object: it is formed by the solutions of the following family of stochastic differential equations (SDEs) indexed by u∈, driven by a two-dimensional process W = ( X, Y)

    d Z^(u)(t)    = _{ Z^(u)(t)> 0} d Y(t) - _{ Z^(u)(t)≤ 0} d  X(t),    t≥ u,
     Z^(u)(t)   =0,    t≤ u.

Existence and uniqueness of solutions were already studied in the literature in the case where the driving process W is a Brownian motion, in particular with the following result.

	
	Let I be a (finite or infinite) interval of ℝ and fix t_0∈ I. Let W = ( X, Y) denote a two-dimensional Brownian motion on  I with covariance matrix [ 1 ρ; ρ 1 ] for ρ∈ (-1,1). We have path-wise uniqueness (explained in 1 below) and existence (explained in 2 below) of a strong solution for the SDE:
	
    d  Z(t)    = _{ Z(t)> 0} d  Y(t) - _{ Z(t)≤ 0} d  X(t),     t∈ I∩[t_0,+∞),
     Z(t_0)   =0.

	Namely, letting (Ω, ℱ, (ℱ_t)_t∈ I, ) be a filtered probability space satisfying the usual conditions, and assuming that ( X, Y) is an (ℱ_t)_t-Brownian motion, 
	
		
  * if Z, Z^⋆ are two (ℱ_t)_t-adapted continuous processes that verify <ref> almost surely, then Z= Z^⋆ almost surely.
		
  * There exists an (ℱ_t)_t-adapted continuous process Z which verifies <ref> almost surely, and is adapted to the completion of the canonical filtration of ( X, Y).
	




  §.§.§ The unconditioned scaling limit result

Let us now work on the completed canonical filtered probability space of a Brownian motion W = ( X,  Y) with covariance [    1 -1/2; -1/2    1 ]. For u∈, let Z^(u) be the strong solution of <ref> with I=[u,∞) and t_0=u, provided by <ref>. Note that Z^(u) satisfies <ref> (only) for almost all ω. For every u, Z^(u) is adapted, and it is simple to see that the map (ω,u)↦ Z^(u) is jointly measurable. By Tonelli's theorem, for almost every ω, Z^(u) is a solution for almost every u.

	For fixed u, Z^(u) is a Brownian motion on [u,∞). Note however that the coupling of Z^(u) for different values of u is highly non trivial.



	Given ω (even restricted to a set of probability one), we cannot say that ( Z^(u))_u∈ forms a whole field of solutions to <ref>, since we cannot guarantee that the SDE holds for all u simultaneously. Similarly, it is expected that there exists exceptional u where uniqueness fails.


Now, let W̅ = (X̅,Y̅) =(X̅_k,Y̅_k)_k∈ be the random plane walk defined below <ref>, and Z̅ = (W̅) be the corresponding coalescent-walk process. 
We define rescaled versions: for all n≥ 1, u∈, let W̅_n:→^2 and Z̅^(u)_n:→ be the continuous functions defined by linearly interpolating the following points:

    W̅_n(k/n) = 1/√(2n)W̅_k,   k∈,     Z̅^(u)_n(k/n) = 1/√(2n)Z̅^(⌊ nu⌋)_k,   u∈, k∈.

Our most important technical result is the following theorem (whose proof is postponed to <ref>).

	Let u_1< … < u_k. 
	We have the following joint convergence in (𝒞(,))^k+2: 
	
    (W̅_n,Z̅^( u_1)_n,…,Z̅^(u_k)_n) 
    	( W, Z^(u_1),…, Z^(u_k)).






  §.§.§ The conditioned scaling limit result


As a standard application of <cit.>, the scaling limit of the random walk W̅_n conditioned on starting at the origin at time 0 and ending at the origin at time n+1 is W_e=( X_e,  Y_e), the Brownian excursion in the non-negative quadrant of covariance [    1 -1/2; -1/2    1 ]. Let us denote by (Ω, ℱ, (ℱ_t)_0≤ t ≤ 1, _) the completed canonical probability space of W_e, and work from now on in that space.

It makes sense that the scaling limit of the coalescent-walk process in this conditioned setting should be the solution of <ref> driven by W_e, for which we have to show existence and uniqueness. First, let us remark that since Brownian excursions are semimartingales, stochastic integrals are still well-defined. We skip the rather abstract proof of the following, which relies on absolute continuity between Brownian excursion and Brownian motion:



	Denote ℱ^(u)_t = σ ( W_e(s)- W_e(u), u≤ s ≤ t) completed by the _-negligible sets of Ω. 
	There is a jointly measurable map (ω, u)↦ Z_e^(u) such that for all u, 
	Z_e^(u) is (ℱ^(u)_t)_t-adapted, and
	almost surely, for almost every u, Z_e^(u) solves <ref> driven by W_e. Moreover, for u∈(0,1), if Z^⋆ is another (ℱ^(u)_t)_t-adapted solution of <ref> driven by W_e started at time u, then Z^⋆ =  Z_e^(u) almost surely.


From the above result and the discrete absolutely continuity arguments of <cit.>, we can deduce the following analogous result of <ref> (whose proof is omitted). We use the same notation as in <ref>, and state the result for uniform random times for later convenience.



	
	Let u_1< … <  u_k be k sorted independent continuous uniform random variables on [0,1], independent from all other random variables. We have the following convergence in (𝒞([0,1],))^k+2: 
	
    (W̅_n,Z̅^( u_1)_n,…,Z̅^( u_k)_n|(W̅_t)_0≤ t≤n+1∈^A,_n+2)
    	( W_e, Z_e^( u_1),…, Z_e^( u_k)).








 §.§ The construction of the limiting object



We introduce the limiting coalescent Baxter permuton. We place ourselves in the probability space defined above, where W_e=( X_e,  Y_e) is a Brownian excursion of correlation -1/2 conditioned to stay in the non-negative quadrant. Let
Z_e={ Z_e^(u)}_u∈ [0,1] be the family of processes given by <ref>, which almost surely solves <ref> driven by W_e for almost every u. From the continuous coalescent-walk process Z_e we build a binary relation ≤_ Z_e on [0,1] defined as in <ref>. Clearly, (ω, x,y)↦_x≤_ Z_e y is measurable, and we have the following property whose proof, which relies on path-wise uniqueness, is skipped.
 The relation ≤_ Z_e is a total order on [0,1]∖ A, where A is a random set of zero Lebesgue measure.
We then define the following random function (note that (ω, t)↦φ_ Z_e(t) is measurable):

    φ_ Z_e(t)( {x∈[0,1]|x ≤_ Z_e t})=( {x∈[0,t)| Z^(x)_e(t)<0}∪{x∈[t,1]| Z^(t)_e(x)≥0}),

where here (·) denotes the one-dimensional Lebesgue measure.
We define the coalescent Baxter permuton as the push-forward of the Lebesgue measure via the map (,φ_ Z_e), i.e.

    μ_B (·)= μ_ Z_e(·)(,φ_ Z_e)_* (·)=({t∈[0,1]|(t,φ_ Z_e(t))∈ · }).


We try to give an intuition behind the definition of μ_B. Recall that given a coalescent-walk process Z={Z^(t)}_t∈[n]∈𝒞, we can associate to it the corresponding Baxter permutation σ=(Z) and the total order ≤_Z on [n]. The permutation σ satisfies the following property: for every i∈ [n], σ(i)=|{j∈[n]|j≤_Z i}|.
The function φ_ Z_e is a continuous analogue of the permutation σ, when we consider the continuous coalescent-walk process Z_e instead of a discrete one, and μ_ Z_e is the associated permuton.


The following result is proved as <cit.>, relying on <ref>.

	Almost surely, μ_ Z_e is a permuton. 

The final proof of <ref>, i.e. the convergence of uniform Baxter permutations to μ_B, can be found in <ref>. We give here a short sketch. The proof is based on the analysis of pattern extraction from uniform Baxter permutations. <ref> relates the probability of extracting a specific pattern to the probability that some trajectories of the corresponding coalescent-walk process have given signs at given times. Then, by <ref>, the latter converges to the analogue probability for the limiting continuous coalescent-walk process.








§ THE PROOF OF <REF>


Recall that W̅ = (X̅,Y̅) =(X̅_k,Y̅_k)_k∈ is the random plane walk defined below <ref>, and Z̅ = (W̅) is the corresponding coalescent-walk process. We need the following result whose proof is left to the complete version of this extended abstract.


	For every u∈, Z̅^(u) has the distribution of a random walk with the same step distribution as Y̅ (which is the same as that of -X̅).



	Recall that the increments of a walk of a coalescent-walk process are not always equal to one of the increments of the corresponding walk (see for instance <ref>). The statement of <ref> is a sort of “miracle” of the geometric distribution.



	The first step in the proof is to establish convergence of the components of the vector on the left-hand side of <ref>.
	By a classical invariance principle, we get that W̅_n=(X̅_n,Y̅_n) converges to W=( X,  Y) in distribution. Using <ref>, and applying again the invariance principle, we get that (Z̅^(u)_n(u+t))_t≥ 0, converges to a one-dimensional Brownian motion. This gives the marginal convergence thanks to <ref>.
	
	The second step in the proof is to establish joint convergence. Marginal convergence gives joint tightness, so that by Prokhorov's theorem, to show convergence, one only needs to identify the distribution of all joint subsequential limits. Assume that along a subsequence, we have 
		
    (W̅_n,Z̅^( u_1)_n,…,Z̅^(u_k)_n) 
    		( W,Z̃_̃1̃,…,Z̃_̃k̃).

	Using Skorokhod's theorem, we may define all involved variables on the same probability space and assume that the convergence is almost sure. The joint distribution of the right-hand-side is unknown for now, but we will show that for every 1≤ i ≤ k, Z̃_̃ĩ =  Z^(u_i) a.s., which would complete the proof. Recall that Z^(u_i) is the strong solution of <ref>, started at time u_i and driven by W =( X, Y), which exists thanks to <ref>.	
	Let us now fix i and abbreviate u=u_i,  Z̃ = Z̃_̃ĩ. Our goal is to show that Z̃ also verifies <ref> and apply path-wise uniqueness.	
		
	Let ℱ_t = σ( W(s),Z̃(s), s≤ t). This gives a filtration for which W and Z̃ are adapted.
	We will show that W is an (ℱ_t)_t-Brownian motion, that is for t∈, s≥ 0, 
	( W(t+s)- W(t)) ℱ_t. 
	For fixed n, by definition of a random walk, W̅_n(t+s) - W̅_n(t) is independent from σ(W̅_k, k≤⌊ n t ⌋). Therefore, by the definition given in <ref>,
	
    (W̅_n(t+s)-W̅_n(t))   (W̅_n(r),Z̅^(u)_n(r))_r≤ n^-1⌊ nt ⌋.

	By convergence, we obtain that W(t+s)- W(t) is independent from ( W(r),Z̃(r))_r≤ t, completing the claim that W is an (ℱ_t)_t-Brownian motion.
	
	Now fix a rational >0 and a rational t>u such that Z̃(t)>. There is δ>0 so that Z̃>/2 on [t-δ,t+δ]. By almost sure convergence, there is N_0 such that for n≥ N_0, Z̅^(u)_n>/4 on [t-δ,t+δ]. 
	On this interval, outside of the event 
	
    {sup_1≤ i  ≤ n  |Y̅_i - Y̅_i-1|≥√(2n)/4},

	Z̅^(u)_n - Y̅_n is constant  by construction of the coalescent-walk process. As a result (the probability of the bad event is bounded by Ce^-c√(n) ), the limit Z̃ -  Y is constant too almost surely. We have shown that almost surely Z̃ -  Y is locally constant on {t:Z̃(t)>}. This translates into the following equality:
	
    ∫_u^t _{Z̃(r)>} dZ̃(r) = ∫_u^t _{Z̃(r)>} d Y(r).

	The stochastic integrals are well-defined: on the left-hand side by considering the canonical filtration of Z̃, on the right-hand-side by considering (ℱ_t)_t.	
	The same can be done for negative values, leading to 
	
    ∫_u^t _{|Z̃(r)|>} dZ̃(r)  =  ∫_u^t _{Z̃(r)>} d Y(r) -  ∫_u^t _{Z̃(r)<-} d X(r).

	
	By stochastic dominated convergence theorem <cit.>, one can take the limit as → 0,  and obtain 
	
    ∫_u^t _{Z̃(r)≠0}dZ̃(r)  =  ∫_u^t _{Z̃(r)>0} d Y(r) -  ∫_u^t _{Z̃(r)<0} d X(r).

	Thanks to the fact that Z̃ is Brownian, ∫_u^t _{Z̃(r)=0}dZ̃(r) = 0, so that the left-hand side equals Z̃(t).
	As a result Z̃ verifies <ref> and we can apply path-wise uniqueness (<ref>) to complete  the proof.






§ THE PROOF OF <REF>


Recall that permuton convergence has been defined in <ref>. We present one its characterizations (which comes from <cit.>), expressed in terms of random induced patterns. For n∈_>0, we denote by _n the set of permutations of size n. Let 1≤ k≤ n, σ∈_n and I = {i_1,… i_k} with 1≤ i_1<…<i_k≤ n. The pattern in σ induced by I is the only permutation π∈_k such that the k values σ(i_1),…, σ(i_k) are order isomorphic to π(1),…, π(k). In this case, we write _I(σ)=π.


We also define permutations induced by k points in the square [0,1]^2. Take a sequence of k points (X,Y)=((x_1,y_1),…, (x_k,y_k)) in [0,1]^2 in general position, i.e. with distinguished x and y coordinates. 
We denote by (x_(1),y_(1)),…, (x_(k),y_(k)) the x-reordering of (X,Y),
i.e. the unique reordering of the sequence ((x_1,y_1),…, (x_k,y_k)) such that
x_(1)<⋯<x_(k).
Then the values (y_(1),…,y_(k)) are in the same
relative order as the values of a unique permutation, that we call the permutation induced by (X,Y).


	 Let σ_n be a random permutation of size n, and I_n^k={ i^1_n,…, i^k_n} be a uniform k-element subset of [n], independent of σ_n. Let  μ be a random permuton, and denote _k(μ) the unique permutation[Note that if μ is a permuton, then it has uniform marginals and so the x and y coordinates of k points sampled according to μ are a.s. distinct.] induced by k independent points in [0,1]^2 with common distribution μ conditionally[This is possible by considering the new probability space described in <cit.>.] on μ. Then
	 
    μ_σ_nd→μ∀ k ∈_>0, ∀π∈_k,  (_ I_n^k(σ_n)=π) →(_k(μ) = π).





We can now prove <ref>. First we state a consequence of the fact that μ_ Z_e is a permuton and that Z_e^(s)(t) are continuous random variables, which allows us to get rid of equalities:

	Almost surely, for almost every s<t∈[0,1], 
	Z_e^(s)(t)≠ 0. Then Z_e^(s)(t)>0 implies φ_ Z_e(s)<φ_ Z_e(t), and  Z_e^(s)(t)<0 implies φ_ Z_e(s)>φ_ Z_e(t).



	We reuse here the notation of <ref>. In particular W̅ is a ν-random walk and Z̅ = (W̅) is the associated coalescent-walk process. Let σ_n = (Z̅|_[n]). Let ℰ_n denote the event {(W̅_t)_0≤ t≤n+1∈^A,_n+2}. By <ref> and the fact that the mapping ∘ is a size-preserving bijection, conditioned on ℰ_n, σ_n is a uniform Baxter permutation.

	Fix k≥ 1 and π∈_k. For n≥ k, let I_n={ i^1_n,…, i^k_n} be a uniform k-element subset of [n], independent of σ_n.
	In view of <ref>, to complete the proof, we will show that 
	
    (_ I_n(σ_n)=π|ℰ_n) (_k(μ_ Z_e) = π).

	Thanks to <ref>, we have
	
    (_ I_n(σ_n )=π|ℰ_n)
    	=( ∀_1≤ℓ< s≤ k, Z̅^( i^ℓ_n)_ i^s_n≥ 0 π(ℓ)>π(s)|ℰ_n).

	Let ( u_1,…, u_k) be the sorted vector of k independent uniform continuous random variables in [0,1]. For every n≥ 1, one can couple I_n and ( u_1,…, u_k) so that i_n^j = ⌊ n  u_j ⌋ for every 1≤ j ≤ k, with an error of probability O(1/n). As a result, 

	
    (_ I_n(σ_n )=π|ℰ_n)=   (∀_1≤ℓ< s≤ k, (2n)^-1/2Z̅^( u_ℓ)_ u_s≥ 0 π(ℓ)>π(s) |ℰ_n )+ O(1/n) 
       (∀_1≤ℓ< s≤ k,  Z^( u_ℓ)_e( u_s)≥ 0 π(ℓ)>π(s)) 
    
    	=   (∀_1≤ℓ< s≤ k, 
    	π(ℓ)>π(s) φ_ Z_e( u_ℓ)>φ_ Z_e( u_s)
    π(ℓ)<π(s) φ_ Z_e( u_ℓ)<φ_ Z_e( u_s)
    	),

	where for the limit we used the convergence in distribution of <ref> together with the Portmanteau theorem. Additionally, <Ref> is used both to take care of the boundary effect in the Portmanteau theorem, and to do the rewriting in the last line.

	In order to finish the proof, it is enough to check that the probability on the right-hand side of <ref> equals (_k(μ_ Z_e) = π). This is clear since by definition of _k and μ_ Z_e,  _k(μ_ Z_e) is the permutation induced by
	(( u_1,φ_ Z_e( u_1)),…, ( u_k,φ_ Z_e( u_k))).





§ SIMULATIONS OF LARGE BAXTER PERMUTATIONS


The simulations for Baxter permutations presented in the first page of this extended abstract have been obtained in the following way:

	
  * first, we have sampled a uniform random walk of size n+2 in the non-negative quadrant starting at (0,0) and ending at (0,0) with increments distribution given by <ref>. This has been done using a "rejection algorithm": it is enough to sample a walk W starting at (0,0) with increments distribution given by <ref>, up to the first time it leaves the non-negative quadrant. Then one has to check if the last step inside the non-negative quadrant is at the origin (0,0). When this is the case (otherwise we resample a new walk), the part of the walk W inside the non-negative quadrant, denoted W̃, is a uniform walk of size |W̃| in the non-negative quadrant starting at (0,0) and ending at (0,0) with increments distribution given by <ref>.
	
  * Removing the first and the last step of W̃, thanks to <ref>, we obtained a uniform random walk in 𝒲_n.
	
  * Finally, applying the mapping ∘ to the walk given by the previous step, we obtained a uniform Baxter permutation of size n (thanks to <ref>).

Note that our algorithm gives a uniform Baxter permutation of random size.




