#### Contact Info

Combinatorics & Optimization

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

Phone: 519-888-4567, ext 33038

PDF files require Adobe Acrobat Reader.

Thursday, February 27, 2020 — 2:30 PM EST

**Title:** An equivariant basis for the cohomology of Springer fibers

Speaker: | Ed Richmond |

Affiliation: | Oklahoma State University |

Room: | MC 5417 |

**Abstract:**

Springer fibers are subvarieties of the flag variety that play an important role in combinatorics and geometric representation theory. In this talk, I will discuss joint work with Martha Precup where we analyze the equivariant cohomology of Springer fibers in type A.

Thursday, February 27, 2020 — 1:00 PM EST

**Title:** Linear Programming and Extremal Expanders

Speaker: | Sabrina Lato |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Nozaki proved a linear programming bound on the number of vertices that depends on the eigenvalues of a graph.

Thursday, February 20, 2020 — 1:00 PM EST

**Title:** Triangle-free Strongly Regular Graphs

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Complete bipartite graphs aside, only five triangle-free strongly regular graphs are known. I will describe some of the background to this topic, with the focus on outlining the construction of the Higman-Sims graph.

Friday, February 14, 2020 — 1:00 PM EST

**Title: **The Aggregation Closure is Polyhedral for Packing and Covering Integer Programs

Speaker: | Kanstantsin Pashkovich |

Affiliation: | University of Ottawa |

Room: | MC 5417 |

**Abstract:**

Recently, Bodur, Del Pia, Dey, Molinaro and Pokutta introduced the concept of aggregation cuts for packing and covering integer programs.

Thursday, February 13, 2020 — 4:00 PM EST

**Title:** List Colouring and Ohba's Conjecture

Speaker: | Matt Kroeker |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

The question of when the list-chromatic number of a graph G, denoted chi_l(G), equals its chromatic number is fundamental to the theory of list colouring.

Thursday, February 13, 2020 — 2:30 PM EST

**Title: **A generalization of balanced tableaux and matching problems with unique solutions

Speaker: | Brian Chan |

Affiliation: | University of British Columbia |

Room: | MC 5417 |

**Abstract:**

In this talk, we consider families of finite sets that we call shellable and that have been characterized by Chang and Hirst and Hughes as being the families of sets that admit unique solutions to Hall's matching problem.

Thursday, February 13, 2020 — 1:00 PM EST

**Title:** Moore Graphs

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Moore graphs were introduced by Hoffman and Singleton in a fundamental paper. They can be defined as graphs with diameter $d$ and girth $2d+1$.

Thursday, February 6, 2020 — 4:00 PM EST

**Title:** Minimum degree conditions for Hamilton cycles in hypergrahs

Speaker: | Richard Lang |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

A classic result of Dirac states that a graph in which every vertex is connected to at least half of the other vertices contains a Hamilton cycle. How can we generalize Dirac's theorem to hypergraphs?

Friday, January 31, 2020 — 1:00 PM EST

**Title:** Network Design $s$-$t$ Effective Resistance

Speaker: | Hong Zhou |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

We consider a problem of designing a network with small $s$-$t$ effective resistance. In the problem, we are given an undirected graph $G=(V,E)$, two designated vertices $s,t \in V$, and a budget $k$.

Thursday, January 30, 2020 — 4:00 PM EST

**Title:** Excluding a ladder

Speaker: | Paul Wollan |

Affiliation: | Sapienza Università di Roma |

Room: | MC 5479 |

**Abstract:**

A folklore result says that if a graph does not contain the path of length k as a subgraph, then it has tree-depth at most k.

Thursday, January 30, 2020 — 2:30 PM EST

**Title: **Random Pattern-Avoiding Permutations

Speaker: | Neal Madras |

Affiliation: | York University |

Room: | MC 5417 |

**Abstract:**

A "pattern of length k" is simply a permutation of {1,..,k}. This pattern is said to be contained in a permutation of {1,...,N} (for N>k) if there is a subsequence of k elements of the (long) permutation that appears in the same relative order as the pattern.

Friday, January 24, 2020 — 1:00 PM EST

**Title:** On the Strong Nine Dragon Tree Conjecture

Speaker: | Ben Moore |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Nash-Williams forest covering theorem says that a graph decomposes into $k$ forests if and only if it has fractional arboricity at most $k$. In 2012 Mickeal Montassier, Patrice Ossona de Mendez, Andre Raspaud, and Xuding Zhu proposed a significant strengthening of Nash-Williams Theorem, called the Strong Nine Dragon Tree Conjecture.

Thursday, January 23, 2020 — 4:00 PM EST

**Title:** Uniformly generate graphs with given degrees rapidly

Speaker: | Jane Gao |

Affiliation: | University of Waterloo |

Room: | MC 5479 |

**Abstract:**

I will survey the research on exact/approximate uniform generation of graphs with prescribed degrees.

Thursday, January 23, 2020 — 2:30 PM EST

**Title:** Some places matroids appear in quantum field theory and some places I would like them to

Speaker: | Karen Yeats |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

I will discuss some places matroids have appeared in my work in quantum field theory, including some older work on numerator structure with Dirk Kreimer and some work in progress with Iain Crump on period identities.

Friday, January 17, 2020 — 1:00 PM EST

**Title:** The Capacitated Survivable Network Design Problem

Speaker: | Ishan Bansal |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

The Capacitated Survivable Network Design Problem or Cap-SNDP models a network reinforcement problem where the network designer wants to find a minimum-cost set of reinforcements that protects the network from an adversary.

Thursday, January 16, 2020 — 2:03 PM EST

**Title:** Electrical networks, random spanning trees, and matroids

Speaker: | David Wagner |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

This is a reprise of a survey talk I gave at the East Coast Combinatorics Conference in August 2019, and a variation of one I gave in the graphs and matroids seminar last year.

Thursday, January 16, 2020 — 1:00 PM EST

**Title:** Covers of Complete Bipartite Graphs

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

I will discuss antipodal distance-regular covers of complete bipartite graphs $K_{n,n}$. The index of such a cover is at most $n$.

Friday, January 10, 2020 — 1:00 PM EST

**Title:** Beating 3/2 for Approximating TSP in the Half-Integral Case

Speaker: | Logan Grout |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

In 2013, Schalekamp, Williamson, and van Zuylen conjectured that the integrality gap for the Subtour Polytope was attained on its half-integral vertices.

Thursday, January 9, 2020 — 1:00 PM EST

**Title:** Periodicity in Quantum Walks

Speaker: | Chris Godsil |

Affiliation: | University of Waterloo |

Room: | MC 5417 |

**Abstract:**

Despite the title, quantum walks are, in general, not periodic. However they are, in general, periodic to any desired degree of accuracy.

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 centralized within our Office of Indigenous Relations.