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, May 31, 2019 — 3:30 PM EDT
Title: Quantum Log-Approximate-Rank Conjecture is also False
| Speaker: | Anurag Anshu |
| Affiliation: | Institute for Quantum Computing - University of Waterloo |
| Room: | MC 5501 |
Abstract:
In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function `f', hence refuting the log approximate rank conjecture of Lee and Shraibman [2009].
Friday, May 31, 2019 — 1:00 PM EDT
Title: A Fixed-Point Approach to Stable Matchings
| Speaker: | Akshay Ramachandran |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
This talk will be independent of the previous reading group talk. Three classical results in stable matching are the correctness of Gale Shapley’s deferred acceptance algorithm, the result of Conway that Stable Matchings form a distributive lattice, and Vande Vate and later Rothblum’s result that the convex hull of stable matchings has a polynomial-sized linear description.
Thursday, May 30, 2019 — 3:30 PM EDT
Title: Wronskians of polynomials
| Speaker: | Kevin Purbhoo |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
The Mukhin-Tarasov-Varchenko (MTV) theorem is the following statement in real algebraic geometry. If the wronskian of a set of complex polynomials has only real roots, then the vector space spanned by these polynomials is real.
Friday, May 24, 2019 — 3:30 PM EDT
Title: The sandwich conjecture of random regular graphs and more
| Speaker: | Mikhail Isaev |
| Affiliation: | Monash University |
| Room: | MC 5501 |
Abstract:
The sandwich conjecture formulated in [Kim, Vu, Advances in Math., 2004] states that if d >> log n, then the random d-regular graph on n vertices R(n, d) can asymptotically almost surely be ”sandwiched” between G(n, p1) and G(n, p2) where probabilities p1 and p2 are both (1 + o(1))d/n.
Friday, May 24, 2019 — 2:03 PM EDT
Title: Free Groups
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
(The "free" in the title is an adjective, not a verb.) I will discuss free groups from a combinatorial perspective, focusing on the connections to fundamental groups and covers of graphs.
Thursday, May 23, 2019 — 2:30 PM EDT
Title: Some results concerning frozen homomorphisms
| Speaker: | Ben Moore |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
A colouring is frozen if you cannot change any vertices colour and remain a proper colouring.
Wednesday, May 22, 2019 — 3:30 PM EDT
Title: The distribution of tree parameters via the martingale CLT
| Speaker: | Mikhail Isaev |
| Affiliation: | Monash University |
| Room: | MC 5479 |
Abstract:
Tree parameters, like pattern or symmetry counts, have been extensively studied in the literature for various random models.
Friday, May 17, 2019 — 1:00 PM EDT
Title: A Fixed-Point Approach to Stable Matchings
| Speaker: | Cedric Koh |
| Affiliation: | London School of Economics |
| Room: | MC 5479 |
Abstract:
We describe a xed-point based approach to the theory of bipartite stable matchings.
Thursday, May 16, 2019 — 3:30 PM EDT
Title: Partial progress on enumerating K5 descendants
| Speaker: | Karen Yeats |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
We call a particular operation on a graph which converts one triangle into two triangles a double triangle expansion, and call all those graphs which can be obtained from repeated double triangle expansions of a fixed graph the double triangle descendants of the graph.
Thursday, May 16, 2019 — 2:30 PM EDT
Title: The 600-cell as a Cayley graph
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
I will discuss some of the things we can learn about the 600-cell by viewing it as a Cayley graph for the group SL(2,5) (once I've discussed the basic properties of this group).
Wednesday, May 15, 2019 — 3:30 PM EDT
Title: Spanning cycles in Hypergraphs
| Speaker: | Richard Lang |
| Affiliation: | University of Waterloo |
| Room: | MC 5479* |
*Please note the room change from the previous week
Abstract:
A long time ago, Lehel asked whether the vertex set of every complete graph, whose edges have been coloured red and blue, can be partitioned into a red and a blue cycle.
Friday, May 10, 2019 — 3:30 PM EDT
Title: Stochastic optimization methods beyond stochastic gradient descent
| Speaker: | Katya Scheinberg |
| Affiliation: | Lehigh University |
| Room: | MC 5501 |
Abstract:
We will present a very general framework for unconstrained stochastic optimization which encompasses standard frameworks such as line search and trust region using random models.
Friday, May 10, 2019 — 1:00 PM EDT
Title: Stable Matching Overview
| Speaker: | Justin Toth |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
This semester, the CombOpt Reading Group studies Stable Matching. In this talk we will introduce the basic concepts in stable matching, provide an overview of the planned papers to be discussed this semester, and mention interesting open questions along the way.
Thursday, May 9, 2019 — 2:30 PM EDT
Title: The 600-cell
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 5479 |
Abstract:
If d ≥ 5, then in Rd there are exactly three regular polytopes (simple, hypercube, dual hypercube). If d = 3 we have the icosahedron and the dodecahedron in addition. If d = 4, there are again two exceptional regular polytopes, the so-called 120-cell and 600-cell.
Wednesday, May 8, 2019 — 3:30 PM EDT
Title: The Erdős-Pósa property for A-paths
| Speaker: | Jim Geelen |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
Let A be a set of vertices in a graph G. An A-path is a path whose ends are in A. Gallai proved, for any integer k, that there are either k disjoint A-paths or there is a set of at most 2k vertices that hit all A-paths.
Friday, May 3, 2019 — 3:30 PM EDT
Title: From Warragul to Waterloo
| Speaker: | Chris Godsil |
| Affiliation: | University of Waterloo |
| Room: | MC 5501 |
Abstract:
As Tom Lehrer once said “Some of you may have run into mathematicians, and therefore had occasion to wonder how they got that way”; this talk will be a partial explanation of how I got this way.