Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Friday, June 28, 2019 3:30 PM EDT
Title: On the hardness of computing the diameter of a polytope
| Speaker: | Laura Sanita |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
The diameter of a polytope P is given by the maximum length of a shortest path between a pair of vertices on P. Giving bounds on the diameter of a polytope is a fundamental research topic in theoretical computer science and discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex Algorithm for solving Linear Programs.
Friday, June 28, 2019 1:00 PM EDT
Title: Approximation Algorithms for the Stable Marriage Problem
| Speaker: | Madison Van Dyk |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
This week we will discuss stable matching when there are unacceptable pairs and preferences include ties. In this setting one can also consider the Hospitals/Residents problem and the variant where ties are one-sided.
Thursday, June 27, 2019 3:30 PM EDT
Title: From Modeling Fermions to the Puzzle Rule
| Speaker: | Timothy Miller |
| Affiliation: | University of Waterloo |
| Room: | MC 6483* |
*room change
Abstract:
A Knutson-Tao-Woodward puzzle is a tiling of a triangle with certain pieces that have labeled edges. The puzzle rule states that number of puzzles with a given boundary is equal to a Littlewood-Richardson coefficient.
Wednesday, June 26, 2019 3:30 PM EDT
Title: Quadratically Dense Matroids
| Speaker: | Zach Walsh |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
We discuss recent work proving that for any integer $t\ge 2$, any maximum-sized simple $\mathbb C$-representable matroid $M$ of large rank with no $U_{2,t+3}$-minor satisfies $|M|=t{r(M)\choose 2}+r(M)$. It was not our intention to prove this result, so we will first explain our original motivation. We assume only basic knowledge of matroid theory.
Tuesday, June 25, 2019 3:30 PM EDT
Title: Sequences of Trees and Higher-Order Renormalization Group Equations
| Speaker: | William Dugan |
| Affiliation: | University of Waterloo |
| Room: | MC 6483 |
Abstract:
In 1998, Connes and Kreimer introduced a combinatorial Hopf algebra HCK on the vector space of forests of rooted trees that precisely explains the phenomenon of renormalization in quantum eld theory.
Friday, June 21, 2019 3:30 PM EDT
Title: Finding perfect matchings in random regular graphs in linear expected time
| Speaker: | Michael Anastos |
| Affiliation: | Carnegie Mellon University |
| Room: | MC 5501 |
Abstract:
In a seminal paper on finding large matchings in sparse random graphs, Karp and Sipser proposed two algorithms for this task. The second algorithm has been intensely studied, but due to technical difficulties, the first algorithm has received less attention. Empirical results suggest that the first algorithm is superior.
Friday, June 21, 2019 1:00 PM EDT
Title: Maximum Cardinality Popular Matchings
| Speaker: | Ishan Bansal |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
We have seen the algorithm by Abraham, Irving, Kavitha, and Mehlhorn which deals with finding popular matchings (can be easily modified to give maximum cardinality popular matchings) in bipartite graphs with one-sided preference lists.
Thursday, June 20, 2019 4:00 PM EDT
Title: The Parallel Postulate: a 2000-year controversy
| Speaker: | Eric Thomas Boulter |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 (Snacks served at 3:30 pm) |
Abstract:
Euclid's book The Elements was groundbreaking in its logical formulation of synthetic geometry, and it is profoundly influential to this day, as it is widely considered to be the most published non-religious book in human history.
Thursday, June 20, 2019 4:00 PM EDT
Title: The Parallel Postulate: a 2000-year controversy
| Speaker: | Eric Thomas Boulter |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Euclid's book The Elements was groundbreaking in its logical formulation of synthetic geometry, and it is profoundly influential to this day, as it is widely considered to be the most published non-religious book in human history.
Thursday, June 20, 2019 3:30 PM EDT
Title: Arborified zeta values and shuffles of rooted trees
| Speaker: | Pierre Clavier |
| Affiliation: | Potsdam University |
| Room: | MC 6483* |
*Please note room change
Abstract:
Arborified zeta values are a generalisation to rooted trees of the usual multizeta values.
Friday, June 14, 2019 3:30 PM EDT
Title: Matching Games: From Bargaining to the Nucleolus
| Speaker: | Jochen Koenemann |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
Cooperative matching games were first introduced in seminal work by Shapley and Shubik in their classic 1971 paper. In this talk, I will first review some of the key concepts and results in this area. I will then use these tools to (re-)derive several facts and algorithms for network generalizations of the famous Nash bargaining concept.
Friday, June 14, 2019 1:00 PM EDT
Title: Popularity, Mixed Matchings, and Self-duality
| Speaker: | Adam Brown |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
This week we continue our discussion of popular matchings.
Wednesday, June 12, 2019 3:30 PM EDT
Title: Spanning trees and electrical networks... and what about matroids?
| Speaker: | David Wagner |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
The relevance of spanning trees to the theory of electrifcal networks goes all the way back to Kirchhoff in 1847.
Friday, June 7, 2019 3:30 PM EDT
Title: Deducing Kurdyka-Łojasiewicz exponent of optimization models
| Speaker: | Ting Kei Pong |
| Affiliation: |
The Hong Kong Polytechnic University |
| Room: | MC 5501 |
Abstract:
Kurdyka-Łojasiewicz (KL) exponent is an important quantity for determining the qualitative convergence behavior of many first-order methods.
Friday, June 7, 2019 1:00 PM EDT
Title: Popular Matchings
| Speaker: | Lily Wang |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
We introduce a variant of the stable matching problem on a bipartite graph G = (A [ P;E)
Thursday, June 6, 2019 3:30 PM EDT
Title: Toric varieties from distributive lattices
| Speaker: | David Wagner |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
Given a nite lattice L, consider the ring of complex polynomials in indeterminates indexed by L, modulo the ideal generated by (XaXb-Xa^bXa_b for all a; b 2 L).
Thursday, June 6, 2019 2:30 PM EDT
Title: Hedetnemi's conjecture is false
| Speaker: | Ben Moore |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
On may 6th 2019, Yaroslav Shitov found a graph G x H such that the chromatic number of G x H is strictly smaller than the minimum of the chromatic number of G and the chromatic number of H. I will present the example.
Wednesday, June 5, 2019 3:30 PM EDT
Title: Approximately counting independent sets in graphs with bounded bipartite pathwidth
| Speaker: | Catherine Greenhill |
| Affiliation: | University of New South Wales |
| Room: | MC 5479 |
Abstract:
In 1989, Jerrum and Sinclair showed that a natural Markov chain for counting
matchings in a given graph G is rapidly mixing.