Browsing Combinatorics and Optimization by Type "Doctoral Thesis"
Now showing items 41-60 of 122
-
Enumerative perspectives on chord diagrams
(University of Waterloo, 2022-10-07)The topic of this thesis is enumerating certain classes of chord diagrams, perfect matchings of the interval $\{1, 2, \ldots, 2n\}$. We consider hereditary classes of chord diagrams that are restricted to satisfy one of ... -
Equiangular Lines and Antipodal Covers
(University of Waterloo, 2010-09-22)It is not hard to see that the number of equiangular lines in a complex space of dimension $d$ is at most $d^{2}$. A set of $d^{2}$ equiangular lines in a $d$-dimensional complex space is of significant importance in Quantum ... -
Error Bounds and Singularity Degree in Semidefinite Programming
(University of Waterloo, 2020-01-24)An important process in optimization is to determine the quality of a proposed solution. This usually entails calculation of the distance of a proposed solution to the optimal set and is referred to as forward error. ... -
Even Cycle and Even Cut Matroids
(University of Waterloo, 2011-05-20)In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes ... -
Exponentially Dense Matroids
(University of Waterloo, 2011-12-15)This thesis deals with questions relating to the maximum density of rank-n matroids in a minor-closed class. Consider a minor-closed class M of matroids that does not contain a given rank-2 uniform matroid. The growth ... -
FACES OF MATCHING POLYHEDRA
(University of Waterloo, 2016-09-30)Let G = (V, E, ~) be a finite loopless graph, let b=(bi:ieV) be a vector of positive integers. A feasible matching is a vector X = (x.: j e: E) J of nonnegative integers such that for each node i of G, the sum of ... -
Finding Independent Transversals Efficiently
(University of Waterloo, 2019-08-23)Let G be a graph and (V_1,...,V_m) be a vertex partition of G. An independent transversal (IT) of G with respect to (V_1,...,V_m) is an independent set {v_1,...,v_m} in G such that v_i is in V_i for each i in {1,...,m}. There ... -
Fractional refinements of integral theorems
(University of Waterloo, 2021-07-09)The focus of this thesis is to take theorems which deal with ``integral" objects in graph theory and consider fractional refinements of them to gain additional structure. A classic theorem of Hakimi says that for an ... -
A Fundamentally Topological Perspective on Graph Theory
(University of Waterloo, 2005)We adopt a novel topological approach for graphs, in which edges are modelled as points as opposed to arcs. The model of classical <i>topologized graphs</i> translates graph isomorphism into topological homeomorphism, ... -
Generation and properties of random graphs and analysis of randomized algorithms
(University of Waterloo, 2010-01-22)We study a new method of generating random $d$-regular graphs by repeatedly applying an operation called pegging. The pegging algorithm, which applies the pegging operation in each step, is a method of generating large ... -
Geometric Ramifications of the Lovász Theta Function and Their Interplay with Duality
(University of Waterloo, 2013-08-30)The Lovasz theta function and the associated convex sets known as theta bodies are fundamental objects in combinatorial and semidefinite optimization. They are accompanied by a rich duality theory and deep connections ... -
Graph Coverings with Few Eigenvalues or No Short Cycles
(University of Waterloo, 2023-05-18)This thesis addresses the extent of the covering graph construction. How much must a cover X resemble the graph Y that it covers? How much can X deviate from Y? The main statistics of X and Y which we will measure are their ... -
Graph-Theoretic Techniques for Optimizing NISQ Algorithms
(University of Waterloo, 2024-02-15)Entering the NISQ era, the search for useful yet simple quantum algorithms is perhaps of more importance now than it may ever be in the future. In place of quantum walks, the quantum Fourier transform, and asymptotic results ... -
Hardness results and approximation algorithms for some problems on graphs
(University of Waterloo, 2008-12-17)This thesis has two parts. In the first part, we study some graph covering problems with a non-local covering rule that allows a "remote" node to be covered by repeatedly applying the covering rule. In the second part, we ... -
Ideal Clutters
(University of Waterloo, 2018-04-24)Let E be a finite set of elements, and let C be a family of subsets of E called members. We say that C is a clutter over ground set E if no member is contained in another. The clutter C is ideal if every extreme point of ... -
Implicit Loss of Surjectivity and Facial Reduction: Theory and Applications
(University of Waterloo, 2023-03-09)Facial reduction, pioneered by Borwein and Wolkowicz, is a preprocessing method that is commonly used to obtain strict feasibility in the reformulated, reduced constraint system. The importance of strict feasibility is ... -
Improving post-quantum cryptography through cryptanalysis
(University of Waterloo, 2020-07-15)Large quantum computers pose a threat to our public-key cryptographic infrastructure. The possible responses are: Do nothing; accept the fact that quantum computers might be used to break widely deployed protocols. Mitigate ... -
Independent Sets and Eigenspaces
(University of Waterloo, 2004)The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets ... -
Induced Binary Submatroids
(University of Waterloo, 2021-07-21)The notion of induced subgraphs is extensively studied in graph theory. An example is the famous Gy\'{a}rf\'{a}s-Sumner conjecture, which asserts that given a tree $T$ and a clique $K$, there exists a constant $c$ such ... -
Infinite graphs, graph-like spaces and B-matroids
(University of Waterloo, 2011-01-19)The central theme of this thesis is to prove results about infinite mathematical objects by studying the behaviour of their finite substructures. In particular, we study B-matroids, which are an infinite generalization ...