Now showing items 21-40 of 434

    • Near-optimal quantum strategies for nonlocal games, approximate representations, and BCS algebras 

      Paul-Paddock, Connor (University of Waterloo, 2023-05-04)
      Quantum correlations can be viewed as particular abstract states on the tensor product of operator systems which model quantum measurement scenarios. In the paradigm of nonlocal games, this perspective illustrates a ...
    • Non-Adaptive Matroid Prophet Inequalities 

      Sayutina, Alice (University of Waterloo, 2023-05-04)
      We consider the problem of matroid prophet inequalities. This problem has been ex- tensively studied in case of adaptive prices, with [KW12] obtaining a tight 2-competitive mechanism for all the matroids. However, the ...
    • Semidefinite Programming Relaxations of the Simplified Wasserstein Barycenter Problem: An ADMM Approach 

      Cheng, Jiahui (University of Waterloo, 2023-05-04)
      The Simplified Wasserstein Barycenter problem, the problem of picking k points each chosen from a distinct set of n points as to minimize the sum of distances to their barycenter, finds applications in various areas of ...
    • Dynamic Pricing Schemes in Combinatorial Markets 

      Kalichman, David (University of Waterloo, 2023-05-01)
      In combinatorial markets where buyers are self-interested, the buyers may make purchases that lead to suboptimal item allocations. As a central coordinator, our goal is to impose prices on the items of the market so that ...
    • Algorithms for Analytic Combinatorics in Several Variables 

      Smolcic, Josip (University of Waterloo, 2023-04-25)
      Given a multivariate rational generating function we are interested in computing asymptotic formulas for the sequences encoded by the coefficients. In this thesis we apply the theory of analytic combinatorics in several ...
    • On coloring digraphs with forbidden induced subgraphs 

      Carbonero, Alvaro (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 ...
    • Analyzing Tree Attachments in 2-Crossing-Critical Graphs with a V8 Minor 

      Bedsole, Carter (University of Waterloo, 2023-04-25)
      The crossing number of a graph is the minimum number of pairwise edge crossings in a drawing of the graph in the plane. A graph G is k-crossing-critical if its crossing number is at least k and if every proper subgraph H ...
    • Post-Quantum Account Recovery for Passwordless Authentication 

      Wilson, Spencer MacLaren (University of Waterloo, 2023-04-24)
      WebAuthn is a passwordless authentication protocol which allows users to authenticate to online services using public-key cryptography. Users prove their identity based on possession of a private key, which is stored on a ...
    • Implicit Loss of Surjectivity and Facial Reduction: Theory and Applications 

      Im, Haesol (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 ...
    • The Edmonds-Giles Conjecture and its Relaxations 

      Hwang, Steven (University of Waterloo, 2022-12-23)
      Given a directed graph, a directed cut is a cut with all arcs oriented in the same direction, and a directed join is a set of arcs which intersects every directed cut at least once. Edmonds and Giles conjectured for all ...
    • k-Connectedness and k-Factors in the Semi-Random Graph Process 

      Koerts, Hidde (University of Waterloo, 2022-12-20)
      The semi-random graph process is a single-player graph game where the player is initially presented an edgeless graph with n vertices. In each round, the player is offered a vertex u uniformly at random and subsequently ...
    • Mixed Integer Programming Approaches for Group Decision Making 

      Iam, Hoi Cheong (University of Waterloo, 2022-10-26)
      Group decision making problems are everywhere in our day-to-day lives and have great influence on the daily operation of companies and institutions. With the recent advances in computational technology, it's not surprising ...
    • Aspects of Quantum Field Theory in Enumerative Graph Theory 

      Yusim, Samuel (University of Waterloo, 2022-10-24)
      While a quantum field theorist has many uses for mathematics of all kinds, the relationship between quantum field theory and mathematics is far too fluid in the world of modern research to be described as the simple provision ...
    • Digraphs with All Induced Directed Cycles of the Same Length are not → χ -Bounded 

      Carbonero, Alvaro; Hompe, Patrick; Moore, Benjamin; Spirkl, Sophie (2022-10-07)
      For t > 2, let us call a digraph D t-chordal if all induced directed cycles in D have length equal to t. In an earlier paper, we asked for which t it is true that t-chordal graphs with bounded clique number have bounded ...
    • Enumerative perspectives on chord diagrams 

      Nabergall, Lukas (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 ...
    • Edge-disjoint Linkages in Infinite Graphs 

      Assem Abd-AlQader Mahmoud, Amena (University of Waterloo, 2022-09-26)
      The main subject of this thesis is the infinite graph version of the weak linkage conjecture by Thomassen [24]. We first prove results about the structure of the lifting graph; Theorems 2.2.8, 2.2.24, and 2.3.1. As an ...
    • Clique minors in dense matroids 

      Rivera Omana, Fernanda (University of Waterloo, 2022-09-23)
      The objective of this thesis is to bound the number of points a $U_{2,\ell+2}$- and $M(K_{k+1})$-minor-free matroid has. We first prove that a sufficiently large matroid will contain a structure called a tower. We then use ...
    • Transversal Problems In Sparse Graphs 

      Sun, Hao (University of Waterloo, 2022-09-20)
      Graph transversals are a classical branch of graph algorithms. In such a problem, one seeks a minimum-weight subset of nodes in a node-weighted graph $G$ which intersects all copies of subgraphs~$F$ from a fixed family ...
    • A Counterexample to a Conjecture About Triangle-Free Induced Subgraphs of Graphs with Large Chromatic Number 

      Carbonero, Alvaro; Hompe, Patrick; Moore, Benjamin; Spirkl, Sophie (Elsevier ScienceDirect, 2023-01)
      We prove that for every n, there is a graph G with χ(G) ≥ n and ω(G) ≤ 3 such that every induced subgraph H of G with ω(H) ≤ 2 satisfies χ(H) ≤ 4.This disproves a well-known conjecture. Our construction is a digraph with ...
    • Induced Subgraphs and Tree Decompositions III. Three-Path-Configurations and Logarithmic Treewidth. 

      Abrishami, Tara; Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (Advances in Combinatorics, 2022-09-09)
      A theta is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family H of graphs, we say a graph G is H-free if no induced subgraph of G is ...

      UWSpace

      University of Waterloo Library
      200 University Avenue West
      Waterloo, Ontario, Canada N2L 3G1
      519 888 4883

      All items in UWSpace are protected by copyright, with all rights reserved.

      DSpace software

      Service outages