## University COVID-19 update

### Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

# Events by month

## June 2019

Sun Mon Tue Wed Thu Fri Sat
26
27
28
29
30
31
1

2
3
4
8

9
10
11
13
15

16
17
18
19
22

23
24
29

30
1
2
3
4
5
6

### Graphs and Matroids Seminar - Catherine Greenhill

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.

### Algebraic Graph Theory Seminar - Ben Moore

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.

### Algebraic Combinatorics Seminar - David Wagner

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

### Combinatorial Optimization Reading Group - Lily Wang

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)

### Tutte Colloquium - Ting Kei Pong

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.

### Graphs and Matroids Seminar - David Wagner

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

### Tutte Colloquium - Jochen Koenemann

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.

### Algebraic Combinatorics Seminar - Pierre Clavier

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*

Abstract:

Arborified zeta values are a generalisation to rooted trees of the usual multizeta values.

### Joint PM and C&O Colloquium - Eric Thomas Boulter

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.

### PMath/C&O Joint Colloquium - Eric Thomas Boulter

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.

### Combinatorial Optimization Reading Group - Ishan Bansal

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.

### Tutte Colloquium - Michael Anastos

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.

### Algebraic Combinatorics Seminar - William Dugan

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.

### Graphs and Matroids Seminar - Zach Walsh

Wednesday, June 26, 2019 — 3:30 PM EDT

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.

### Algebraic Combinatorics Seminar - Timothy Miller

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.

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.

### Tutte Colloquium - Laura Sanita

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.

### June 2019

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