Selected problems in enumerative combinatorics: permutation classes, random walks and planar maps

Abstract

In this thesis we consider a number of enumerative combinatorial problems. We solve the problems of enumerating Eulerian orientations by edges and quartic Eulerian orientations counted by vertices. We also find and prove an algebraic relationship between the counting functions for permutations sortable by a double ended queue (deque) and permutations sortable by two stacks in parallel (2sip). In each of these cases, our proof of the result uses an elaborate system of functional equations which is much more complicated than the result itself, leaving the door open for a more direct, combinatorial proof.

We find polynomial time algorithms for generating the counting sequence of deque-sortable permutations and the cogrowth sequence of some groups, including the lamplighter group $L$ and the Brin-Navas group $B$. For permutations sortable by two stacks in series and for the cogrowth sequence of Thompson's group $F$, we find exponential time algorithms which are significantly more efficient than the algorithms that previously existed in the literature. In each case an empirical analysis of the produced terms of the sequence leads to a prediction regarding its asymptotic form. In particular, this method leads us to conjecture that the growth rate of deque-sortable permutations is equal to that of 2sip-sortable permutations, a conjecture which we reduce to three conjectures of Albert and Bousquet-M\'elou about quarter plane walks. The analysis of the cogrowth sequence of Thompson's group $F$ leads us to conjecture that $F$ is not amenable.

We also study the enumeration of $1324$-avoiding permutations, a notoriously difficult problem in the field of pattern avoiding permutations. Using a structural decomposition of these permutations, we improve the lower and upper bounds on the growth rate to $10.271$ and $13.5$ respectively.

Next we investigate the concept of combinatorial Stieltjes moment sequences. We prove that the counting sequence of returns in any undirected locally-finite graph is a Stieltjes moment sequence. As a special case, this implies that any cogrowth sequence is a Stieltjes moment sequence. Based on empirical evidence, we conjecture that the counting sequence for $1324$-avoiding permutations is a Stieltjes moment sequence, which would imply an improved lower bound of $10.302$ on its growth rate.

We then describe a general class of counting sequences of augmented perfect matchings, which we prove to be Stieltjes moment sequences. In fact, we prove the stronger result that these sequences are Hankel totally-positive as sequences of polynomials. As a special case, we show that the Ward polynomials are Hankel totally-positive.

In the final chapter we generalise an identity of Duminil-Copin and Smirnov for the $O(n)$ loop model on the hexagonal lattice to the off-critical case. In the $n=0$ case, which corresponds to the enumeration of self-avoiding walks, we use our identity to prove a relationship between the half-plane surface critical exponents $\gamma_{1}$ and $\gamma_{11}$ and the exponent characterising the winding angle distribution of self-avoiding walks in the half-plane.