Rational Catalan combinatorial objects and algorithms

Abstract

The Catalan numbers and mathematical objects enumerated by them have been studied since the 1700’s. The study of these objects, related objects, and bijections between them is called Catalan combinatorics. In this thesis, we discuss three areas of Catalan combinatorics. First, we discuss rational parking functions and the Pak-Stanley bijection from rational parking functions to alcoves of the Sommers region. Second, we discuss the combinatorics of the polytope created by taking the convex hull over all vector-parking functions. Last, we discuss planar tanglegrams, and provide an algorithm to generate them uniformly at random. An (m, n)-parking function can be characterized as a function f : [n] → [m] such that the partition obtained by reordering the values of f fits inside a right triangle with legs of length m and n. Recent work by McCammond, Thomas, and Williams define an action of words in [m]n on Rn. They show that rational parking functions are exactly the words that admit fixed points under that action. An (m, n)-invariant set is a set ∆ ⊂ Z such that ∆ + m ⊂ ∆ and ∆ + n ⊂ ∆. In the first part of this thesis we define an action of words in [m]n on m-invariant sets by removing the jth m-generator from ∆. We show this action also characterizes (m, n)-parking functions. Further, we show that each (m, n)-invariant set is fixed by a unique monotone parking function. By relating the actions on Rm and on (m, n)-invariant sets we prove that the set of all the points in Rm that can be fixed by a parking function is a union of points fixed by monotone parking functions. In the case when gcd(m, n) = 1 we characterize the set of periodic points of the action defined on Rm and show that the algorithm conjectured by Gorsky, Mazin, and Vazirani becomes affine periodic and provides an inverse to the Pak-Stanley map. For b = (b1, . . . , bn) ∈ Zn >0, a b-parking function is defined to be a sequence (β1, . . . , βn) of positive integers whose nondecreasing rearrangement β′ 1 ≤ β′ 2 ≤ · · · ≤ β′ n satisfies β′ i ≤ b1 + · · · + bi. The b-parking-function polytope Xn(b) is the convex hull of all b-parking functions of length n in Rn. Geometric properties of Xn(b) were previously explored in the specific case where b = (a, b, b, . . . , b) and were shown to generalize those of the classical parking-function polytope. In the second part of this thesis, we study Xn(b) in full generality. We present a minimal inequality and vertex description for Xn(b), prove it is a generalized permutahedron, and study its h-polynomial. Furthermore, we investigate Xn(b) through the perspectives of building sets and polymatroids, allowing us to identify its combinatorial types and obtain a bound on its combinatorial diameter. A tanglegram consists of two rooted binary trees and a perfect matching between their leaves, and a planar tanglegram is one that admits a layout with no crossings. In the third part of this thesis we show that the problem of generating planar tanglegrams uniformly at random reduces to the corresponding problem for irreducible planar tanglegram layouts, which are known to be in bijection with pairs of disjoint triangulations of a convex polygon. We extend the flip operation on a single triangulation to a flip operation on pairs of disjoint triangulations. Interestingly, the resulting flip graph is both connected and regular, and hence a random walk on this graph converges to the uniform distribution. We also show that the restriction of the flip graph to the pairs with a fixed triangulation in either coordinate is connected and give diameter bounds that are near optimal. Our results furthermore yield new insight into the flip graph of triangulations of a convex n-gon with a geometric interpretation on the associahedron.