Events

Filter by:

Limit to events where the first date of the event:
Date range
Limit to events where the first date of the event:
Limit to events where the title matches:
Limit to events where the type is one or more of:
Limit to events tagged with one or more of:
Limit to events where the audience is one or more of:
Thursday, September 28, 2023 3:00 pm - 3:00 pm EDT (GMT -04:00)

Graphs and Matroids Seminar - Jim Geelen

Title: Structure in minor-closed classes of matroids

Speaker: Jim Geelen
Affiliation: University of Waterloo
Location: MC 5417

Abstract: I will give a brief overview of the structure of matroids in minor-closed classes representable over a fixed finite field. Then I will discuss open problems related to extending those results to more general minor-closed classes of matroids.

Friday, September 29, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

C&O Reading Group - Noah Weninger

Title: A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints, Part II

Speaker: Noah Weninger
Affiliation: University of Waterloo
Location: MC 6029

Abstract: We consider the bilevel knapsack problem with interdiction constraints, a generalization of 0-1 knapsack. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack (i.e. interdict) such that the maximum profit attainable from packing the remaining items into the second knapsack is minimized.

Friday, September 29, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Nikhil Kumar

Title: An Approximate Generalization of the Okamura-Seymour Theorem

Speaker: Nikhil Kumar
Affiliation: University of Waterloo
Location: MC 5501

Abstract: We consider the problem of multicommodity flows in planar graphs. Okamura and Seymour showed that if all the demands are incident on one face, then the cut-condition is sufficient for routing demands.

Monday, October 2, 2023 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory - Maarten De Boeck

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.

Thursday, October 5, 2023 2:00 pm - 2:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics Seminar - Karen Yeats

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.

Thursday, October 5, 2023 3:00 pm - 3:00 pm EDT (GMT -04:00)

Graphs and Matroids Seminar - Chinh T. Hoang

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.

Friday, October 6, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

C&O Reading Group - Nikhil Kumar

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.

Friday, October 6, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Antoine Deza

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 13, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

C&O Reading Group - Nikhil Kumar

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.

Monday, October 16, 2023 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory - Sooyeong Kim

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.