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, October 4, 2024 12:30 pm - 1:30 pm EDT (GMT -04:00)

C&O Reading Group - Rian Neogi

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 6029

Abstract: In this talk, we will cover the paper of Svensson and Tarnawski that shows that perfect matching in general (non-bipartite) graphs in is quasi-NC. Similar to the work of Fenner, Gurjar and Thierauf (covered earlier in the reading group), the approach is to derandomize the isolation lemma for the perfect matching polytope by applying weight functions to iteratively restrict to subfaces of the polytope. However, the perfect matching polytope in general graphs is not as well-structured as it is in bipartite graphs. The faces of the polytope no longer correspond to subgraphs and now involve additional tight odd set constraints that need to be dealt with. This makes it so that a cycle with non-zero circulation may still exist in the support of the new face. Additionally, the existence of odd cycles in the graph breaks the cycle counting argument used in the paper of Fenner, Gurjar, Thierauf. We will see how Svensson and Tarnawski deal with these issues in the talk.

Friday, October 4, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte colloquium-Debbie Leung

Title: Purifying arbitrarily noisy quantum states

Speaker: Debbie Leung
Affiliation: University of Waterloo
Location: MC 5501

Abstract: Quantum state purification is the task of recovering a nearly pure copy of an unknown pure quantum state using multiple noisy copies of the state. We derive an efficient purification procedure based on the swap test for qudits of any dimension, starting with any initial error parameter. For constant initial error parameter and dimension, our procedure has sample complexity asymptotically optimal in the final error parameter, and almost matches the known optimal protocol for qubits. Our protocol has a simple recursive structure that can be applied when the states are provided one at a time in a streaming fashion, requiring only a small quantum memory to implement.  Joint work with Andrew Childs, Honghao Fu, Zhi Li, Maris Ozols, Vedang Vyas. 

 

Monday, October 7, 2024 11:30 am - 12:30 pm EDT (GMT -04:00)

Algebraic Graph Theory-Chris Godsil

Title: Constructing cospectral graphs - a ``Prehistory’'

Speaker: Chris Godsil
Affiliation: University of Waterloo
Location: Please contact Sabrina Lato for Zoom link.

Abstract: I will present some old constructions of cospectral graphs, due Brendan McKay and myself. I will also describe how we found some of these.

Tuesday, October 8, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Graphs and Matroids - Matthew Kroeker

Title: Unavoidable flats in matroids representable over a finite field

Speaker: Matthew Kroeker
Affiliation: University of Waterloo
Location: MC 5417

Abstract: For a positive integer k and finite field F, we prove that every simple F-representable matroid with sufficiently high rank has a rank-k flat which either is independent, or is a projective or affine geometry over a subfield of F.  As a corollary, we obtain the following Ramsey theorem: given an F-representable matroid of sufficiently high rank and any 2-colouring of its points,  there is a monochromatic rank-k flat.  This is joint work with Jim Geelen and Peter Nelson. 

Thursday, October 10, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Algebraic and enumerative combinatorics seminar-Joshua Swanson

Title: Cyclotomic generating functions

Speaker: Joshua Swanson
Affiliation: University of Southern California
Location: MC 5479

Abstract: It is a remarkable fact that for many statistics on finite sets of combinatorial objects, the roots of the corresponding generating function are each either a complex root of unity or zero. These and related polynomials have been studied for many years by a variety of authors from the fields of combinatorics, representation theory, probability, number theory, and commutative algebra. We call such polynomials *cyclotomic generating functions* (CGFs). We will review some of the many known examples and give results to classify the asymptotic behavior of their coefficient sequences in certain regimes.

Joint work with Sara Billey.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.

Friday, October 11, 2024 12:30 pm - 1:30 pm EDT (GMT -04:00)

C&O Reading Group - Rian Neogi Part 2

Speaker: Rian Neogi
Affiliation: University of Waterloo
Location: MC 6029

Abstract: In this talk, we will cover the paper of Svensson and Tarnawski that shows that perfect matching in general (non-bipartite) graphs in is quasi-NC. Similar to the work of Fenner, Gurjar and Thierauf (covered earlier in the reading group), the approach is to derandomize the isolation lemma for the perfect matching polytope by applying weight functions to iteratively restrict to subfaces of the polytope. However, the perfect matching polytope in general graphs is not as well-structured as it is in bipartite graphs. The faces of the polytope no longer correspond to subgraphs and now involve additional tight odd set constraints that need to be dealt with. This makes it so that a cycle with non-zero circulation may still exist in the support of the new face. Additionally, the existence of odd cycles in the graph breaks the cycle counting argument used in the paper of Fenner, Gurjar, Thierauf. We will see how Svensson and Tarnawski deal with these issues in the talk.

Friday, October 11, 2024 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte colloquium-Jessica Striker

Title: Rotation-invariant web bases from hourglass plabic graphs and symmetrized six-vertex configurations

Speaker: Jessica Striker
Affiliation: North Dakota State University
Location: MC 5501

Abstract: Many combinatorial objects with strikingly good enumerative formulae also have remarkable dynamical behavior and underlying algebraic structure. In this talk, we consider the promotion action on certain rectangular tableaux and explain its small, predictable order by reinterpreting promotion as a rotation in disguise. We show how the search for this visual explanation of combinatorial dynamics led to the solution of an algebraic problem involving web bases and a generalization of the six-vertex model of statistical physics. We find that this framework includes several unexpected combinatorial objects of interest: alternating sign matrices, plane partitions, and their symmetry classes (joint with Ashleigh Adams). This talk is based primarily on joint work with Christian Gaetz, Stephan Pfannerer, Oliver Pechenik, and Joshua P. Swanson.

 

Tuesday, October 15, 2024 2:00 pm - 3:00 pm EDT (GMT -04:00)

Algebraic and enumerative combinatorics seminar-Christian Gaetz

Title: Hypercube decompositions and combinatorial invariance for Kazhdan-Lusztig polynomials

Speaker: Christian Gaetz
Affiliation: UC Berkeley
Location: MC 5501

Abstract: Kazhdan-Lusztig polynomials are of foundational importance in geometric representation theory. Yet the Combinatorial Invariance Conjecture, due to Lusztig and to Dyer, suggests that they only depend on the combinatorics of Bruhat order. I'll describe joint work with Grant Barkley in which we adapt the hypercube decompositions introduced by Blundell-Buesing-Davies-Veličković-Williamson to prove this conjecture for Kazhdan-Lusztig R-polynomials in the case of elementary intervals in the symmetric group. This significantly generalizes the main previously known case of the conjecture, that of lower intervals.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm.