Browsing Combinatorics and Optimization by Title
Now showing items 65-84 of 436
-
Combinatorial Approaches To The Jacobian Conjecture
(University of Waterloo, 2007-08-24)The Jacobian Conjecture is a long-standing open problem in algebraic geometry. Though the problem is inherently algebraic, it crops up in fields throughout mathematics including perturbation theory, quantum field theory ... -
Combinatorial Arithmetic on Elliptic Curves
(University of Waterloo, 2017-09-27)We propose a scalar multiplication technique on an elliptic curve, which operates on triples of collinear points. The computation of this operation requires a new approach to operation chains, with similarities to Montgomery ... -
Combinatorial aspects of braids with applications to cryptography
(University of Waterloo, 2015-08-25)This thesis is a collection of different results on braids, and draws connections between them. We first introduce braids by showcasing a number of equivalent ways of describing what a braid is, and how those representations ... -
Combinatorial Constructions for Transitive Factorizations in the Symmetric Group
(University of Waterloo, 2004)We consider the problem of counting <i>transitive factorizations</i> of permutations; that is, we study tuples (σ<i>r</i>,. . . ,σ1) of permutations on {1,. . . ,<i>n</i>} such that (1) the product ... -
Combinatorial Generalizations of Sieve Methods and Characterizing Hamiltonicity via Induced Subgraphs
(University of Waterloo, 2022-08-17)A sieve method is in effect an application of the inclusion-exclusion counting principle, and the estimation methods to avoid computing the explicit formula. Sieve methods have been used in number theory for over a hundred ... -
A Combinatorial Interpretation of Minimal Transitive Factorizations into Transpositions for Permutations with two Disjoint Cycles
(University of Waterloo, 2008-01-24)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 ... -
Combinatorial Methods for Enumerating Maps in Surfaces of Arbitrary Genus
(University of Waterloo, 2016-06-10)The problem of map enumeration is one that has been studied intensely for the past half century. Early work on this subject included the works of Tutte for various types of rooted planar maps and the works of Brown for ... -
A Combinatorial Tale of Two Scattering Amplitudes: See Two Bijections
(University of Waterloo, 2022-01-07)In this thesis, we take a journey through two different but not dissimilar stories with an underlying theme of combinatorics emerging from scattering amplitudes in quantum field theories. The first part tells the tale ... -
Combinatorially Thin Trees and Spectrally Thin Trees in Structured Graphs
(University of Waterloo, 2023-12-19)Given a graph $G=(V,E)$, finding simpler estimates of $G$ with possibly fewer edges or vertices while capturing some of its specific properties has been used in order to design efficient algorithms. The concept of estimating ... -
Combinatorics and the KP Hierarchy
(University of Waterloo, 2009-10-01)The study of the infinite (countable) family of partial differential equations known as the Kadomtzev - Petviashvili (KP) hierarchy has received much interest in the mathematical and theoretical physics community for ... -
Combinatorics of Grassmannian Decompositions
(University of Waterloo, 2019-08-22)This thesis studies several combinatorially defined families of subsets of the Grassmannian. We introduce and study a family of subsets called “basis shape loci” associated to transversal matroids. Additionally, we study ... -
The combinatorics of the Jack parameter and the genus series for topological maps
(University of Waterloo, 2009-08-19)Informally, a rooted map is a topologically pointed embedding of a graph in a surface. This thesis examines two problems in the enumerative theory of rooted maps. The b-Conjecture, due to Goulden and Jackson, predicts ... -
Communication Complexity of Remote State Preparation
(University of Waterloo, 2014-05-27)Superdense coding and quantum teleportation are two phenomena which were not possible without prior entanglement. In superdense coding, one sends n bits of information using n/2 qubits in the presence of shared entanglement. ... -
Comparing Classical Portfolio Optimization and Robust Portfolio Optimization on Black Swan Events
(University of Waterloo, 2021-01-29)Black swan events, such as natural catastrophes and manmade market crashes, historically have a drastic negative influence on investments; and there is a discrepancy on losses caused by these two types of disasters. In ... -
Comparing Intersection Cut Closures using Simple Families of Lattice-Free Convex Sets
(University of Waterloo, 2022-04-26)Mixed integer programs are a powerful mathematical tool, providing a general model for expressing both theoretically difficult and practically useful problems. One important subroutine of algorithms solving mixed integer ... -
A Complete Multipartite Basis for the Chromatic Symmetric Function
(Society for Industrial and Applied Mathematics, 2021-11-15)In the vector space of symmetric functions, the elements of the basis of elementary symmetric functions are (up to a factor) the chromatic symmetric functions of disjoint unions of cliques. We consider their graph complements, ... -
Complexity Dichotomy for List-5-Coloring with a Forbidden Induced Subgraph
(Society for Industrial and Applied Mathematics, 2022-08-30)For a positive integer r and graphs G and H, we denote by G+H the disjoint union of G and H and by rH the union of r mutually disjoint copies of H. Also, we say G is H-free if H is not isomorphic to an induced subgraph of ... -
Complexity of Ck-Coloring in Hereditary Classes of Graphs
(Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019)For a graph F, a graph G is F-free if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an H-coloring of G is a mapping f : V (G) --> V (H) such that for every edge uv E(G) it holds that ... -
The complexity of some set-partitioning formulations for the vehicle routing problem with stochastic demands
(University of Waterloo, 2020-10-28)The capacitated vehicle routing problem with stochastic demands (CVRPSD) is a variant of the deterministic capacitated vehicle routing problem (CVRP). The CVRP consists of planning routes for vehicles with a given capacity ... -
A Comprehensive Analysis of Lift-and-Project Methods for Combinatorial Optimization
(University of Waterloo, 2014-08-20)In both mathematical research and real-life, we often encounter problems that can be framed as finding the best solution among a collection of discrete choices. Many of these problems, on which an exhaustive search in the ...