Stable matchings were introduced in 1962 by David Gale and Lloyd Shapley to study the college admissions problem. The seminal work of Gale and Shapley has motivated hundreds of research papers and found applications in many areas of mathematics, computer science, economics, and even medicine. This thesis studies stable matchings in graphs and hypergraphs. We begin by introducing the work of Gale and Shapley. Their main contribution was the proof that every bipartite graph has a stable matching. Our discussion revolves around the Gale-Shapley algorithm and highlights some of the interesting properties of stable matchings in bipartite graphs. We then progress to non-bipartite graphs. Contrary to bipartite graphs, we may not be able to find a stable matching in a non-bipartite graph. Some of the work of Irving will be surveyed, including his extension of the Gale-Shapley algorithm. Irving's algorithm shows that many of the properties of bipartite stable matchings remain when the general case is examined. In 1991, Tan showed how to extend the fundamental theorem of Gale and Shapley to non-bipartite graphs. He proved that every graph contains a set of edges that is very similar to a stable matching. In the process, he found a characterization of graphs with stable matchings based on a modification of Irving's algorithm. Aharoni and Fleiner gave a non-constructive proof of Tan's Theorem in 2003. Their proof relies on a powerful topological result, due to Scarf in 1965. In fact, their result extends beyond graphs and shows that every hypergraph has a fractional stable matching. We show how their work provides new and simpler proofs to several of Tan's results. We then consider fractional stable matchings from a linear programming perspective. Vande Vate obtained the first formulation for complete bipartite graphs in 1989. Further, he showed that the extreme points of the solution set exactly correspond to stable matchings. Roth, Rothblum, and Vande Vate extended Vande Vate's work to arbitrary bipartite graphs. Abeledo and Rothblum further noticed that this new formulation can model fractional stable matchings in non-bipartite graphs in 1994. Remarkably, these formulations yield analogous results to those obtained from Gale-Shapley's and Irving's algorithms. Without the presence of an algorithm, the properties are obtained through clever applications of duality and complementary slackness. We will also discuss stable matchings in hypergraphs. However, the desirable properties that are present in graphs no longer hold. To rectify this problem, we introduce a new ``majority" stable matchings for 3-uniform hypergraphs and show that, under this stronger definition, many properties extend beyond graphs. Once again, the linear programming tools of duality and complementary slackness are invaluable to our analysis. We will conclude with a discussion of two open problems relating to stable matchings in 3-uniform hypergraphs.

In this thesis we study the subset of quantum operations that can be implemented using only local quantum operations and classical communication (LOCC). This restricted paradigm serves as a tool to study not only quantum correlations and other nonlocal quantum effects, but also resource transformations such as channel capacities. The mathematical structure of LOCC is complex and difficult to characterize. In the first part of this thesis we provide a precise description of LOCC and related operational classes in terms of quantum instruments. Our formalism captures both finite round protocols as well as those that utilize an unbounded number of communication rounds. This perspective allows us to measure the distance between two LOCC instruments and hence discuss the closure of LOCC in a rigorous way. While the set of LOCC is not topologically closed, we show that the operations that can be implemented using some fixed number rounds of communication constitute a compact subset of all quantum operations. We also exhibit a subset of LOCC measurements that is closed. Additionally we establish the existence of an open ball around the completely depolarizing map consisting entirely of LOCC implementable maps. In the second part of this thesis we focus on the task of discriminating states from some known set S by LOCC. Building on the work in the paper "Quantum nonlocality without entanglement", we provide a framework for lower bounding the error probability of any LOCC protocol aiming at discriminating the states from S. We apply our framework to an orthonormal product basis known as the domino states. This gives an alternative and simplified bound quantifying how well these states can be discriminated using LOCC. We generalize this result for similar bases in larger dimensions, as well as the "rotated" domino states, resolving a long-standing open question. These results give new examples of quantitative gaps between the classes of separable and LOCC operations. In the last part of this thesis, we ask what differentiates separable from LOCC operations. Both of these classes play a key role in the study of entanglement. Separable operations are known to be strictly more powerful than LOCC ones, but no simple explanation of this phenomenon is known. We show that, in the case of bipartite von Neumann measurements, the ability to interpolate is an operational principle that separates LOCC and separable operations.

Placement games are a subclass of combinatorial games which are played on graphs. In this thesis, we demonstrate that placement games could be considered as games played on simplicial complexes. These complexes are constructed using square-free monomials. We define new classes of placement games and the notion of Doppelgänger. To aid in exploring the simplicial complex of a game, we introduce the bipartite flip and develop tools to compare known bounds on simplicial complexes (such as the Kruskal-Katona bounds) with bounds on game complexes.

In this dissertation we study the excedance permutation statistic. We start by extending the classical excedance statistic of the symmetric group to the affine symmetric group eSn and determine the generating function of its distribution. The proof involves enumerating lattice points in a skew version of the root polytope of type A. Next we study the excedance set statistic on the symmetric group by defining a related algebra which we call the excedance algebra. A combinatorial interpretation of expansions from this algebra is provided. The second half of this dissertation deals with the topology of the Frobenius complex, that is the order complex of a poset whose definition was motivated by the classical Frobenius problem. We determine the homotopy type of the Frobenius complex in certain cases using discrete Morse theory. We end with an enumeration of Q-factorial posets. Open questions and directions for future research are located at the end of each chapter.

Boij-Söderberg theory shows that the Betti table of a graded module can be written as a linear combination of pure diagrams with integer coefficients. In chapter 2 using Ferrers hypergraphs and simplicial polytopes, we provide interpretations of these coefficients for ideals with a d-linear resolution, their quotient rings, and for Gorenstein rings whose resolution has essentially at most two linear strands. We also establish a structural result on the decomposition in the case of quasi-Gorenstein modules. These results are published in the Journal of Algebra, see [25]. In chapter 3 we provide some further results about Boij-Söderberg decompositions. We show how truncation of a pure diagram impacts the decomposition. We also prove constructively that every integer multiple of a pure diagram of codimension 2 can be realized as the Betti table of a module. In chapter 4 we introduce the idea of a c-polar self-dual polytope. We prove that in dimension 2 only the odd n-gons have an embedding which is polar self-dual. We also define the family of Ferrers polytopes. We prove that the Ferrers polytope in dimension d is d-polar self-dual hence establishing a nontrivial example of a polar self-dual polytope in all dimension. Finally we prove that the Ferrers polytope in dimension d supports a cellular resolution of the Stanley-Reisner ring of the (d+3)-gon.

The super Catalan numbers T(m,n) = (2m)!(2n)!=2m!n!(m+n)! are integers which generalize the Catalan numbers. Since 1874, when Eugene Catalan discovered these numbers, many mathematicians have tried to find their combinatorial interpretation. This dissertation is dedicated to this open problem. In Chapter 1 we review known results on T (m,n) and their q-analog polynomials. In Chapter 2 we give a weighted interpretation for T(m,n) in terms of 2-Motzkin paths of length m+n2 and a reformulation of this interpretation in terms of Dyck paths. We then convert our weighted interpretation into a conventional combinatorial interpretation for m = 1,2. At the beginning of Chapter 2, we prove our weighted interpretation for T(m,n) by induction. In the final section of Chapter 2 we present a constructive combinatorial proof of this result based on rooted plane trees. In Chapter 3 we introduce two q-analog super Catalan numbers. We also define the q-Ballot number and provide its combinatorial interpretation. Using our q-Ballot number, we give an identity for one of the q-analog super Catalan numbers and use it to interpret a q-analog super Catalan number in the case m= 2. In Chapter 4 we review problems left open and discuss their difficulties. This includes the unimodality of some of the q-analog polynomials and the conventional combinatorial interpretation of the super Catalan numbers and their q-analogs for higher values of m.

This thesis concerns the use of labelled infinite trees to solve families of nested recursions of the form $R(n)=\sum_{i=1}^kR(n-a_i-\sum_{j=1}^{p_i}R(n-b_{ij}))+w$, where $a_i$ is a nonnegative integer, $w$ is any integer, and $b_{ij},k,$ and $p_i$ are natural numbers. We show that the solutions to many families of such nested recursions have an intriguing combinatorial interpretation, namely, they count nodes on the bottom level of labelled infinite trees that correspond to the recursion. Furthermore, we show how the parameters defining these recursion families relate in a natural way to specific structural properties of the corresponding tree families. We introduce a general tree ``pruning" methodology that we use to establish all the required tree-sequence correspondences.

This thesis concerns the use of labelled infinite trees to solve families of nested recursions of the form $R(n)=\sum_{i=1}^kR(n-a_i-\sum_{j=1}^{p_i}R(n-b_{ij}))+w$, where $a_i$ is a nonnegative integer, $w$ is any integer, and $b_{ij},k,$ and $p_i$ are natural numbers. We show that the solutions to many families of such nested recursions have an intriguing combinatorial interpretation, namely, they count nodes on the bottom level of labelled infinite trees that correspond to the recursion. Furthermore, we show how the parameters defining these recursion families relate in a natural way to specific structural properties of the corresponding tree families. We introduce a general tree ``pruning" methodology that we use to establish all the required tree-sequence correspondences.

If R is a list of positive integers with greatest common denominator equal to 1, calculating the Frobenius number of R is in general NP-hard. Dino Lorenzini defines the arithmetical graph, which naturally arises in arithmetic geometry, and a notion of genus, the g-number, that in specific cases coincides with the Frobenius number of R. A result of Dino Lorenzini's gives a method for quickly calculating upper bounds for the g-number of arithmetical graphs. We discuss the arithmetic geometry related to arithmetical graphs and present an example of an arithmetical graph that arises in this context. We also discuss the construction for Lorenzini's Riemann-Roch structure and how it relates to the Riemann-Roch theorem for finite graphs shown by Matthew Baker and Serguei Norine. We then focus on the connection between the Frobenius number and arithmetical graphs. Using the Laplacian of an arithmetical graph and a formulation of chip-firing on the vertices of an arithmetical graph, we show results that can be used to find arithmetical graphs whose g-numbers correspond to the Frobenius number of R. We describe how this can be used to quickly calculate upper bounds for the Frobenius number of R.

Bilinear pairings are being used in ingenious ways to solve various protocol problems. Much research has been done on improving the efficiency of pairing computations. This thesis gives an introduction to the Tate pairing and some variants including the ate pairing, Vercauteren's pairing, and the R-ate pairing. We describe the Barreto-Naehrig (BN) family of pairing-friendly curves, and analyze three different coordinates systems (affine, projective, and jacobian) for implementing the R-ate pairing. Finally, we examine some recent work for speeding the pairing computation and provide improved estimates of the pairing costs on a particular BN curve.