Randomised algorithms are an effective method of attacking computationally intractable problems. A simple and fast randomised algorithm may produce results to an accuracy sufficient for many purposes, especially in the average case. In this thesis we consider average case analyses of heuristics for certain NP-hard graph optimisation problems. In particular, we consider algorithms that find dominating sets of random regular directed graphs. As well as providing an average case analysis, our results also determine new upper bounds on domination numbers of random regular directed graphs. The algorithms for random regular directed graphs considered in this thesis are known as prioritised algorithms. Each prioritised algorithm determines a discrete random process. This discrete process may be continuously approximated using differential equations. Under certain conditions, the solutions to these differential equations describe the behaviour of the prioritised algorithm. Applying such an analysis to prioritised algorithms directly is difficult. However, we are able to use prioritised algorithms to define new algorithms, called deprioritised algorithms, that can be analysed in this fashion. Defining a deprioritised algorithm based on a given prioritised algorithm, and then analysing the deprioritised algorithm, is called the deprioritised approach. The initial theory describing the deprioritised approach was developed by Wormald and has been successfully applied in many cases. However not all algorithms are covered by Wormald??s theory: for example, algorithms for random regular directed graphs. The main contribution of this thesis is the extension of the deprioritised approach to a larger class of prioritised algorithms. We demonstrate the new theory by applying it to two algorithms which find dominating sets of random regular directed graphs.

This thesis consists of the manuscripts of two research papers. In the first paper, we verify a recent conjecture of Kenyon/Szendroi by computing the generating function for pyramid partitions. Pyramid partitions are closely related to Aztec Diamonds; their generating function turns out to be the partition function for the Donaldson-Thomas theory of a non-commutative resolution of the conifold singularity {x₁ x₂ - x₃ x₄ = 0}⊂ C⁴. The proof does not require algebraic geometry; it uses a modified version of the domino (or dimer) shuffling algorithm of Elkies, Kuperberg, Larsen and Propp. In the second paper, we derive two multivariate generating functions for three-dimensional Young diagrams (also called plane partitions). The variables correspond to a colouring of the boxes according to a finite abelian subgroup G of SO(3). These generating functions turn out to be orbifold Donaldson-Thomas partition functions for the orbifold [C³/G]. We need only the vertex operator methods of Okounkov-Reshetikhin-Vafa for the easy case G = Zn; to handle the considerably more difficult case G = Z₂ x Z₂ , we will also use a refinement of the author's recent q-enumeration of pyramid partitions. In the appendix, written by Jim Bryan, we relate the diagram generating functions to the Donaldson-Thomas partition functions of the orbifold [C³/G]. We find a relationship between the Donaldson-Thomas partition functions of the orbifold and its G-Hilbert scheme resolution. We formulate a crepant resolution conjecture for the Donaldson-Thomas theory of local orbifolds satisfying the Hard Lefschetz condition. / Science, Faculty of / Mathematics, Department of / Graduate

In this dissertation, we treat several problems in Ramsey theory, probabilistic combinatorics and extremal graph theory.

This thesis provides an introduction to the theory of tropical mutation schemes, and computes explicit examples. Tropical mutation schemes generalize toric geometry. The study of toric varieties is a popular area of algebraic geometry, due to toric varieties' strong combinatorial interpretations. In particular, the characters and one-parameter subgroups of the rank $r$ algebraic torus form a pair of dual lattices of rank $r$, isomorphic to $\mathbb{Z}^r$. We can then construct toric varieties from fans in these lattices, and compactifications of the algebraic torus are parametrized by full dimensional convex polytopes. A tropical mutation scheme is a finite collections of lattices, equipped with bijective piecewise-linear functions between each pair of lattices, where these functions satisfy certain compatibility conditions. They generalize lattices in the sense that a lattice can be viewed as the trivial tropical mutation scheme. We also introduce the space of points of a tropical mutation scheme, which is the set of functions from a tropical mutation scheme to $\mathbb{Z}$ which satisfy a minimum condition. A priori, the structure of the space of points of a tropical mutation scheme is unknown, but in certain cases can be identified by the elements of another tropical mutation scheme, inducing a dual pairing between the two tropical mutation schemes. When we have a strict dual pairing of tropical mutation schemes, we can sometimes construct an algebra to be a detropicalization of the pairing. In the trivial case, the coordinate ring of the algebraic torus is a detropicalization of a single lattice and its dual. Thus, when we can construct a detropicalization for a non-trivial strict dual pairing, we recover much of the useful combinatorics from the toric case. This thesis shows that all rank 2 tropical mutation schemes on two lattice charts are autodual, meaning there is a dual pairing between the tropical mutation scheme and its own space of points. Furthermore, we construct a detropicalization for these tropical mutation schemes. We end the thesis by reviewing open questions and future directions for the theory of tropical mutation schemes. / Thesis / Master of Science (MSc) / Informally, algebraic geometry is the study of solution sets to systems of polynomial equations, called algebraic varieties. Such systems are ubiquitous across the sciences, being found as biological models, optimization problems, revenue models, and much more. However, it is a difficult problem in general to ascertain salient properties of the solutions to these systems. One type of algebraic variety which is easier to work with is a toric variety. These varieties can be associated to simpler mathematical objects such as lattices, polytopes and fans, and important geometric properties of the variety can then be obtained via analyzing properties of these simpler objects. This thesis introduces the notion of a tropical mutation scheme, which is a generalization of a lattice. A broader class of algebraic varieties can be associated with tropical mutation schemes in a similar manner to how toric varieties are associated with lattices. We then compute this association explicitly in the case of the simplest non-trivial examples of a tropical mutation scheme, rank 2 tropical mutation schemes with 2 charts.

No description available.

We study the representations of the symmetric group $S_n$ found by acting on labeled graphs and trees with $n$ vertices. Our main results provide combinatorial interpretations that give the number of times the irreducible representations associated with the integer partitions $(n)$ and $(1^n)$ appear in the representations. We describe a new sign reversing involution with fixed points that provide a combinatorial interpretation for the number of times the irreducible associated with the integer partition $(n-1, 1)$ appears in the representations.

Here we investigate a variety of ways to represent polytopes and related objects. We define a class of posets, which includes all abstract polytopes, giving a unique representative among posets having a particular labeled flag graph and characterize the labeled flag graphs of abstract polytopes. We show that determining the realizability of an abstract polytope is equivalent to solving a low rank matrix completion problem. For any given polytope, we provide a new construction for the known result that there is a combinatorial polytope with a specified ridge that is always projectively equivalent to the given polytope, and we show how this makes a naturally arising subclass of intractable problems tractable. We give necessary and sufficient conditions for realizing a polytope's interval poset, which is the polytopal analog of a poset's Hasse diagram. We then provide a counter example to the general realizablity of a polytope's interval poset. / Mathematics

The manufacturer claims that there is only one solution to the puzzle Instant Insanity II. However, a recent paper shows that there are two solutions. Our goal is to find ways in which we only have one solution. We examine the permutation groups of the puzzle and use modern algebra to attempt to fix the puzzle. First, we find the permutation group for the case when there is only one empty slot at the top. We then examine the scenario when we add an extra column or an extra row to make the game a 4 × 5 puzzle or a 5 x 4 puzzle, respectively. We consider the possibilities when we delete a color to make the game a 3 × 3 puzzle and when we add a color, making the game a 5 × 5 puzzle. Finally, we determine if solution two is a permutation of solution one.

A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.

The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by Bollobás in 1984 in connection to k-connected subgraphs of random graphs. Subsequently, k-cores and their properties have been extensively investigated in random graphs and hypergraphs, with the determination of the threshold for the emergence of a giant k-core, due to Pittel, Spencer and Wormald, as one of the most prominent results. In this thesis, we obtain an asymptotic formula for the number of 2-connected graphs, as well as 2-edge-connected graphs, with given number of vertices and edges in the sparse range by exploiting properties of random 2-cores. Our results essentially cover the whole range for which asymptotic formulae were not described before. This is joint work with G. Kemkes and N. Wormald. By defining and analysing a core-type structure for uniform hypergraphs, we obtain an asymptotic formula for the number of connected 3-uniform hypergraphs with given number of vertices and edges in a sparse range. This is joint work with N. Wormald. We also examine robustness aspects of k-cores of random graphs. More specifically, we investigate the effect that the deletion of a random edge has in the k-core as follows: we delete a random edge from the k-core, obtain the k-core of the resulting graph, and compare its order with the original k-core. For this investigation we obtain results for the giant k-core for Erdős-Rényi random graphs as well as for random graphs with minimum degree at least k and given number of vertices and edges.