Browsing Combinatorics and Optimization by Title
Now showing items 266-285 of 434
-
On 2-crossing-critical graphs with a V8-minor
(University of Waterloo, 2014-05-22)The crossing number of a graph is the minimum number of pairwise edge crossings in a drawing of a graph. A graph $G$ is $k$-crossing-critical if it has crossing number at least $k$, and any subgraph of $G$ has crossing ... -
On Aharoni’s rainbow generalization of the Caccetta–Häggkvist conjecture
(Elsevier, 2021-05-01)For a digraph G and v is an element of V(G), let delta(+)(v) be the number of out-neighbors of v in G. The Caccetta-Haggkvist conjecture states that for all k >= 1, if G is a digraph with n = |V(G)| such that delta(+)(v) ... -
On Algorithms, Separability and Cellular Automata in Quantum Computing
(University of Waterloo, 2007-09-26)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 ... -
On coloring digraphs with forbidden induced subgraphs
(University of Waterloo, 2023-04-25)This thesis mainly focuses on the structural properties of digraphs with high dichromatic number. The dichromatic number of a digraph $D$, denoted by $\dichi(D)$, is designed to be the directed analog of the chromatic ... -
On Combinatorics, Integrability and Puzzles
(University of Waterloo, 2020-10-23)In the last decade, many old and new results in combinatorics have been shown using the theory of quantum integrable systems from particle physics. The key to solving such problems is the derivation of an underlying ... -
On Efficient Semidefinite Relaxations for Quadratically Constrained Quadratic Programming
(University of Waterloo, 2007-05-18)Two important topics in the study of Quadratically Constrained Quadratic Programming (QCQP) are how to exactly solve a QCQP with few constraints in polynomial time and how to find an inexpensive and strong relaxation bound ... -
On Enumerative Structures in Quantum Field Theory
(University of Waterloo, 2020-07-13)This thesis addresses a number of enumerative problems that arise in the context of quantum field theory and in the process of renormalization. In particular, the enumeration of rooted connected chord diagrams is further ... -
On Eulerian orientations of even-degree hypercubes
(Elsevier, 2018-09-01)It is well known that every Eulerian orientation of an Eulerian 2k-edge connected (undirected) graph is strongly k-edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, ... -
On Excluded Minors for Even Cut Matroids
(University of Waterloo, 2007-01-22)In this thesis we will present two main theorems that can be used to study minor minimal non even cut matroids. Given any signed graph we can associate an even cut matroid. However, given an even cut matroid, there are ... -
On Finding Large Cliques when the Chromatic Number is close to the Maximum Degree
(University of Waterloo, 2021-12-23)We prove that every graph G with chromatic number χ(G) = ∆(G) − 1 and ∆(G) ≥ 66 contains a clique of size ∆(G) − 17. Our proof closely parallels a proof from Cranston and Rabern, who showed that graphs with χ = ∆ and ∆ ≥ ... -
On Geometric Drawings of Graphs
(University of Waterloo, 2018-04-18)This thesis is about geometric drawings of graphs and their topological generalizations. First, we study pseudolinear drawings of graphs in the plane. A pseudolinear drawing is one in which every edge can be extended ... -
On Pairing-Based Signature and Aggregate Signature Schemes
(University of Waterloo, 2009-01-21)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 ... -
On Polynomial-time Path-following Interior-point Methods with Local Superlinear Convergence
(University of Waterloo, 2016-09-30)Interior-point methods provide one of the most popular ways of solving convex optimization problems. Two advantages of modern interior-point methods over other approaches are: (1) robust global convergence, and (2) the ... -
On primal-dual interior-point algorithms for convex optimisation
(2015-09-29)This thesis studies the theory and implementation of interior-point methods for convex optimisation. A number of important problems from mathematics and engineering can be cast naturally as convex optimisation ... -
On primal-dual interior-point algorithms for convex optimisation
(2015-09-25)This thesis studies the theory and implementation of interior-point methods for convex optimisation. A number of important problems from mathematics and engineering can be cast naturally as convex optimisation ... -
On Prime-Order Elliptic Curves with Embedding Degrees 3, 4 and 6
(University of Waterloo, 2007-01-22)Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are ... -
On Schnyder's Theorm
(University of Waterloo, 2010-08-20)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 ... -
On symmetric intersecting families of vectors
(Cambridge University Press, 2021-11)A family of vectors in [k]n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [k]n invariant under a transitive ... -
On The Circuit Diameters of Some Combinatorial Polytopes
(University of Waterloo, 2017-09-20)The combinatorial diameter of a polytope P is the maximum value of a shortest path between two vertices of P, where the path uses the edges of P only. In contrast to the combinatorial diameter, the circuit diameter of P ... -
On the Crossing Numbers of Complete Graphs
(University of Waterloo, 2006)In this thesis we prove two main results. The Triangle Conjecture asserts that the convex hull of any optimal rectilinear drawing of <em>K<sub>n</sub></em> must be a triangle (for <em>n</em> ≥ 3). We prove that, ...