Events

Filters
Export this event to calendar
iCal
RSS
RSS
Close X

Filter by:

Limit to events where the title matches:
Limit to events where the first date of the event:
Date range
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, March 6, 2026 3:30 pm - 4:30 pm EST (GMT -05:00)

Tutte Colloquium -Kathie Cameron-Reconfiguration of Vertex Colourings

Speaker: Kathie Cameron
Affiliation: Wilfrid Laurier University
Location: MC 5011

Abstract: A k-colouring of a graph is an assignment of at most k colours to its vertices so that the ends of each edge get different colours. We consider two types of “reconfiguration steps” for transforming a given k-colouring into a target k-colouring. The first is to change the colour of a vertex to a colour which does not appear on any of the vertices it is adjacent to. We say that a graph G is recolourable if for every k greater than its chromatic number, any k-colouring of G can be transformed into any other by these reconfiguration steps. The second (more general) type of reconfiguration step is Kempe swaps. We call a graph Kempe connected if for every k, any k-colouring can be transformed into any other by Kempe swaps.

We have characterized the graphs H such that all graphs which don’t contain H as an induced subgraph are recolourable, and done the same for Kempe connectedness. We have shown that modular decomposition and a stronger version of clique cutsets can be used to show that certain classes are recolourable. We also give some classes of graphs which admit colourings that are “frozen” with respect to these reconfiguration steps.
This is joint work with Manoj Belavadi and parts are also joint with Elias Hildred, Owen Merkel and Dewi Sintiari.
Monday, March 9, 2026 2:45 pm - 3:45 pm EDT (GMT -04:00)

Graphs and Matroids - Taite LaGrange-Classes of graphs with sub-linear twin-width

Speaker: Taite LaGrange
Affiliation: University of Waterloo
Room: MC 5479

Abstract:Twin-width is a graph and matrix parameter introduced in 2021 by Bonnet, Kim, Thomassé, and Watrigant as essentially a measure of the 'error' between vertex neighbourhoods over a series of vertex contractions. This talk covers some graph classes with unbounded twin-width. We present a tool for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods. For a graph G on n vertices, we show that if such a partition exists, then the twin-width of G is at worst sub-linear with respect to n. We use this to obtain an upper bound on the twin-width of interval graphs and of graphs with bounded VC dimension. The latter implies that hereditary classes have sub-linear twin-width if and only if they have bounded VC dimension.

Friday, March 13, 2026 3:30 pm - 4:30 pm EDT (GMT -04:00)

Tutte Colloquium -Seunghoon Lee-Parallel Reversible Pebbling: Time-Space Tradeoffs on DAGs (with Cryptographic Motivation)

Speaker: Seunghoon Lee
Affiliation: University of Waterloo
Location: MC 5011

Abstract: The (parallel) pebbling game is a useful abstraction for analyzing the resources (e.g., space, space-time, amortized space-time) needed to evaluate a function f with a static data-dependency graph G on a (parallel) computer. The underlying question is purely combinatorial: what tradeoffs does a directed acyclic graph (DAG) force between storing intermediate values and recomputing them? This viewpoint has been particularly influential in cryptography, where many “Memory-Hard Function” (MHF) constructions can be modeled by evaluating a fixed DAG.

Classical pebbling, however, does not capture an essential constraint in quantum/reversible computation: intermediate information cannot be discarded freely, so cleanup must respect the dependency structure. While sequential reversible pebbling has been used to study space-time tradeoffs in sequential settings, it does not reflect the space-time tradeoffs for parallel quantum/reversible algorithms. To model this, we introduce the parallel reversible pebbling game and use it to analyze reversible space-time and amortized costs for important graph families, including line graphs and structured DAGs arising in MHF constructions (e.g., Argon2i and DRSample).
The talk highlights two core results: First, we give a lower bound on the reversible amortized space-time cost for a line graph, which yields a separation between classical and reversible pebbling costs, showing a super-constant (yet sub-polynomial) gap. Second, this overhead is nevertheless controlled: we show that any classical parallel pebbling can be transformed into a reversible one with only a sub-polynomial loss. This generic transformation serves as a central tool for analyzing broader graph families.
The talk will focus on the combinatorial aspects of cryptographic applications; no background in cryptography is assumed. Based on joint work with Jeremiah Blocki and Blake Holman: The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs (TCC 2022), and The Impact of Reversibility on Parallel Pebbling (EUROCRYPT 2025).
Thursday, March 19, 2026 2:30 pm - 3:30 pm EDT (GMT -04:00)

Algebraic and enumerative combinatorics seminar - Moriah Elkin- Open quiver loci, CSM classes, and chained generic pipe dreams

Speaker: Moriah Elkin
Affiliation: Cornell University
Location: MC 5417

Abstract: In the space of type A quiver representations, putting rank conditions on the maps cuts out subvarieties called "open quiver loci." These subvarieties are closed under the group action that changes bases in the vector spaces, so their closures define classes in equivariant cohomology, called "quiver polynomials." Knutson, Miller, and Shimozono found a pipe dream formula to compute these polynomials in 2006. To study the geometry of the open quiver loci themselves, we might instead compute "equivariant Chern-Schwartz-MacPherson classes," which interpolate between cohomology classes and Euler characteristic. I will introduce objects called "chained generic pipe dreams" that allow us to compute these CSM classes combinatorially, and along the way give streamlined formulas for quiver polynomials.

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