A dissection is a union of a convex polygon and some diagonals that intersect only at their endpoints (see Figure 1). We are interested in the graph-theoretical properties of a random dissection, and in particular, the maximum vertex degree.

The main challenge here lies in identifying decompositions of a dissection whose degrees are partially known. To overcome this, we move to the context of dual trees (see Figure 1), where natural decompositions can be identified.

Our main result is a concentration inequality for the maximum vertex degree. This settles a conjecture posed in this paper.

This paper has been posted on the arXiv here.

Figure 1: A dissection and its dual tree. 

A composition of n ≥ 1 is a tuple of positive integers summing to n. These objects can be associated with diagrams of boxes (see Figure 2). In this context, a simple way to construct a Markov process is by fixing an initial diagram and sequentially constructing a new diagram from an old one by randomly rearranging its boxes. In our case, these rearrangements are inspired by the Chinese Restaurant Process (CRP). We are interested in the behavior of these processes as the number of boxes gets large.

To analyze the limit of our processes, we use generators. As usual, the challenge here is that explicit computations are difficult. However, a connection to quasi-symmetric functions allows us to overcome this.

Our main result is the convergence of our processes (in some sense) to a Feller diffusion that we describe explicitly through its generator. These diffusions provide natural ordered analogues to the diffusions constructed here.

This paper has been posted on the arXiv here.

Figure 2: The diagram for the composition (2, 3, 1, 4).

Each composition process studied above has an associated leftmost column process, obtained by projecting onto the first coordinate. We are interested in studying the limiting behavior of these processes, since they provide insight into the above diffusions.

Before our analysis, we first establish the Markov property. This is done by establishing an intertwining relation between the leftmost column and its composition process (see Figure 3).

To study the limiting behavior, we identify another intertwining relation – this time between the leftmost columns and some Feller process on [0, 1]. We then establish a general result that yields convergence from intertwining.

In addition, we relate the limiting process here to the diffusions of our previous work.

This paper has been posted on the arXiv here.

Figure 3: The intertwining relation is a commuting diagram between transition kernels, represented as arrows.