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