Combinatorics and Optimization: Recent submissions
Now showing items 41-60 of 435
-
Induced Subgraphs and Tree Decompositions III. Three-Path-Configurations and Logarithmic Treewidth.
(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 ... -
Two combinatorial problems from craniosynostosis
(University of Waterloo, 2022-09-08)The art of cranial vault remodelling surgery is amazing and fascinating, but remains much of that, an art, to this day. In this thesis, we provide two mathematical approaches to tackle cranial vault remodelling surgery, ... -
Polyhedral Diameters and Applications to Optimization
(University of Waterloo, 2022-09-01)The Simplex method is the most popular algorithm for solving linear programs (LPs). Geometrically, it moves from an initial vertex solution to an improving neighboring one, selected according to a pivot rule. Despite decades ... -
On the Power and Limitations of Shallow Quantum Circuits
(University of Waterloo, 2022-09-01)Constant-depth quantum circuits, or shallow quantum circuits, have been shown to exhibit behavior that is uniquely quantum. This thesis explores the power and limitations of constant-depth quantum circuits, in particular ... -
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 ... -
Local properties of graphs with large chromatic number
(University of Waterloo, 2022-08-31)This thesis deals with problems concerning the local properties of graphs with large chromatic number in hereditary classes of graphs. We construct intersection graphs of axis-aligned boxes and of lines in $\mathbb{R}^3$ ... -
Algorithm Design for Ordinal Settings
(University of Waterloo, 2022-08-29)Social choice theory is concerned with aggregating the preferences of agents into a single outcome. While it is natural to assume that agents have cardinal utilities, in many contexts, we can only assume access to the ... -
Lattice Paths
(University of Waterloo, 2022-08-24)This thesis is a survey of some of the well known results in lattice path theory. Chapter 1 looks into the history of lattice paths. That is, when it began and how it was popularized. Chapter 3 focuses on general lattices ... -
Cycles and coloring in graphs and digraphs
(University of Waterloo, 2022-08-22)We show results in areas related to extremal problems in directed graphs. The first concerns a rainbow generalization of the Caccetta-H\"{a}ggkvist conjecture, made by Aharoni. The Caccetta-H\"{a}ggkvist conjecture states ... -
Sandwich and probe problems for excluding paths
(Elsevier, 2018-12-31)Let Pk denote an induced path on k vertices. For k ≥ 5, we show that the Pk-free sandwich problem, partitioned probe problem, and unpartitioned probe problem are NP-complete. For k ≤ 4, it is known that the Pk-free sandwich ... -
Minimal induced subgraphs of two classes of 2-connected non-Hamiltonian graphs
(Elsevier, 2022-07)In 1981, Duffus, Gould, and Jacobson showed that every connected graph either has a Hamiltonian path, or contains a claw (K1,3) or a net (a fixed six-vertex graph) as an induced subgraph. This implies that subject to being ... -
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 ... -
Modular relations of the Tutte symmetric function
(Elsevier, 2022-04)For a graph G, its Tutte symmetric function XBG generalizes both the Tutte polynomial TG and the chromatic symmetric function XG. We may also consider XB as a map from the t-extended Hopf algebra G[t] of labelled graphs ... -
Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
(Society for Industrial and Applied Mathematics, 2021-10-14)We study the Max Partial H-Coloring problem: given a graph G, find the largest induced subgraph of G that admits a homomorphism into H, where H is a fixed pattern graph without loops. Note that when H is a complete graph ... -
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, ... -
Pure Pairs VI. Excluding an Ordered Tree.
(Society for Industrial and Applied Mathematics Journal on Discrete Mathematics, 2022-01)A pure pair in a graph G is a pair (Z1,Z2) of disjoint sets of vertices such that either every vertex in Z1 is adjacent to every vertex in Z2, or there are no edges between Z1 and Z2. With Maria Chudnovsky, we recently ... -
The Traveling Tournament Problem
(University of Waterloo, 2022-08-17)In this thesis we study the Traveling Tournament problem (TTP) which asks to generate a feasible schedule for a sports league such that the total travel distance incurred by all teams throughout the season is minimized. ... -
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 ... -
Plethysms of Chromatic and Tutte Symmetric Functions
(The Electronic Journal of Combinatorics, 2022)Plethysm is a fundamental operation in symmetric function theory, derived directly from its connection with representation theory. However, it does not admit a simple combinatorial interpretation, and finding coefficients ... -
Concatenating Bipartite Graphs
(The Electronic Journal of Combinatorics, 2022)Let x, y E (0, 1], and let A, B, C be disjoint nonempty stable subsets of a graph G, where every vertex in A has at least x |B| neighbors in B, and every vertex in B has at least y|C| neighbors in C, and there are no edges ...