Events

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.

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.

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.