Random planar graphs have been the subject of much recent work. Many basic properties of the standard uniform random planar graph $P_{n}$, by which we mean a graph chosen uniformly at random from the set of all planar graphs with vertex set $ { 1,2, ldots, n }$, are now known, and variations on this standard random graph are also attracting interest. Prominent among the work on $P_{n}$ have been asymptotic results for the probability that $P_{n}$ will be connected or contain given components/ subgraphs. Such progress has been achieved through a combination of counting arguments cite{mcd} and a generating function approach cite{gim}. More recently, attention has turned to $P_{n,m}$, the graph taken uniformly at random from the set of all planar graphs on ${ 1,2, ldots, n }$ with exactly $m(n)$ edges (this can be thought of as a uniform random planar graph with a constraint on the average degree). In cite{ger} and cite{gim}, the case when $m(n) =~!lfloor qn floor$ for fixed $q in (1,3)$ has been investigated, and results obtained for the events that $P_{n, lfloor qn floor}$ will be connected and that $P_{n, lfloor qn floor}$ will contain given subgraphs. In Part I of this thesis, we use elementary counting arguments to extend the current knowledge of $P_{n,m}$. We investigate the probability that $P_{n,m}$ will contain given components, the probability that $P_{n,m}$ will contain given subgraphs, and the probability that $P_{n,m}$ will be connected, all for general $m(n)$, and show that there is different behaviour depending on which `region' the ratio $rac{m(n)}{n}$ falls into. In Part II, we investigate the same three topics for a uniform random planar graph with constraints on the maximum and minimum degrees.

In this dissertation, we consider a generalization of the historically significant problem posed in 1850 by Reverend Thomas Kirkman which asked whether it was possible for 15 schoolgirls to walk in lines of three to school for seven days so that no two of them appear in the same line on multiple days. This puzzle spawned the study of what we now call resolvable pairwise balanced designs, which balance pair coverage of points within blocks while also demanding that the blocks can be grouped in such a way that each group partitions the point-set. Our generalization aims to relax this condition slightly, so that each group of blocks balances point-wise coverage but each point occurs in each group σ times (instead of just once). We call these objects thickly-resolvable designs. Here we show that the necessary divisibility conditions for the existence of thickly-resolvable designs are also sufficient when the size of the point set is large enough. A few variations of this problem are considered as well. / Graduate

Master of Science / Department of Mathematics / Natasha Rozhkovskaya / “Incomplete open cubes” is one of the major projects of the artist Sol Lewitt. It consists of a collection of frame structures and a presentation of their diagrams. Each structure in the project is a cube with some edges removed so that the structure remains three-dimensional and connected Structures are considered to be identical if one can be transformed into another by a space rotation (but not reflection). The list of incomplete cubes consists of 122 structures. In this project, the concept of incomplete cubes was formulated in the language of graph theory. This allowed us to compare the problem posed by the artist with the similar questions of graph theory considered during the last decades. Classification of Incomplete cubes was then refined using the language of combinatorics. The list produced by the artist was then checked to be complete. And lastly, properties of Incomplete cubes in the list were studied.

This thesis exhibits a range of applications of combinatoric methods to string theory. The concepts and techniques used in the counting of ribbon graphs, the theory of finite groups, and the construction of cell complexes can give powerful methods and interesting insights into the nature of gauge-string duality, the limits of CFT factorisation, and the topology of worldsheet moduli space. The first part presents a candidate space-time theory of the Belyi string with a holographic extension to three-dimensional Euclidean gravity. This is a model of gauge-string duality in which the correlators of the Gaussian Hermitian matrix model are identfied with sums over worldsheet embeddings onto the 2-sphere target space. We show that the matrix model can be reformulated on the sphere by using su(2) representation couplings, and that the analogues of Feynman diagrams in this model can be holographically extended to 3-manifolds within the Ponzano-Regge model. The second part explores the limits of large N factorisation in conformal field theory and the dual interpretation in supergravity. By considering exact finite N correlators of single and multi-trace half-BPS operators in N = 4 super Yang-Mills theory in four dimensions, we can explicitly nd the exact threshold of the operator dimensions at which the correlators fail to factorise. In the dual supergravity, this is the energy regime at which quantum correlations between distinct gravitons become non-vanishing. The third part develops a cell decomposition of the moduli space of punctured Riemann surfaces. The cells are specified by a particular family of ribbon graphs, and we show that these graphs correspond to equivalence classes of permutation tuples arising from branched coverings of the Riemann sphere. This description yields efficient computational approaches for understanding the topology of moduli space.

The Regularity Lemma of Szemeredi is a fundamental tool in extremal graph theory with a wide range of applications in theoretical computer science. Partly as a recognition of his work on the Regularity Lemma, Endre Szemeredi has won the Abel Prize in 2012 for his outstanding achievement. In this thesis we present both practical and theoretical applications of the Regularity Lemma. The practical applications are concerning the important problem of data clustering, the theoretical applications are concerning the monochromatic vertex partition problem. In spite of its numerous applications to establish theoretical results, the Regularity Lemma has a drawback that it requires the graphs under consideration to be astronomically large, thus limiting its practical utility. As stated by Gowers, it has been ``well beyond the realms of any practical applications', the existing applications have been theoretical, mathematical. In the first part of the thesis, we propose to change this and we propose some modifications to the constructive versions of the Regularity Lemma. While this affects the generality of the result, it also makes it more useful for much smaller graphs. We call this result the practical regularity partitioning algorithm and the resulting clustering technique Regularity Clustering. This is the first integrated attempt in order to make the Regularity Lemma applicable in practice. We present results on applying regularity clustering on a number of benchmark data-sets and compare the results with k-means clustering and spectral clustering. Finally we demonstrate its application in Educational Data Mining to improve the student performance prediction. In the second part of the thesis, we study the monochromatic vertex partition problem. To begin we briefly review some related topics and several proof techniques that are central to our results, including the greedy and absorbing procedures. We also review some of the current best results before presenting ours, where the Regularity Lemma has played a critical role. Before concluding we discuss some future research directions that appear particularly promising based on our work.

Let G = (V,A,E) be a mixed graph and co : V → {1, 2,...,λ} a function such that co is a proper colouring of the underlying graph, Und(G), and co(u) ≠ co(y) when co(v) = co(x), for every pair of arcs (u,v) and (x,y). Such a function is called a proper oriented λ − colouring of G. The number of proper oriented λ–colourings of G, denoted fo(G,λ), is a polynomial in λ. We call fo(G,λ) the mixed-chromatic polynomial of G. In this thesis we will first present the basic theory of the mixed-chromatic poly-nomial. This theory will include computational tools and results concerning the coefficients of fo(G,λ). Next, we will consider the question of chromatic uniqueness and invariance of mixed graphs. Lastly, we reformulate a contract-delete recurrence for chromatic polynomials in order to enumerate various colourings, such as k−frugal λ−colourings. / Graduate

The main topic of this thesis is combinatorics on words. The field of combinatorics on words dates back at least to the beginning of the 20th century when Axel Thue constructed an infinite squarefree sequence over a ternary alphabet. From this celebrated result also emerged the subfield of repetition in words which is the main focus of this thesis. One basic tool in the study of repetition in words is the iteration of morphisms. In Chapter 1, we introduce this tool among other basic notions. In Chapter 2, we see applications of iterated morphisms in several examples. The second half of the chapter contains a survey of results concerning Dejean's conjecture. In Chapter 3, we generalize Dejean's conjecture to circular factors. We see several applications of iterated morphism in this chapter. We continue our study of repetition in words in Chapter 4, where we study the length of the shortest repetition-free word in regular languages. Finally, in Chapter 5, we conclude by presenting a number of open problems.

In this thesis we will present two main theorems that can be used to study minor minimal non even cut matroids. Given any signed graph we can associate an even cut matroid. However, given an even cut matroid, there are in general, several signed graphs which represent that matroid. This is in contrast to, for instance graphic (or cographic) matroids, where all graphs corresponding to a particular graphic matroid are essentially equivalent. To tackle the multiple non equivalent representations of even cut matroids we use the concept of Stabilizer first introduced by Wittle. Namely, we show the following: given a "substantial" signed graph, which represents a matroid N that is a minor of a matroid M, then if the signed graph extends to a signed graph which represents M then it does so uniquely. Thus the representations of the small matroid determine the representations of the larger matroid containing it. This allows us to consider each representation of an even cut matroid essentially independently. Consider a small even cut matroid N that is a minor of a matroid M that is not an even cut matroid. We would like to prove that there exists a matroid N' which contains N and is contained in M such that the size of N' is small and such that N' is not an even cut matroid (this would imply in particular that there are only finitely many minimally non even cut matroids containing N). Clearly, none of the representations of N extends to M. We will show that (under certain technical conditions) starting from a fixed representation of N, there exists a matroid N' which contains N and is contained in M such that the size of N' is small and such that the representation of N does not extend to N'.

In this thesis we investigate complete systems of MUBs and SIC-POVMs. These are highly symmetric sets of vectors in Hilbert space, interesting because of their applications in quantum tomography, quantum cryptography and other areas. It is known that these objects form complex projective 2-designs, that is, they satisfy Welch bounds for k = 2 with equality. Using this fact, we derive a necessary and sufficient condition for a set of vectors to be a complete system of MUBs or a SIC-POVM. This condition uses the orthonormality of a specific set of vectors. Then we define homogeneous systems, as a special case of systems of vectors for which the condition takes an especially elegant form. We show how known results and some new results naturally follow from this construction.

Cryptography plays an integral role in secure communication and is usually the strongest link in the chain of security. Yet security problems abound in electronic communication: spyware, phishing, denial of service, and side-channel attacks are still major concerns. The main goal in this thesis is to consider how cryptographic techniques can be extended to offer greater defence against these non-traditional security threats. In the first part of this thesis, we consider problems in classical cryptography. We introduce multi-factor password-authenticated key exchange which allows secure authentication and key agreement based on multiple short secrets, such as a long-term password and a one-time response; it can provide an enhanced level of assurance in higher security scenarios because a multi-factor protocol is designed to remain secure even if all but one of the factors has been compromised due to attacks such as phishing or spyware. Next, we consider the integration of denial of service countermeasures with key exchange protocols: by introducing a formal model for denial of service resilience that complements the extended Canetti-Krawczyk model for secure key agreement, we cover a wide range of existing denial of service attacks and prevent them by carefully using client puzzles. Additionally, we look at how side-channel attacks affect certain types of formulae used in elliptic curve cryptography, and demonstrate that information leaked during field operations such as addition, subtraction, and multiplication can be exploited by an attacker. In the second part of this thesis, we examine cryptography in the quantum setting. We argue that quantum key distribution will have an important role to play in future information security infrastructures and will operate best when integrated with the powerful public key infrastructures that are used today. Finally, we present a new look at quantum money and describe a quantum coin scheme where the coins are not easily counterfeited, are locally verifiable, and can be transferred to another party.