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

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

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

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within our Office of Indigenous Relations.