Events by month

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.