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

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.