We study several extremal problems in graphs and hypergraphs. The first one is on list-colouring hypergraphs, which is a generalization of the ordinary colouring of hypergraphs. We discuss two methods for determining the list-chromatic number of hypergraphs. One method uses hypergraph polynomials, which invokes Alon's combinatorial nullstellensatz. This method usually requires computer power to complete the calculations needed for even a modest-sized hypergraph. The other method is elementary, and uses the idea of minimum improper colourings. We apply these methods to various classes of hypergraphs, including the projective planes. We focus on solving the list-colouring problem for Steiner triple systems (STS). It is not hard using either method to determine that Steiner triple systems of orders 7, 9 and 13 are 3-list-chromatic. For systems of order 15, we show that they are 4-list-colourable, but they are also ``almost'' 3-list-colourable. For all Steiner triple systems, we prove a couple of simple upper bounds on their list-chromatic numbers. Also, unlike ordinary colouring where a 3-chromatic STS exists for each admissible order, we prove using probabilistic methods that for every $s$, every STS of high enough order is not $s$-list-colourable. The second problem is on embedding nearly-spanning bounded-degree trees in sparse graphs. We determine sufficient conditions based on expansion properties for a sparse graph to embed every nearly-spanning tree of bounded degree. We then apply this to random graphs, addressing a question of Alon, Krivelevich and Sudakov, and determine a probability $p$ where the random graph $G_{n,p}$ asymptotically almost surely contains every tree of bounded degree. This $p$ is nearly optimal in terms of the maximum degree of the trees that we embed. Finally, we solve a problem that arises from quantum computing, which can be formulated as an extremal question about maximizing the size of a type of acyclic directed graph.

In the study of quantum computation, data is represented in terms of linear operators which form a generalized model of probability, and computations are most commonly described as products of unitary transformations, which are the transformations which preserve the quality of the data in a precise sense. This naturally leads to unitary circuit models, which are models of computation in which unitary operators are expressed as a product of "elementary" unitary transformations. However, unitary transformations can also be effected as a composition of operations which are not all unitary themselves: the one-way measurement model is one such model of quantum computation. In this thesis, we examine the relationship between representations of unitary operators and decompositions of those operators in the one-way measurement model. In particular, we consider different circumstances under which a procedure in the one-way measurement model can be described as simulating a unitary circuit, by considering the combinatorial structures which are common to unitary circuits and two simple constructions of one-way based procedures. These structures lead to a characterization of the one-way measurement patterns which arise from these constructions, which can then be related to efficiently testable properties of graphs. We also consider how these characterizations provide automatic techniques for obtaining complete measurement-based decompositions, from unitary transformations which are specified by operator expressions bearing a formal resemblance to path integrals. These techniques are presented as a possible means to devise new algorithms in the one-way measurement model, independently of algorithms in the unitary circuit model.

This thesis investigates HU+00E4ggkvist & Hell graphs. These graphs are an extension of the idea of Kneser graphs, and as such share many attributes with them. A variety of original results on many different properties of these graphs are given. We begin with an examination of the transitivity and structural properties of HU+00E4ggkvist & Hell graphs. Capitalizing on the known results for Kneser graphs, the exact values of girth, odd girth, and diameter are derived. We also discuss subgraphs of HU+00E4ggkvist & Hell graphs that are isomorphic to subgraphs of Kneser graphs. We then give some background on graph homomorphisms before giving some explicit homomorphisms of HU+00E4ggkvist & Hell graphs that motivate many of our results. Using the theory of equitable partitions we compute some eigenvalues of these graphs. Moving on to independent sets we give several bounds including the ratio bound, which is computed using the least eigenvalue. A bound for the chromatic number is given using the homomorphism to the Kneser graphs, as well as a recursive bound. We then introduce the concept of fractional chromatic number and again give several bounds. Also included are tables of the computed values of these parameters for some small cases. We conclude with a discussion of the broader implications of our results, and give some interesting open problems.

In 2001, Boneh, Lynn, and Shacham presented a pairing-based signature scheme known as the BLS signature scheme. In 2003, Boneh, Gentry, Lynn, and Shacham presented the first aggregate signature scheme called the BGLS aggregate signature scheme. The BGLS scheme allows for N users with N signatures to combine their signatures into a single signature. The size of the resulting signature is independent of N. The BGLS signature scheme enjoys roughly the same level of security as the BLS scheme. In 2005, Waters presented a pairing-based signature scheme which does not assume the existence of random oracles. In 2007, Lu, Ostrovsky, Sahai, Shacham, and Waters presented the LOSSW aggregate signature scheme which does not assume the existence of random oracles. The BLS, BGLS, Waters, and LOSSW authors each chose to work with a restricted class of pairings. In each scheme, it is clear that the scheme extend to arbitrary pairings. We present the schemes in their full generality, explore variations of the schemes, and discuss optimizations that can be made when using specific pairings. Each of the schemes we discuss is secure assuming that the computational Diffie-Hellman (CDH) assumption holds. We improve on the security reduction for a variation of the BGLS signature scheme which allows for some restrictions of the BGLS signature scheme can be dropped and provides a stronger guarantee of security. We show that the BGLS scheme can be modified to reduce public-key size in presence of a certifying authority, when a certain type of pairing is used. We show that patient-free bit-compression can be applied to each of the scheme with a few modifications.

We consider a communication method, where the sender encodes n classical bits into 1 qubit and sends it to the receiver who performs a certain measurement depending on which of the initial bits must be recovered. This procedure is called (n,1,p) quantum random access code (QRAC) where p > 1/2 is its success probability. It is known that (2,1,0.85) and (3,1,0.79) QRACs (with no classical counterparts) exist and that (4,1,p) QRAC with p > 1/2 is not possible. We extend this model with shared randomness (SR) that is accessible to both parties. Then (n,1,p) QRAC with SR and p > 1/2 exists for any n > 0. We give an upper bound on its success probability (the known (2,1,0.85) and (3,1,0.79) QRACs match this upper bound). We discuss some particular constructions for several small values of n. We also study the classical counterpart of this model where n bits are encoded into 1 bit instead of 1 qubit and SR is used. We give an optimal construction for such codes and find their success probability exactly---it is less than in the quantum case. Interactive 3D quantum random access codes are available on-line at http://home.lanet.lv/~sd20008/racs

Given positive integers c1,c2,...,ck with gcd(c1,c2,...,ck) = 1, the Frobenius problem (FP) is to compute the largest integer g(c1,c2,...,ck) that cannot be written as a non-negative integer linear combination of c1,c2,...,ck. The Frobenius problem in a free monoid (FPFM) is a non-commutative generalization of the Frobenius problem. Given words x1,x2,...,xk such that there are only finitely many words that cannot be written as concatenations of words in {x1,x2,...,xk}, the FPFM is to find the longest such words. Unlike the FP, where the upper bound g(c1,c2,...,ck)≤max 1≤i≤k ci2 is quadratic, the upper bound on the length of the longest words in the FPFM can be exponential in certain measures and some of the exponential upper bounds are tight. For the 2FPFM, where the given words over Σ are of only two distinct lengths m and n with 1<m<n, the length of the longest omitted words is ≤g(m, m|Σ|n-m + n - m). In Chapter 1, I give the definition of the FP in integers and summarize some of the interesting properties of the FP. In Chapter 2, I give the definition of the FPFM and discuss some general properties of the FPFM. Then I mainly focus on the 2FPFM. I discuss the 2FPFM from different points of view and present two equivalent problems, one of which is about combinatorics on words and the other is about the word graph. In Chapter 3, I discuss some variations on the FPFM and related problems, including input in other forms, bases with constant size, the case of infinite words, the case of concatenation with overlap, and the generalization of the local postage-stamp problem in a free monoid. In Chapter 4, I present the construction of some essential examples to complement the theory of the 2FPFM discussed in Chapter 2. The theory and examples of the 2FPFM are the main contribution of the thesis. In Chapter 5, I discuss the algorithms for and computational complexity of the FPFM and related problems. In the last chapter, I summarize the main results and list some open problems. Part of my work in the thesis has appeared in the papers.

The problem of counting ramified covers of a Riemann surface up to homeomorphism was proposed by Hurwitz in the late 1800's. This problem translates combinatorially into factoring a permutation with a specified cycle type, with certain conditions on the cycle types of the factors, such as minimality and transitivity. Goulden and Jackson have given a proof for the number of minimal, transitive factorizations of a permutation into transpositions. This proof involves a partial differential equation for the generating series, called the Join-Cut equation. Furthermore, this argument is generalized to surfaces of higher genus. Recently, Bousquet-M&eacute;lou and Schaeffer have found the number of minimal, transitive factorizations of a permutation into arbitrary unspecified factors. This was proved by a purely combinatorial argument, based on a direct bijection between factorizations and certain objects called <em>m</em>-Eulerian trees. In this thesis, we will give a new proof of the result by Bousquet-M&eacute;lou and Schaeffer, introducing a simple partial differential equation. We apply algebraic methods based on Lagrange's theorem, and combinatorial methods based on a new use of Bousquet-M&eacute;lou and Schaeffer's <em>m</em>-Eulerian trees. Some partial results are also given for a refinement of this problem, in which the number of cycles in each factor is specified. This involves Lagrange's theorem in many variables.

A theorem due to Scarf in 1967 is examined in detail. Several versions of this theorem exist, some which appear at first unrelated. Two versions can be shown to be equivalent to a result due to Sperner in 1928: for a proper labelling of the vertices in a simplicial subdivision of an n-simplex, there exists at least one elementary simplex which carries all labels {0,1,..., n}. A third version is more akin to Dantzig's simplex method and is also examined. In recent years many new applications in combinatorics have been found, and we present several of them. Two applications are in the area of fair division: cake cutting and rent partitioning. Two others are graph theoretic: showing the existence of a fractional stable matching in a hypergraph and the existence of a fractional kernel in a directed graph. For these last two, we also show the second implies the first.

The Jacobian Conjecture is a long-standing open problem in algebraic geometry. Though the problem is inherently algebraic, it crops up in fields throughout mathematics including perturbation theory, quantum field theory and combinatorics. This thesis is a unified treatment of the combinatorial approaches toward resolving the conjecture, particularly investigating the work done by Wright and Singer. Along with surveying their contributions, we present new proofs of their theorems and motivate their constructions. We also resolve the Symmetric Cubic Linear case, and present new conjectures whose resolution would prove the Jacobian Conjecture to be true.

We study reducibility for nowhere-zero flows. A reducibility proof typically consists of showing that some induced subgraphs cannot appear in a minimum counter-example to some conjecture. We derive algebraic proofs of reducibility. We define variables which in some sense count the number of nowhere-zero flows of certain type in a graph and then deduce equalities and inequalities that must hold for all graphs. We then show how to use these algebraic expressions to prove reducibility. In our case, these inequalities and equalities are linear. We can thus use the well developed theory of linear programming to obtain certificates of these proof. We make publicly available computer programs we wrote to generate the algebraic expressions and obtain the certificates.