In pursuit of negatively associated measures, this thesis focuses on certain negative correlation properties in matroids. In particular, the results presented contribute to the search for matroids which satisfy $$P(\{X:e,f\in X\}) \leq P(\{X:e\in X\})P(\{X:f\in X\})$$ for certain measures, $P$, on the ground set. Let $\mathcal M$ be a matroid. Let $(y_g:g\in E)$ be a weighting of the ground set and let $${Z = \sum_{X}\left( \prod_{x\in X} y_x\right) }$$ be the polynomial which generates Z-sets, were Z $\in \{$ B,I,S $\}$. For each of these, the sum is over bases, independent sets and spanning sets, respectively. Let $e$ and $f$ be distinct elements of $E$ and let $Z_e$ indicate partial derivative. Then $\mathcal M$ is Z-Rayleigh if $Z_eZ_f-ZZ_{ef}\geq 0$ for every positive evaluation of the $y_g$s. The known elementary results for the B, I and S-Rayleigh properties and two special cases called negative correlation and balance are proved. Furthermore, several new results are discussed. In particular, if a matroid is binary on at most nine elements or paving or rank three, then it is I-Rayleigh if it is B-Rayleigh. Sparse paving matroids are B-Rayleigh. The I-Rayleigh difference for graphs on at most seven vertices is a sum of monomials times squares of polynomials and this same special form holds for all series parallel graphs.

This thesis explores two infinite families of self-complementary arc-transitive graphs: the familiar Paley graphs and the newly discovered Peisert graphs. After studying both families, we examine a result of Peisert which proves the Paley and Peisert graphs are the only self-complementary arc transitive graphs other than one exceptional graph. Then we consider other families of graphs which share many properties with the Paley and Peisert graphs. In particular, we construct an infinite family of self-complementary strongly regular graphs from affine planes. We also investigate the pseudo-Paley graphs of Weng, Qiu, Wang, and Xiang. Finally, we prove a lower bound on the number of maximal cliques of certain pseudo-Paley graphs, thereby distinguishing them from Paley graphs of the same order.

In this thesis we take a specialized approach to edge-colouring by focusing exclusively on multigraphs with high chromatic index. The bulk of our results can be classified into three categories. First, we prove results which aim to characterize those multigraphs achieving known upper bounds. For example, Goldberg's Theorem says that χ'≤ Δ+1+(Δ-2}/(g₀+1) (where χ' denotes chromatic index, Δ denotes maximum degree, and g₀ denotes odd girth). We characterize this bound by proving that for a connected multigraph G, χ'= Δ+1+(Δ-2}/(g₀+1) if and only if G=μC_g₀ and (g₀+1)|2(μ-1) (where μ denotes maximum edge-multiplicity). Our second category of results are new upper bounds for chromatic index in multigraphs, and accompanying polynomial-time edge-colouring algorithms. Our bounds are all approximations to the famous Seymour-Goldberg Conjecture, which asserts that χ'≤ max{⌈ρ⌉, Δ+1} (where ρ=max{(2|E[S]|)/(|S|-1): S⊆V, |S|≥3 and odd}). For example, we refine Goldberg's classical Theorem by proving that χ'≤ max{⌈ρ⌉, Δ+1+(Δ-3)/(g₀+3)}. Our third category of results are characterizations of high chromatic index in general, with particular focus on our approximation results. For example, we completely characterize those multigraphs with χ'> Δ+1+(Δ-3)/(g₀+3). The primary method we use to prove results in this thesis is the method of Tashkinov trees. We first solidify the theory behind this method, and then provide general edge-colouring results depending on Tashkinov trees. We also explore the limits of this method, including the possibility of vertex-colouring graphs which are not line graphs of multigraphs, and the importance of Tashkinov trees with regard to the Seymour-Goldberg Conjecture.

We study techniques, approximation algorithms, structural properties and lower bounds related to applications of linear programs in combinatorial optimization. The following "Steiner tree problem" is central: given a graph with a distinguished subset of required vertices, and costs for each edge, find a minimum-cost subgraph that connects the required vertices. We also investigate the areas of network design, multicommodity flows, and packing/covering integer programs. All of these problems are NP-complete so it is natural to seek approximation algorithms with the best provable approximation ratio. Overall, we show some new techniques that enhance the already-substantial corpus of LP-based approximation methods, and we also look for limitations of these techniques. The first half of the thesis deals with linear programming relaxations for the Steiner tree problem. The crux of our work deals with hypergraphic relaxations obtained via the well-known full component decomposition of Steiner trees; explicitly, in this view the fundamental building blocks are not edges, but hyperedges containing two or more required vertices. We introduce a new hypergraphic LP based on partitions. We show the new LP has the same value as several previously-studied hypergraphic ones; when no Steiner nodes are adjacent, we show that the value of the well-known bidirected cut relaxation is also the same. A new partition uncrossing technique is used to demonstrate these equivalences, and to show that extreme points of the new LP are well-structured. We improve the best known integrality gap on these LPs in some special cases. We show that several approximation algorithms from the literature on Steiner trees can be re-interpreted through linear programs, in particular our hypergraphic relaxation yields a new view of the Robins-Zelikovsky 1.55-approximation algorithm for the Steiner tree problem. The second half of the thesis deals with a variety of fundamental problems in combinatorial optimization. We show how to apply the iterated LP relaxation framework to the problem of multicommodity integral flow in a tree, to get an approximation ratio that is asymptotically optimal in terms of the minimum capacity. Iterated relaxation gives an infeasible solution, so we need to finesse it back to feasibility without losing too much value. Iterated LP relaxation similarly gives an O(k^2)-approximation algorithm for packing integer programs with at most k occurrences of each variable; new LP rounding techniques give a k-approximation algorithm for covering integer programs with at most k variable per constraint. We study extreme points of the standard LP relaxation for the traveling salesperson problem and show that they can be much more complex than was previously known. The k-edge-connected spanning multi-subgraph problem has the same LP and we prove a lower bound and conjecture an upper bound on the approximability of variants of this problem. Finally, we show that for packing/covering integer programs with a bounded number of constraints, for any epsilon > 0, there is an LP with integrality gap at most 1 + epsilon.

The LYM property of a finite standard graded poset is one of the central notions in Sperner theory. It is known that the product of two finite standard graded posets satisfying the LYM properties may not have the LYM property again. In 1974, Harper proved that if two finite standard graded posets satisfying the LYM properties also satisfy rank logarithmic concavities, then their product also satisfies these two properties. However, Harper's proof is rather non-intuitive. Giving a natural proof of Harper's theorem is one of the goals of this thesis. The main new result of this thesis is a characterization of rank-finite standard graded LYM posets that satisfy rank logarithmic concavities. With this characterization theorem, we are able to give a new, natural proof of Harper's theorem. In fact, we prove a strengthened version of Harper's theorem by weakening the finiteness condition to the rank-finiteness condition. We present some interesting applications of the main characterization theorem. We also give a brief history of Sperner theory, and summarize all the ingredients we need for the main theorem and its applications, including a new equivalent condition for the LYM property that is a key for proving our main theorem.

This thesis develops an algorithm for the Schubert calculus of the Grassmanian. Specifically, we state a puzzle-based, synthesis algorithm for a triple intersection of Schubert varieties. Our algorithm is a reformulation of the synthesis algorithm by Bercovici, Collins, Dykema, Li, and Timotin. We replace their combinatorial approach, based on specialized Lebesgue measures, with an approach based on the puzzles of Knutson, Tao and Woodward. The use of puzzles in our algorithm is beneficial for several reasons, foremost among them being the larger body of work exploiting puzzles. To understand the algorithm, we study the necessary Schubert calculus of the Grassmanian to define synthesis. We also discuss the puzzle-based Littlewood-Richardson rule, which connects puzzles to triple intersections of Schubert varieties. We also survey three combinatorial objects related to puzzles in which we include a puzzle-based construction, by King, Tollu, and Toumazet, of the well known Horn inequalities.

We study a directed network design problem called the $k$-$(S,T)$-connectivity problem; we design and analyze approximation algorithms and give hardness results. For each positive integer $k$, the minimum cost $k$-vertex connected spanning subgraph problem is a special case of the $k$-$(S,T)$-connectivity problem. We defer precise statements of the problem and of our results to the introduction. For $k=1$, we call the problem the $(S,T)$-connectivity problem. We study three variants of the problem: the standard $(S,T)$-connectivity problem, the relaxed $(S,T)$-connectivity problem, and the unrestricted $(S,T)$-connectivity problem. We give hardness results for these three variants. We design a $2$-approximation algorithm for the standard $(S,T)$-connectivity problem. We design tight approximation algorithms for the relaxed $(S,T)$-connectivity problem and one of its special cases. For any $k$, we give an $O(\log k\log n)$-approximation algorithm, where $n$ denotes the number of vertices. The approximation guarantee almost matches the best approximation guarantee known for the minimum cost $k$-vertex connected spanning subgraph problem which is $O(\log k\log\frac{n}{n-k})$ due to Nutov in 2009.

The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

Graph searching problems are described as games played on graphs, between a set of searchers and a fugitive. Variants of the game restrict the abilities of the searchers and the fugitive and the corresponding search number (the least number of searchers that have a winning strategy) is related to several well-known parameters in graph theory. One popular variant is called the Cops and Robber game, where the searchers (cops) and the fugitive (robber) move in rounds, and in each round they move to an adjacent vertex. This game, defined in late 1970's, has been studied intensively. The most famous open problem is Meyniel's conjecture, which states that the cop number (the minimum number of cops that can always capture the robber) of a connected graph on n vertices is O(sqrt n). We consider a version of the Cops and Robber game, where the robber is faster than the cops, but is not allowed to jump over the cops. This version was first studied in 2008. We show that when the robber has speed s, the cop number of a connected n-vertex graph can be as large as Omega(n^(s/s+1)). This improves the Omega(n^(s-3/s-2)) lower bound of Frieze, Krivelevich, and Loh (Variations on Cops and Robbers, J. Graph Theory, to appear). We also conjecture a general upper bound O(n^(s/s+1)) for the cop number, generalizing Meyniel's conjecture. Then we focus on the version where the robber is infinitely fast, but is again not allowed to jump over the cops. We give a mathematical characterization for graphs with cop number one. For a graph with treewidth tw and maximum degree Delta, we prove the cop number is between (tw+1)/(Delta+1) and tw+1. Using this we show that the cop number of the m-dimensional hypercube is between c1 n / m sqrt(m) and c2 n / m for some constants c1 and c2. If G is a connected interval graph on n vertices, then we give a polynomial time 3-approximation algorithm for finding the cop number of G, and prove that the cop number is O(sqrt(n)). We prove that given n, there exists a connected chordal graph on n vertices with cop number Omega(n/log n). We show a lower bound for the cop numbers of expander graphs, and use this to prove that the random G(n,p) that is not very sparse, asymptotically almost surely has cop number between d1 / p and d2 log (np) / p for suitable constants d1 and d2. Moreover, we prove that a fixed-degree regular random graph with n vertices asymptotically almost surely has cop number Theta(n).

A clique of a graph G is a set of pairwise adjacent nodes of G. Similarly, a biclique (U, V ) of a bipartite graph G is a pair of disjoint, independent vertex sets such that each node in U is adjacent to every node in V in G. We consider the problems of identifying the maximum clique of a graph, known as the maximum clique problem, and identifying the biclique (U, V ) of a bipartite graph that maximizes the product |U | · |V |, known as the maximum edge biclique problem. We show that finding a clique or biclique of a given size in a graph is equivalent to finding a rank one matrix satisfying a particular set of linear constraints. These problems can be formulated as rank minimization problems and relaxed to convex programming by replacing rank with its convex envelope, the nuclear norm. Both problems are NP-hard yet we show that our relaxation is exact in the case that the input graph contains a large clique or biclique plus additional nodes and edges. For each problem, we provide two analyses of when our relaxation is exact. In the first, the diversionary edges are added deterministically by an adversary. In the second, each potential edge is added to the graph independently at random with fixed probability p. In the random case, our bounds match the earlier bounds of Alon, Krivelevich, and Sudakov, as well as Feige and Krauthgamer for the maximum clique problem. We extend these results and techniques to the k-disjoint-clique problem. The maximum node k-disjoint-clique problem is to find a set of k disjoint cliques of a given input graph containing the maximum number of nodes. Given input graph G and nonnegative edge weights w, the maximum mean weight k-disjoint-clique problem seeks to identify the set of k disjoint cliques of G that maximizes the sum of the average weights of the edges, with respect to w, of the complete subgraphs of G induced by the cliques. These problems may be considered as a way to pose the clustering problem. In clustering, one wants to partition a given data set so that the data items in each partition or cluster are similar and the items in different clusters are dissimilar. For the graph G such that the set of nodes represents a given data set and any two nodes are adjacent if and only if the corresponding items are similar, clustering the data into k disjoint clusters is equivalent to partitioning G into k-disjoint cliques. Similarly, given a complete graph with nodes corresponding to a given data set and edge weights indicating similarity between each pair of items, the data may be clustered by solving the maximum mean weight k-disjoint-clique problem. We show that both instances of the k-disjoint-clique problem can be formulated as rank constrained optimization problems and relaxed to semidefinite programs using the nuclear norm relaxation of rank. We also show that when the input instance corresponds to a collection of k disjoint planted cliques plus additional edges and nodes, this semidefinite relaxation is exact for both problems. We provide theoretical bounds that guarantee exactness of our relaxation and provide empirical examples of successful applications of our algorithm to synthetic data sets, as well as data sets from clustering applications.