Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
Sun  Mon  Tue  Wed  Thu  Fri  Sat 

1

3

4

7







8

9

10

11

12

14









15

17

18

21







22

23

24

25

28








29

31

1

2

3

4








Title: Neumaier graphs
Speaker: Maarten De Boeck Affiliation: University of Memphis Location: Please contact Sabrina Lato for Zoom linkAbstract: A Neumaier graph is an edgeregular graph with a regular clique. Several families of strongly regular graphs (but not all of them) are indeed Neumaier, but in 1981 it was asked whether there are Neumaier graphs that are not strongly regular. This question was only solved a few years ago by Greaves and Koolen, so now we know there are socalled strictly Neumaier graphs.
Title: Diagrammatic boundary calculus for Wilson loop diagrams
Speaker: Karen Yeats Affiliation: University of Waterloo Location: MC 6029There will be a preseminar presenting relevant background at the beginning graduate level starting at 1pm.
Abstract: This talk is about a different part of the quantum field theory story than I usually talk about. Wilson loop diagrams can be used to index amplitudes in a theory known as N=4 SYM. Suitably nice Wilson loop diagrams are also associated to positroids. For both mathematical and physical reasons it would be nice to have a diagrammatic understanding of the boundaries of the positroid cells of all codimensions. While we do not yet have a full understanding, we can build many boundaries with certain diagrammatic moves.
Joint work with Susama Agarwala and Colleen Delaney.
Title: A closure lemma for tough graphs and Hamiltonian ideals
Speaker: Chinh T. Hoang Affiliation: Wilfrid Laurier University Location: MC 5417Abstract: The closure of a graph $G$ is the graph $G^*$ obtained from $G$ by repeatedly adding edges between pairs of nonadjacent vertices whose degree sum is at least $n$, where $n$ is the number of vertices of $G$. The wellknown Closure Lemma proved by Bondy and Chv\'atal states that a graph $G$ is Hamiltonian if and only if its closure $G^*$ is. This lemma can be used to prove several classical results in Hamiltonian graph theory. We prove a version of the Closure Lemma for tough graphs.
Title: Approximate MaxFlow MinMulticut Theorem for Graphs of Bounded Treewidth
Speaker: Nikhil Kumar Affilation: University of Waterloo Location: MC 6029Abstract: I will present a recent maxflow mincut type result for graphs of bounded treewidth. Multicommodity flow is a generalization of the well known st flow problem, where we are given multiple sourcesink pairs and goal is to maximize the total flow. A natural upper bound on the value of total flow is the value of the minimum multicut : the minimum total capacity of edges that need to be removed in order to disconnect all the sourcesink pairs. We will show that given a treewidthr graph, there exists a (fractional) multicommodity flow of value F, and a multicut of capacity C such that F ≤ C ≤ O(log r)·F.
Title: Kissing Polytopes
Speaker: Antoine Deza Affiliation: McMaster University Location: MC 5501Abstract: We investigate the following question: how close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms.
Title: Approximate MaxFlow MinMulticut Theorem for Graphs of Bounded Treewidth, Part II
Speaker: Nikhil Kumar Affiliation: University of Waterloo Location: MC 6029Abstract: I will present a recent maxflow mincut type result for graphs of bounded treewidth. Multicommodity flow is a generalization of the well known st flow problem, where we are given multiple sourcesink pairs and goal is to maximize the total flow. A natural upper bound on the value of total flow is the value of the minimum multicut : the minimum total capacity of edges that need to be removed in order to disconnect all the sourcesink pairs. We will show that given a treewidthr graph, there exists a (fractional) multicommodity flow of value F, and a multicut of capacity C such that F ≤ C ≤ O(log r)·F.
Title: Kemeny’s constant for random walks on graphs
Speaker: Sooyeong Kim Affiliation: York University Location: Please contact Sabrina Lato for Zoom link.Abstract: Kemeny's constant, a fundamental parameter in the theory of Markov chains, has recently received significant attention within the graph theory community. Originally defined for a discrete, finite, timehomogeneous, and irreducible Markov chain based on its stationary vector and mean first passage times, Kemeny's constant finds special relevance in the study of random walks on graphs.
Title: Forest polynomials and harmonics for the ideal of quasisymmetric polynomials
Speaker: Vasu Tewari Affiliation: University of Toronto Location: MC 6029There will be a preseminar presenting relevant background at the beginning graduate level starting at 1pm.
Abstract: The type A coinvariant algebra, obtained by quotienting the polynomial ring by the ideal of positive degree symmetric polynomials, is a rich and active object of study. A distinguished basis for this quotient is given by Schubert polynomials. There is a dual to this story involving degree polynomials studied in depth by PostnikovStanley who shed light on their combinatorics.
Title: Fast Combinatorial Algorithms for Efficient Sortation
Speaker: Madison Van Dyk Affiliation: University of Waterloo Location: MC 6029Abstract: Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes in typical hubandspoke fashion. In practice, such consolidation requires parcelsortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation.
Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams
Speaker: Sepehr Assadi Affiliation: University of Waterloo Location: MC 5501Abstract: In this talk, we present a simple algorithm that reduces approximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs.
Title: Higherorder correlation inequalities for random spanning trees
Speaker: David Wagner Affiliation: University of Waterloo Location: MC 6029There will be a preseminar presenting relevant background at the beginning graduate level starting at 1:00 pm.
Abstract: The connection between enumerating spanning trees of a graph and the theory of (linear) electrical networks goes all the way back to Kirchhoff's 1847 paper. It is physically sensible that if one increases the conductance of one wire in an electrical network, then the overall conductance of the network can not decrease. This corresponds to the less obvious fact that any two distinct edges are nonpositively correlated, when one chooses a random spanning tree. Covariance is the 2point "Ursell function'', and expectation is the 1point Ursell function. For any subset of edges there is an associated Ursell function, and these are related to occupation probabilities by Möbius inversion. I will discuss some situations in which the signs of these Ursell functions can be predicted, yielding higherorder correlation inequalities for random spanning trees.
Title: Chromatic Number of Random Signed Graphs
Speaker: Dao Chen Yuan Affiliation: University of Waterloo Location: MC 5417Abstract: A signed graph is a graph where edges are labelled {+1,1}. A signed colouring in 2k colours maps the vertices of a signed graph to {k,...,1,1,...,k}, such that neighbours joined by a positive edge do not share the same colour, and those joined by a negative edge do not share opposite colours. It is a classical result that the chromatic number of a G(n,p) ErdosRenyi random graph is asymptotically almost surely n/(2log_b(n)), where p is constant and b=1/(1p). We extend the method used there to prove that the chromatic number of a G(n,p,q) random signed graph, where q is the probability that an edge is labelled 1, is also a.a.s. n/(2log_b(n)), if p is constant and q=o(1).
Title: Average planesize
Speaker: Jim Geelen Affiliation: University of Waterloo Location: MC 5501Abstract: In 1941, Eberhard Melchior proved that, given any finite set of points in the plane, not all on a single line, the average length of a spanned line is at most three.
Title: Graphs that Admit Orthogonal Matrices
Speaker: Shaun Fallat Affiliation: University of Regina Location: Please contact Sabrina Lato for Zoom link.Abstract: Given a simple graph $G=(\{1,\ldots, n},E), we consider the class $S(G)$ of real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}\neq 0$ iff $ij \in E$. Under the umbrella of the inverse eigenvalue problem for graphs (IEPG), $q(G)$  known as the minimum number of distinct eigenvalues of $G$  has emerged as one of the most wellstudied parameters of the IEPG. Naturally, characterizing graphs $G$ for which $q(G) \leq, =, \geq k$ is an important step for studying the IEPG.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 5198884567, ext 33038
PDF files require Adobe Acrobat Reader.
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 coordinated within the Office of Indigenous Relations.