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:
Friday, August 4, 2023 3:30 pm - 3:30 pm EDT (GMT -04:00)

Tutte Colloquium - Bill Jackson

Title: Rigidity of Simplicial Complexes

Speaker: Bill Jackson
Affiliation: Queen Mary University of London
Location: MC 5501

Abstract: A simplicial k-cycle is an abstract simplicial k-complex in which every (k-1)-face belongs to an even number of k-faces. A simplicial k-circuit is a minimal simplicial k-cycle (in the sense that none of its proper subcomplexes are simplicial k-cycles).

Thursday, August 10, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

Algebraic Combinatorics - Patricia Klein

Title: From the Upper Bound Conjecture to Gorenstein linkage

Speaker: Patricia Klein
Affiliation: Texas A&M
Location: MC 5501

Abstract: In 1957, Motzkin conjectured that the maximum number of faces possible for a polytope on n vertices in d-space is achieved by the convex hull of n points on the moment curve in d-space.  This conjecture, called the Upper Bound Conjecture, was proved by McMullen in 1970 and generalized by Stanley in 1975.  On the road to Stanley's proof, a correspondence between squarefree monomial ideals and simplicial complexes was born.  That correspondence is called the Stanley--Reisner correspondence.  It has come to occupy a central place in combinatorial algebraic geometry. 

Monday, August 14, 2023 2:30 pm - 2:30 pm EDT (GMT -04:00)

URA Seminar - URA Presentations

Title: URA Presentations

Speakers: Benjamin Wong, Rick Lyu, and Yen-Kang Fu
Affiliation: University of Waterloo
Location: MC 5479

Abstract: A series of presentations by a group of Spring 2023 Undergraduate Research Assistants. The topics of each presentation are detailed below.

Quantum Max-Cut on Bipartite Graphs - Benjamin Wong

Wednesday, August 23, 2023 11:30 am - 11:30 am EDT (GMT -04:00)

C&O Reading Group - Niv Buchbinder

Title: Chasing Positive Bodies

Speaker: Niv Buchbinder
Affiliation: Tel Aviv University
Location: MC 5417

Abstract: We study the problem of chasing positive bodies in \ell_1: given a sequence of bodies K_t\subset R^n revealed online, where each K_t is defined by a mixed packing-covering linear program, the goal is to (approximately) maintain a point x_t \in K_t such that \sum_t \|x_t - x_{t-1}\|_1 is minimized. This captures the fully-dynamic low-recourse variant of any problem that can be expressed as a mixed packing-covering linear program and thus also the fractional version of many central problems in dynamic algorithms such as set cover, load balancing, hyperedge orientation, minimum spanning tree, and matching.

Monday, August 28, 2023 11:30 am - 11:30 am EDT (GMT -04:00)

Algebraic Graph Theory - Dorian Smith

Title: Sandpile groups of cones over trees

Speaker: Dorian Smith
Affiliation: University of Minnesota Twin Cities
Location: Please contact Sabrina Lato for Zoom link

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. 

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

Algebraic Graph Theory - John S. Caughman

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.

Thursday, September 14, 2023 2:00 pm - 2:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics Seminar - Tianyi Yu

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.

Thursday, September 21, 2023 2:00 pm - 2:00 pm EDT (GMT -04:00)

Algebraic and Enumerative Combinatorics Seminar - Jeremy Chizewer

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.

Friday, September 22, 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

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.

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

Tutte Colloquium - Vida Dujmovic

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.