Events

Title: Sandpile groups of cones over trees

Abstract: The sandpile group  K(G) of a graph G is a finite abelian group, isomorphic to the cokernel of the reduced graph Laplacian of G. We study K(G) when G = Cone(T) is obtained from a tree T on n vertices by attaching a new cone vertex attached to all other vertices. For two such families of graphs, we will describe K(G) exactly: the fan graphs Cone(P_n) where  P_n is a path, and the thagomizer graph Cone(S_n) where S_n is the star-shaped tree. The motivation is that these two families turn out to be extreme cases among Cone(T) for all trees T on n vertices. 

Title: Parameter constraints for distance-regular graphs that afford spin models

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

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

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

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

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

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

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

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

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.