Monday, May 31, 3pm ET (8pm BST, 7am Tue NZST)
Daniel Slilaty, Wright State University
Orientations of golden-mean matroids

Abstract:

Tutte proved that a binary matroid is representable over some field of characteristic other than 2 if and only if the matroid is regular. His result inspired the discovery of analogs for $GF(3)$-representable matroids by Whittle, $GF(4)$-representable matroids by Vertigan as well as Pendavingh and Van Zwam, and $GF(5)$-representable matroids by Pendavingh and Van Zwam.

Bland and Las Vergnas proved that a binary matroid’s orientations correspond to its regular representations. (Minty’s result on digraphoids is closely related.) Lee and Scobee proved that a $GF(3)$-representable matroid’s orientations correspond to its dyadic representations. In this talk we will explore orientations of $GF(4)$-representable matroids. A natural partial field to use is the golden-mean partial field; however, not every orientation of a $GF(4)$-representable matroid comes from a golden-mean representation. For example, $U_{3,6}$ has 372 orientations but only 12 of them come from golden-mean representations. We will give a combinatorial characterization of those orientations of $GF(4)$-representable matroids which do come from golden-mean representations and show that these orientations correspond one-to-one to the golden-mean representations.

Joint work with Jakayla Robbins.

Monday, May 17, 3pm ET (8pm BST, 7am Tue NZST)
Bertrand Guenin, University of Waterloo
Graphs with the same even cycles

Abstract:

Monday, May 10, 3pm ET (8pm BST, 7am Tue NZST)
Sophie Spirkl, University of Waterloo
The complexity of list-5-colouring H-free graphs

Abstract:

A $k$-list-assignment for a graph $G$ is a function $L$ from $V(G)$ to subsets of $\{1, …, k\}$. The list-$k$-colouring problem asks, given $G$ and a $k$-list-assignment $L$, is there a colouring $f$ of $G$ with $f(v)$ in $L(v)$ for all $v$ in $V(G)$? This generalizes the $k$-colouring problem (where we use $L(v) = \{1, …, k\}$ for every vertex).

For $k$ at least $3$, both $k$-colouring and list-$k$-colouring are NP-hard, which motivates studying the complexity of these problems when the input is restricted to $H$-free graphs (for a fixed $H$, excluded as an induced subgraph).

I will present an algorithm for list-$5$-colouring restricted to $H$-free graphs for all $H$ which consist of connected components each of which is a $3$-vertex path. This, together with previous results, gives a complete answer to the question, “for which $H$ is list-$5$-colouring restricted to $H$-free graphs NP-hard?”

Joint work with Sepehr Hajebi and Yanjia Li.

Monday, April 19, 3pm ET (8pm BST, 7am Tue NZST)
Daniel Bernstein, MIT
Rigidity of symmetry-forced frameworks

Abstract:

The fundamental problem in rigidity theory is to determine whether a given immersion of a graph into $\mathbb{R}^d$ can be continuously deformed, treating the edges as rigid bars that can move freely about their incident vertices. Rigidity is a generic property of each fixed graph $G$, in the sense that almost all immersions of $G$ into $\mathbb{R}^d$ are rigid, or almost all immersions are flexible. The graphs that are generically rigid in $\mathbb{R}^d$ are the spanning sets of a certain matroid. The main result of my talk will be about rigidity in the plane when the graphs and their immersions have certain symmetry constraints.