Browsing Combinatorics and Optimization by Title
Now showing items 144-163 of 435
-
Ehrhart Theory and Unimodular Decompositions of Lattice Polytopes
(University of Waterloo, 2015-01-20)Ehrhart theory studies the behaviour of lattice points contained in dilates of lattice polytopes. We provide an introduction to Ehrhart theory. In particular, we prove Ehrhart's Theorem, Stanley Non-negativity, and ... -
Eigenvalue, Quadratic Programming and Semidefinite Programming Bounds for Graph Partitioning Problems
(University of Waterloo, 2014-09-03)The Graph Partitioning problems are hard combinatorial optimization problems. We are interested in both lower bounds and upper bounds. We introduce several methods including basic eigenvalue and projected eigenvalue ... -
Entropic Matroids and Their Representation
(Multidisciplinary Digital Publishing Institute, 2019)This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have ... -
Entropy and Graphs
(University of Waterloo, 2014-01-23)The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and ... -
Enumerating matroid extensions
(University of Waterloo, 2023-09-01)This thesis investigates the problem of enumerating the extensions of certain matroids. A matroid M is an extension of a matroid N if M delete e is equal to N for some element e of M. Similarly, a matroid M is a coextension ... -
Enumeration of Factorizations in the Symmetric Group: From Centrality to Non-centrality
(University of Waterloo, 2011-04-25)The character theory of the symmetric group is a powerful method of studying enu- merative questions about factorizations of permutations, which arise in areas including topology, geometry, and mathematical physics. This ... -
Enumerative Applications of Integrable Hierarchies
(University of Waterloo, 2015-05-21)Countably infinite families of partial differential equations such as the Kadomtzev - Petviashvili (KP) hierarchy and the B-type KP (BKP) hierarchy have received much interest in the mathematical and theoretical physics ... -
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 ... -
The Erdős Pentagon Problem
(University of Waterloo, 2018-12-20)The Erdős pentagon problem asks about the maximum number of copies of C_5 that one can find in a triangle-free graph. This problem was posed in 1984, but was not resolved until 2012. In this thesis, we aim to capture the ... -
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. ... -
Establishing a Connection Between Graph Structure, Logic, and Language Theory
(University of Waterloo, 2015-09-08)The field of graph structure theory was given life by the Graph Minors Project of Robertson and Seymour, which developed many tools for understanding the way graphs relate to each other and culminated in the proof of the ... -
Evaluating Large Degree Isogenies between Elliptic Curves
(University of Waterloo, 2010-12-20)An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves ... -
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 ... -
Even pairs and prism corners in square-free Berge graphs
(Elsevier, 2018-07)Let G be a Berge graph such that no induced subgraph is a 4-cycle or a line-graph of a bipartite subdivision of K4. We show that every such graph G either is a complete graph or has an even pair. -
Exact, Approximate, and Online Algorithms for Optimization Problems Arising in DVD Assignment
(University of Waterloo, 2009-09-01)Zip.ca is an online DVD rental company that faces two major operational problems: calculation of the assignment of DVDs to customers every thirty minutes throughout the day and purchasing of new inventory in regular ... -
The Existence of Balanced Tournament Designs and Partitioned Balanced Tournament Designs
(University of Waterloo, 2001)A balanced tournament design of order <I>n</I>, BTD(<I>n</I>), defined on a 2<I>n</I>-set<I> V</i>, is an arrangement of the all of the (2<I>n</i>2) distinct unordered pairs of elements of <I>V</I> into an <I>n</I> X ... -
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 ... -
Extending Pappus' Theorem
(University of Waterloo, 2017-12-22)Let $M_1$ and $M_2$ be matroids such that $M_2$ arises from $M_1$ by relaxing a circuit-hyperplane. We will prove that if $M_1$ and $M_2$ are both representable over some finite field $GF(q)$, then $M_1$ and $M_2$ have ... -
Extensions of Galvin's Theorem
(University of Waterloo, 2018-04-30)We discuss problems in list coloring with an emphasis on techniques that utilize oriented graphs. Our central theme is Galvin's resolution of the Dinitz problem (Galvin. J. Comb. Theory, Ser. B 63(1), 1995, 153--158). We ...