In this thesis, we use Mathematical Induction to give a direct proof to show the numbers of binary trees with nodes and nonnegative sequences with terms are the same.

This thesis concerns sufficient conditions for a matroid to admit one of two types of structural characterization: a representation over a finite field or a description as a frame matroid. We call a restriction N of a matroid M modular if, for every flat F of M, r_M(F) + r(N) = r_M(F ∩ E(N)) + r_M(F ∪ E(N)). A consequence of a theorem of Seymour is that any 3-connected matroid with a modular U_{2,3}-restriction is binary. We extend this fact to arbitrary finite fields, showing that if N is a modular rank-3 restriction of a vertically 4-connected matroid M, then any representation of N over a finite field extends to a representation of M. We also look at a more general notion of modularity that applies to minors of a matroid, and use it to present conditions for a matroid with a large projective geometry minor to be representable over a finite field. In particular, we show that a 3-connected, representable matroid with a sufficiently large projective geometry over a finite field GF(q) as a minor is either representable over GF(q) or has a U_{2,q^2+1}-minor. A second result of Seymour is that any vertically 4-connected matroid with a modular M(K_4)-restriction is graphic. Geelen, Gerards, and Whittle partially generalized this from M(K_4) to larger frame matroids, showing that any vertically 5-connected, representable matroid with a rank-4 Dowling geometry as a modular restriction is a frame matroid. As with projective geometries, we prove a version of this result for matroids with large Dowling geometries as minors, providing conditions which imply that they are frame matroids.

We develop algebraic methods to solve join-cut equations, which are partial differential equations that arise in the study of permutation factorizations. Using these techniques, we give a detailed study of the recently introduced monotone Hurwitz numbers, which count factorizations of a given permutation into a fixed number of transpositions, subject to some technical conditions known as transitivity and monotonicity. Part of the interest in monotone Hurwitz numbers comes from the fact that they have been identified as the coefficients in a certain asymptotic expansion related to the Harish-Chandra-Itzykson-Zuber integral, which comes from the theory of random matrices and has applications in mathematical physics. The connection between random matrices and permutation factorizations goes through representation theory, with symmetric functions in the Jucys-Murphy elements playing a key role. As the name implies, monotone Hurwitz numbers are related to the more classical Hurwitz numbers, which count permutation factorizations regardless of monotonicity, and for which there is a significant body of work. Our results for monotone Hurwitz numbers are inspired by similar results for Hurwitz numbers; we obtain a genus expansion for the related generating functions, which yields explicit formulas and a polynomiality result for monotone Hurwitz numbers. A significant difference between the two cases is that our methods are purely algebraic, whereas the theory of Hurwitz numbers relies on some fairly deep results in algebraic geometry. Despite our methods being algebraic, it seems that there should be a connection between monotone Hurwitz numbers and geometry, although this is currently missing. We give some evidence for this connection by identifying some of the coefficients in the monotone Hurwitz genus expansion with coefficients in the classical Hurwitz genus expansion known to be Hodge integrals over the moduli space of curves.

We develop algebraic methods to solve join-cut equations, which are partial differential equations that arise in the study of permutation factorizations. Using these techniques, we give a detailed study of the recently introduced monotone Hurwitz numbers, which count factorizations of a given permutation into a fixed number of transpositions, subject to some technical conditions known as transitivity and monotonicity. Part of the interest in monotone Hurwitz numbers comes from the fact that they have been identified as the coefficients in a certain asymptotic expansion related to the Harish-Chandra-Itzykson-Zuber integral, which comes from the theory of random matrices and has applications in mathematical physics. The connection between random matrices and permutation factorizations goes through representation theory, with symmetric functions in the Jucys-Murphy elements playing a key role. As the name implies, monotone Hurwitz numbers are related to the more classical Hurwitz numbers, which count permutation factorizations regardless of monotonicity, and for which there is a significant body of work. Our results for monotone Hurwitz numbers are inspired by similar results for Hurwitz numbers; we obtain a genus expansion for the related generating functions, which yields explicit formulas and a polynomiality result for monotone Hurwitz numbers. A significant difference between the two cases is that our methods are purely algebraic, whereas the theory of Hurwitz numbers relies on some fairly deep results in algebraic geometry. Despite our methods being algebraic, it seems that there should be a connection between monotone Hurwitz numbers and geometry, although this is currently missing. We give some evidence for this connection by identifying some of the coefficients in the monotone Hurwitz genus expansion with coefficients in the classical Hurwitz genus expansion known to be Hodge integrals over the moduli space of curves.

This thesis concerns sufficient conditions for a matroid to admit one of two types of structural characterization: a representation over a finite field or a description as a frame matroid. We call a restriction N of a matroid M modular if, for every flat F of M, r_M(F) + r(N) = r_M(F ∩ E(N)) + r_M(F ∪ E(N)). A consequence of a theorem of Seymour is that any 3-connected matroid with a modular U_{2,3}-restriction is binary. We extend this fact to arbitrary finite fields, showing that if N is a modular rank-3 restriction of a vertically 4-connected matroid M, then any representation of N over a finite field extends to a representation of M. We also look at a more general notion of modularity that applies to minors of a matroid, and use it to present conditions for a matroid with a large projective geometry minor to be representable over a finite field. In particular, we show that a 3-connected, representable matroid with a sufficiently large projective geometry over a finite field GF(q) as a minor is either representable over GF(q) or has a U_{2,q^2+1}-minor. A second result of Seymour is that any vertically 4-connected matroid with a modular M(K_4)-restriction is graphic. Geelen, Gerards, and Whittle partially generalized this from M(K_4) to larger frame matroids, showing that any vertically 5-connected, representable matroid with a rank-4 Dowling geometry as a modular restriction is a frame matroid. As with projective geometries, we prove a version of this result for matroids with large Dowling geometries as minors, providing conditions which imply that they are frame matroids.

No description available.

No description available.

We prove various results in additive combinatorics for subsets of random sets. In particular we extend Sarkozy's theorem and a theorem of Green on long arithmetic progressions in sumsets to dense subsets of random sets with asymptotic density 0. Our proofs require a transference argument due to Green and Green-Tao which enables us to apply known results for sets of positive upper density to subsets of random sets which have positive relative density. We also prove a density result which states that if a subset of a random set has positive relative density, then the sumset of the subset must have positive upper density in the integers.

In Part I of this thesis, we present a new model of quantum cellular automata (QCA) based on local unitary operations. We will describe a set of desirable properties for any QCA model, and show that all of these properties are satisfied by the new model, while previous models of QCA do not. We will also show that the computation model based on Local Unitary QCA is equivalent to the Quantum Circuit model of computation, and give a number of applications of this new model of QCA. We also present a physical model of classical CA, on which the Local Unitary QCA model is based, and Coloured QCA, which is an alternative to the Local Unitary QCA model that can be used as the basis for implementing QCA in actual physical systems. In Part II, we explore the quantum separability problem, where we are given a density matrix for a state over two quantum systems, and we are to determine whether the state is separable with respect to these systems. We also look at the converse problem of finding an entanglement witness, which is an observable operator which can give a verification that a particular quantum state is indeed entangled. Although the combined problem is known to be NP-hard in general, it reduces to a convex optimization problem, and by exploiting specific properties of the set of separable states, we introduce a classical algorithm for solving this problem based on an Interior Point Algorithm introduced by Atkinson and Vaidya in 1995. In Part III, we explore the use of a low-depth AQFT (approximate quantum Fourier transform) in quantum phase estimation. It has been shown previously that the logarithmic-depth AQFT is as effective as the full QFT for the purposes of phase estimation. However, with sub-logarithmic depth, the phase estimation algorithm no longer works directly. In this case, results of the phase estimation algorithm need classical post-processing in order to retrieve the desired phase information. A generic technique such as the method of maximum likelihood can be used in order to recover the original phase. Unfortunately, working with the likelihood function analytically is intractable for the phase estimation algorithm. We develop some computational techniques to handle likelihood functions that occur in phase estimation algorithms. These computational techniques may potentially aid in the analysis of certain likelihood functions.

This thesis is about minimal transitive factorizations of permutations into transpositions. We focus on finding direct combinatorial proofs for the cases where no such direct combinatorial proofs were known. We give a description of what has been done previously in the subject at the direct combinatorial level and in general. We give some new proofs for the known cases. We then present an algorithm that is a bijection between the set of elements in {1, ..., k} dropped into n cyclically ordered boxes and some combinatorial structures involving trees attached to boxes, where these structures depend on whether k > n, k = n or k < n. The inverse of this bijection consists of removing vertices from trees and placing them in boxes in a simple way. In particular this gives a bijection between parking functions of length n and rooted forests on n elements. Also, it turns out that this bijection allows us to give a direct combinatorial derivation of the number of minimal transitive factorizations into transpositions of the permutations that are the product of two disjoint cycles.