Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Monday, October 30, 2023 11:30 AM EDT
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 well-studied parameters of the IEPG. Naturally, characterizing graphs $G$ for which $q(G) \leq, =, \geq k$ is an important step for studying the IEPG.
Friday, October 27, 2023 3:30 PM EDT
Title: Average plane-size
| Speaker: | Jim Geelen |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: 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.
Thursday, October 26, 2023 3:00 PM EDT
Title: Chromatic Number of Random Signed Graphs
| Speaker: | Dao Chen Yuan |
| Affiliation: | University of Waterloo |
| Location: | MC 5417 |
Abstract: 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) Erdos-Renyi random graph is asymptotically almost surely n/(2log_b(n)), where p is constant and b=1/(1-p). 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).
Thursday, October 26, 2023 2:00 PM EDT
Title: Higher-order correlation inequalities for random spanning trees
| Speaker: | David Wagner |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
There will be a pre-seminar 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 non-positively correlated, when one chooses a random spanning tree. Covariance is the 2-point "Ursell function'', and expectation is the 1-point 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 higher-order correlation inequalities for random spanning trees.
Friday, October 20, 2023 3:30 PM EDT
Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams
| Speaker: | Sepehr Assadi |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: 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.
Friday, October 20, 2023 1:00 PM EDT
Title: Fast Combinatorial Algorithms for Efficient Sortation
| Speaker: | Madison Van Dyk |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: 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 hub-and-spoke fashion. In practice, such consolidation requires parcel-sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation.
Thursday, October 19, 2023 2:00 PM EDT
Title: Forest polynomials and harmonics for the ideal of quasisymmetric polynomials
| Speaker: | Vasu Tewari |
| Affiliation: | University of Toronto |
| Location: | MC 6029 |
There will be a pre-seminar 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 Postnikov-Stanley who shed light on their combinatorics.
Monday, October 16, 2023 11:30 AM EDT
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, time-homogeneous, 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.
Friday, October 13, 2023 1:00 PM EDT
Title: Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth, Part II
| Speaker: | Nikhil Kumar |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: I will present a recent max-flow min-cut type result for graphs of bounded treewidth. Multicommodity flow is a generalization of the well known s-t flow problem, where we are given multiple source-sink 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 source-sink pairs. We will show that given a treewidth-r graph, there exists a (fractional) multi-commodity flow of value F, and a multicut of capacity C such that F ≤ C ≤ O(log r)·F.
Friday, October 6, 2023 3:30 PM EDT
Title: Kissing Polytopes
| Speaker: | Antoine Deza |
| Affiliation: | McMaster University |
| Location: | MC 5501 |
Abstract: 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.
Friday, October 6, 2023 1:00 PM EDT
Title: Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
| Speaker: | Nikhil Kumar |
| Affilation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: I will present a recent max-flow min-cut type result for graphs of bounded treewidth. Multicommodity flow is a generalization of the well known s-t flow problem, where we are given multiple source-sink 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 source-sink pairs. We will show that given a treewidth-r graph, there exists a (fractional) multi-commodity flow of value F, and a multicut of capacity C such that F ≤ C ≤ O(log r)·F.
Thursday, October 5, 2023 3:00 PM EDT
Title: A closure lemma for tough graphs and Hamiltonian ideals
| Speaker: | Chinh T. Hoang |
| Affiliation: | Wilfrid Laurier University |
| Location: | MC 5417 |
Abstract: The closure of a graph $G$ is the graph $G^*$ obtained from $G$ by repeatedly adding edges between pairs of non-adjacent vertices whose degree sum is at least $n$, where $n$ is the number of vertices of $G$. The well-known 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.
Thursday, October 5, 2023 2:00 PM EDT
Title: Diagrammatic boundary calculus for Wilson loop diagrams
| Speaker: | Karen Yeats |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
There will be a pre-seminar 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 co-dimensions. 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.
Monday, October 2, 2023 11:30 AM EDT
Title: Neumaier graphs
| Speaker: | Maarten De Boeck |
| Affiliation: | University of Memphis |
| Location: | Please contact Sabrina Lato for Zoom link |
Abstract: A Neumaier graph is an edge-regular 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 so-called strictly Neumaier graphs.