Events - May 2019

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.

S M T W T F S
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
  1. 2019 (127)
    1. September (13)
    2. August (9)
    3. July (17)
    4. June (18)
    5. May (16)
    6. April (9)
    7. March (24)
    8. February (13)
    9. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)