Please email any errors or updates to our website support/editor.

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, p_{1}) and G(n, p_{2}) where probabilities p_{1} and p_{2} 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 *K*_{5} 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 R^{d} 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.

Please email any errors or updates to our website support/editor.

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