#### 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.

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

University of Waterloo

University of Waterloo

43.471468

-80.544205

200 University Avenue West

Waterloo,
ON,
Canada
N2L 3G1

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Indigenous Initiatives Office.