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

PDF files require Adobe Acrobat Reader.

Visit our **COVID-19 Information website** for information on our response to the pandemic.

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

Friday, July 26, 2019 — 1:00 PM EDT

**Title:** New and Simple Algorithms for Stable Flow Problems

Speaker: | Justin Toth |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

In the previous reading group talk we defined stable flows and saw that they always exist by a reduction to the stable allocation problem.

Thursday, July 25, 2019 — 3:30 PM EDT

**Title:** Lewis Carroll and the Red Hot Potato

Speaker: | Melanie Dennis |

Affiliation: | Dartmouth College |

Room: | MC 5417 |

**Abstract:**

The Lewis Carroll identity expresses the determinant of a matrix in terms of subdeterminants obtained by deleting one row and column or a pair of rows and columns.

Thursday, July 25, 2019 — 2:30 PM EDT

**Title:** Kemeny's Constant for Markov Chains

Speaker: | Steve Kirkland |

Affiliation: | University of Manitoba |

Room: | MC 5479 |

**Abstract:**

Markov chains are a much-studied class of stochastic processes, and it is well-known that if the transition matrix A associated with a Markov chain possesses a certain property (called primitivity), then the long-term behaviour of the Markov chain is described by a particular eigenvector of A, known as the stationary distribution vector.

Wednesday, July 24, 2019 — 4:30 PM EDT

**Title:** Graphs in algebra and algebra in graphs

Speaker: | Soffia Arnadottir |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

How do algebraic properties of a graph relate to its graph theoretic properties? What are algebraic properties of graphs? What does the spectrum of a graph tell us about its structure? What is a Cayley graph?

Tuesday, July 23, 2019 — 3:30 PM EDT

**Title:** Reverse plane partitions via quiver representations

Speaker: | Hugh Thomas |

Affiliation: | Université du Québec à Montréal |

Room: | MC 5417 |

**Abstract:**

Let $\lambda$ be a partition. The reverse plane partitions of shape $\lambda$ are a kind of filling of the Ferrers diagram of $\lambda$ by non-negative integers. Richard Stanley found the generating function which enumerates them according to the sum of the entries.

Friday, July 19, 2019 — 3:30 PM EDT

**Title:** QAOA Versus Classical

Speaker: | Mario Szegedy |

Affiliation: | Alibaba Quantum Laboratory |

Room: | MC 5501 |

**Abstract:**

There has been a back and forth about whether the QAOA algorithm of Farhi, Goldstone and Gutmann can in some sense be duplicated classically.

Friday, July 19, 2019 — 1:00 PM EDT

**Title:** Stable Flows

Speaker: | Sharat Ibrahimpur |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

We describe a flow model that generalizes ordinary network flows the same way as stable matchings generalize the bipartite matching problem.

Thursday, July 18, 2019 — 3:30 PM EDT

**Title:** Incidence bialgebras of monoidal categories

Speaker: | Lucia Rotheray |

Affiliation: | Technische Universität Dresden |

Room: | MC 5417 |

**Abstract:**

We begin with Joni and Rota's definition of the incidence coalgebra of a category or partially ordered set and then discuss some cases where a monoidal product on a category turns this coalgebra into a bialgebra.

Tuesday, July 16, 2019 — 3:30 PM EDT

**Title:** From Combinatorics to Computer Algebra and Morse Theory - Making Sense of Multivariate Asymptotics

Speaker: | Stephen Melczer |

Affiliation: | University of Pennsylvania |

Room: | MC 5479 |

**Abstract:**

The asymptotic study of multivariate generating functions comprises the domain of Analytic Combinatorics in Several Variables (ACSV).

Friday, July 12, 2019 — 3:30 PM EDT

**Title:** On the approximability of the stable matching problem with ties of size two and one-sided ties

Speaker: | Kanstantsin Pashkovich |

Affiliation: | University of Ottawa |

Room: | MC 5501 |

**Abstract:**

The stable matching problem is central for game theory. If participants are allowed to have ties, the problem of finding a stable matching of maximum cardinality is an NP-hard problem, even when the ties are of size two.

Friday, July 12, 2019 — 1:00 PM EDT

**Title:** A (1 + 1/*e*)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists

Speaker: | Madison Van Dyk |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract**:

We will continue the discussion of stable matching when there are unacceptable pairs and one-sided ties. Two weeks ago, we looked at a 3/2-approximation that was purely combinatorial.

Thursday, July 11, 2019 — 3:30 PM EDT

**Title:** Indicence groups of graphs, forbidden minors, and planar covers

Speaker: | William Slofstra |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

The solution group of binary linear system is a quantum-probabilistic generalization of the solution space of the system.

Friday, July 5, 2019 — 3:03 PM EDT

**Title:** Feynman graphs to chord diagrams

Speaker: | Karen Yeats |

Affiliation: | University of Waterloo |

Room: | MC 5501 |

**Abstract:**

I will explain how classic techniques of algebraic combinatorics can, via chord diagrams, tell us about the leading log, next-to-leading log, etc, expansions in quantum field theory, and what we think chord diagrams can tell us about individual Feynman graphs as well.

Friday, July 5, 2019 — 1:00 PM EDT

**Title:** Quasi-popular Matchings, Optimality, and Extended Formulations

Speaker: | Kanstantsin Pashkovich |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

The goal of this talk is to obtain efficient algorithms for computing desirable matchings (wrt cost) by paying the price of mildly relaxing popularity.

Thursday, July 4, 2019 — 3:30 PM EDT

**Title:** Fun with Pfaffians: Identities for Schur Q-Functions

Speaker: | Angele Hamel |

Affiliation: | Wilfrid Laurier University |

Room: | MC 5417 |

**Abstract:**

Schur functions determinantal identities (e.g. Jacobi-Trudi, Giambelli) are cornerstones of symmetric function theory. Less well-known are the Pfaffian identities for Schur Q-functions.

Thursday, July 4, 2019 — 2:30 PM EDT

**Title:** Mutually unbiased bases

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

A pair of d x d unitary matrices is unbiased if M*N is at, i.e., all its entries have the same absolute value. A relatively simple argument shows that a set of pairwise unbiased unitary matrices has size at most d + 1.

Tuesday, July 2, 2019 — 4:00 PM EDT

**Title:** Dyadic matroids with spanning cliques

Speaker: | Kevin Grace |

Affiliation: | University of Bristol |

Room: | MC 5479 |

^{*Please note time and date change}

**Abstract:**

The Matroid Minors Project of Geelen, Gerards, and Whittle describes the structure of minor-closed classes of matroids representable over a fixed finite field.

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