Search

The structure of the three pattern classes defined by the sets of forbidden permutations $\{2143, 4321\}$, $\{2143, 4312\}$ and $\{1324, 4312\}$ is determined using the machinery of monotone grid classes. This allows the permutations in these classes to be described in terms of simple diagrams and regular languages and, using this, the rational generating functions which enumerate these classes are determined.

Pattern classes which avoid $321$ and other patterns are shown to have the same growth rates as similar (but strictly larger) classes obtained by adding articulation points to any or all of the other patterns. The method of proof is to show that the elements of the latter classes can be represented as bounded merges of elements of the original class, and that the bounded merge construction does not change growth rates.

A complete structural description and enumeration is found for permutations that avoid both $1324$ and $4231$.

We introduce the insertion encoding, an encoding of finite permutations. Classes of permutations whose insertion encodings form a regular language are characterized. Some necessary conditions are provided for a class of permutations to have insertion encodings that form a context free language. Applications of the insertion encoding to the evaluation of generating functions for classes of permutations, construction of polynomial time algorithms for enumerating such classes, and the illustration of bijective equivalence between classes are demonstrated.

A fork stack is a generalised stack which allows pushes and pops of several items at a time. We consider the problem of determining which input streams can be sorted using a single forkstack, or dually, which permutations of a fixed input stream can be produced using a single forkstack. An algorithm is given to solve the sorting problem and the minimal unsortable sequences are found. The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time. In this context we also establish how to enumerate the collection of sortable sequences.

The density of a permutation pattern $\pi$ in a permutation $\sigma$ is the proportion of subsequences of $\sigma$ of length $|\pi|$ that are isomorphic to $\pi$. The maximal value of the density is found for several patterns $\pi$, and asymptotic upper and lower bounds for the maximal density are found in several other cases. The results are generalised to sets of patterns and the maximum density is found for all sets of length $3$ patterns.

In the game of End-Nim two players take turns in removing one or more boxes from a string of non-empty stacks. At each move boxes may only be taken from the two stacks which form the ends of the string (unless only one stack remains!). We give a solution for both impartial and partizan versions of the game and explain the significance of the mystic hieroglyphs: $$ \begin{array}{|cc|} \hline \uparrow & \downarrow \\ \downarrow & \uparrow \\ \hline \end{array} $$

The edges of the complete graph $K_n$ are coloured so that no colour appears more than $\lceil cn\rceil$ times, where $c < 1/32$ is a constant. We show that if $n$ is sufficiently large then there is a Hamiltonian cycle in which each edge is a different colour, thereby proving a 1986 conjecture of Hahn and Thomassen. We prove a similar result for the complete digraph with $c < 1/64$. We also show, by essentially the same technique, that if $t\geq 3$, $c < (2t^2(1+t))^{-1}$, no colour appears more than $\lceil cn\rceil$ times and $t|n$ then the vertices can be partitioned into $n/t$ $t-$sets $K_1,K_2,\ldots,K_{n/t}$ such that the colours of the $n(t-1)/2$ edges contained in the $K_i$'s are distinct. The proof technique follows the lines of Erdős and Spencer's modification of the Local Lemma.