Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Monday, October 25, 2021 11:30 AM EDT
Title: State transfer on graphs with twin vertices
| Speaker: | Hermie Monterde |
| Affiliation: | University of Manitoba |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
In this talk, we discuss algebraic and spectral properties of graphs with twin vertices that are important in quantum state transfer. We give a characterization of strong cospectrality between twin vertices, and characterize some types of state transfer that occur between them.
Friday, October 22, 2021 3:30 PM EDT
Title: Dyadic Linear Programming
| Speaker: | Ahmad Abdi |
| Affiliation: | London School of Economics |
| Zoom: | Please email Emma Watson |
Abstract:
Most linear programming solvers use fixed-precision floating points to approximate the rational numbers. Though successful on most real-world instances, solvers sometimes run into serious issues when carrying out sequential floating-point arithmetic, due to compounded error terms. This practical limitation leads to the following theoretical problem:
Friday, October 8, 2021 3:30 PM EDT
Title: Induced subgraphs and treewidth
| Speaker: | Sophie Spirkl |
| Affiliation: | University of Waterloo |
| Zoom: | Please email Emma Watson |
Abstract:
Treewidth, introduced by Robertson and Seymour in the graph minors series, is a fundamental measure of the complexity of a graph. While their results give an answer to the question, “what minors occur in graphs of large treewidth?,” the same question for induced subgraphs is still open. I will talk about some conjectures and recent results in this area.
Joint work with Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Sepehr Hajebi, Pawel Rzazewski, Kristina Vuskovic.
Thursday, October 7, 2021 1:00 PM EDT
Title: Newell-Littlewood numbers
| Speaker: | Shiliang Gao |
| Affiliation: | University of Illinois at Urbana-Champaign |
| Zoom: | Contact Steve Melczer |
Abstract:
The Newell-Littlewood numbers are defined in terms of the Littlewood-Richardson coefficients. Both arise as tensor product multiplicities for a classical Lie group. A. Klyachko connected eigenvalues of sums of Hermitian matrices to the saturated LR-cone and established defining linear inequalities.
Monday, October 4, 2021 11:30 AM EDT
Title: Four families of polynomials in spectral graph theory
| Speaker: | Miguel Angel Fiol Mora |
| Affiliation: | Universitat Politècnica de Catalunya |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
In this talk we describe four families of polynomials related to the spectrum of a graph. First, some known main results involving such polynomials, such as the spectral excess theorem characterizing distance-regularity, are discussed. Second, some new results giving bounds for the $k$-independence number $\alpha_k$ of a graph are presented. In this context, we comment on some relationships between the inertia (Cvetkovi\`c) and ratio (Hoffman) bounds of $\alpha_k$.
Friday, October 1, 2021 3:30 PM EDT
Title: Quantum information science for combinatorial optimization
| Speaker: | Stephen Jordan |
| Affiliation: | Microsoft Quantum & University of Maryland |
| Zoom: | Please email Emma Watson |
Abstract:
Due to input-output bottlenecks, quantum computers are expected to be most applicable to problems for which the quantity of data specifying the instance is small but the computational cost of finding a solution is large. Aside from cryptanalysis and quantum simulation, combinatorial optimization provides some of the best candidates for problems of real-world impact fitting these criteria. Many of these problems are NP-hard and thus unlikely to be solvable on quantum computers with polynomial worst-case time complexity.