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, September 27, 2021 — 11:30 AM EDT
Title: Graph Continued Fractions
| Speaker: | Thomás Spier |
| Affiliation: | Matemática Pura e Aplicada (IMPA) |
| Zoom: | Contact Soffia Arnadottir |
Abstract:
This talk is about a connection between matching polynomials and continued fractions. For the matching polynomials: we prove a refinement of a theorem by Ku and Wong, which extends the classical Gallai-Edmonds decomposition;
Thursday, September 30, 2021 — 10:00 AM EDT
Title: Semidefinite Optimization Approaches for Reactive Optimal Power Flow Problems
| Speaker: | Miguel Anjos |
| Affiliation: | University of Edinburgh |
| Zoom: | Register through The Fields Institute |
Abstract:
The Reactive Optimal Power Flow (ROPF) problem consists in computing an optimal power generation dispatch for an alternating current transmission network that respects power flow equations and operational constraints. Some means of voltage control are modelled in ROPF such as the possible activation of shunts, and these controls are modelled using discrete variables. The ROPF problem belongs to the class of nonconvex MINLPs, which are NP-hard problems. We consider semidefinite optimization approaches for solving ROPF problems and their integration into a branch-and-bound algorithm.
Thursday, September 30, 2021 — 11:00 AM EDT
Title: Structured (In)Feasibility: Nonmonotone Operator Splitting in Nonlinear Spaces
| Speaker: | Bissan Ghaddar |
| Affiliation: | Western University |
| Zoom: | Register through The Fields Institute |
Abstract:
Several challenging optimization problems in power networks involve operational decisions, non-linear models of the underlying physics described by the network as well as uncertainty in the system parameters. However, these networks exhibit a nice structure. This talk provides an overview of approaches that combine recent advances in robust optimization and conic relaxations of polynomial optimization problems along with exploiting the structure of the underlying problem. These approaches are demonstrated on applications arising in power networks.
Thursday, September 30, 2021 — 1:00 PM EDT
Title: Forcing Quasirandomness in Permutations
| Speaker: | John Noel |
| Affiliation: | University of Victoria |
| Zoom: | Contact Steve Melczer |
Abstract:
A striking result in graph theory is that the property of a graph being quasirandom (i.e. resembling a random graph) is characterized by the number of edges and the number of 4-cycles being close to the expected number in a random graph. Král’ and Pikhurko (2013) proved an analogous result for permutations; i.e. that quasirandom permutations are characterized by the densities of all permutations of length 4.
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.
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.
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.