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

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 the Office of Indigenous Relations.