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, September 29, 2023 3:30 PM EDT
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.
Friday, September 29, 2023 1:00 PM EDT
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.
Thursday, September 28, 2023 3:00 PM EDT
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.
Thursday, September 28, 2023 2:00 PM EDT
Title: Closure of Deodhar components
| Speaker: | Kartik Singh |
| 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: Deodhar decomposition of the Grassmannian is finest decomposition (that we know of) for which the components are homeomorphic to affine spaces. So, it's natural to be interested in their topology. In the talk we will try to describe a combinatorial rule that can possibly describe the closure of Deodhar decomposition. This work is joint with Olya Mandelshtam and Kevin Purbhoo.
Monday, September 25, 2023 11:30 AM EDT
Title: Quantum symmetries of Hadamard matrices
| Speaker: | Daniel Gromada |
| Affiliation: | Czech Technical University in Prague |
| Location: | Please contact Sabrina Lato for Zoom link |
Abstract: The main purpose of this talk is to explain the idea behind the main results of a recent article arXiv:2210.02047 about quantum symmetries of Hadamard matrices. First, we recall the notion of quantum symmetries from the viewpoint of quantum groups as well as diagrammatic categories. On the example of a finite (quantum) space, we show, how the diagrammatic approach can be used to prove that all finite spaces (of size at least four) have quantum symmetries and all finite quantum spaces of a given size are mutually quantum isomorphic. The same technique is used to show analogous results for Hadamard matrices. Finally, we would like to list a couple of questions and research suggestions related to this topic.
Friday, September 22, 2023 3:30 PM EDT
Title: Proof of the Clustered Hadwiger Conjecture
| Speaker: | Vida Dujmovic |
| Affiliation: | University of Ottawa |
| Location: | MC 5501 |
Abstract: Hadwiger's Conjecture asserts that every Kh-minor-free graph is properly (h-1)-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every Kh-minor-free graph is (h-1)-colourable with monochromatic components of bounded size.
Friday, September 22, 2023 1:00 PM EDT
Title: A Fast Combinatorial Algorithm for the Bilevel Knapsack Problem with Interdiction Constraints
| 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. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments for 99% of the instances reported in the literature.
Thursday, September 21, 2023 2:00 PM EDT
Title: The Sunflower Problem: Restricted Intersections
| Speaker: | Jeremy Chizewer |
| 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: A sunflower with $r$ petals is a collection of $r$ sets over a ground set $X$ such that every element in $X$ is in no set, every set, or exactly one set. Erdos and Rado showed that a family of sets of size $n$ contains a sunflower if there are more than $n!(r-1)^n$ sets in the family. Alweiss et al. and subsequently Rao and Bell et al. improved this bound to $(O(r \log(n))^n$.
In this talk, I will discuss the sunflower problem with an additional restriction, a bound on the size of pairwise intersections in the set family. In particular, I will show an improved bound for set families when the size of the pairwise intersections of any two sets is in a set $L$. This talk is based on https://arxiv.org/abs/2307.01374.
Thursday, September 14, 2023 2:00 PM EDT
Title: Analogue of Fomin-Stanley algebra on bumpless pipedreams
| Speaker: | Tianyi Yu |
| Affiliation: | University of California |
| Location: | MC 6029 |
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:00 pm.
Abstract: Schubert polynomials are distinguished representatives of Schubert cells in the cohomology of the flag variety. Pipedreams (PD) and bumpless pipedreams (BPD) are two combinatorial models of Schubert polynomials. There are many classical perspectives to view PDs: Fomin and Stanley represented each PD as an element in the NilCoexter algebra; Lenart and Sottile converted each PD into a labeled chain in the Bruhat order. In this talk, we unravel the BPD analogues of both viewpoints.
One application of our results is a simple bijection between PDs and BPDs via Lenart's growth diagram.
Monday, September 11, 2023 11:30 AM EDT
Title: Parameter constraints for distance-regular graphs that afford spin models
| Speaker: | John S. Caughman |
| Affiliation: | Portland State University |
| Location: | Please contact Sabrina Lato for Zoom link |
Abstract: In 1990, Vaughn Jones introduced a link invariant constructed using matrices known as spin models. In 1996, Francois Jaeger discovered that spin model matrices are contained in the Bose-Mesner algebra of an association scheme. Since many examples of association schemes arise from distance-regular graphs, it is natural to ask which distance-regular graphs afford a spin model.