This week's seminar is given by our own Joannes Vermant, Umeå universitet.
Title: Sparsity, pebble games and posets
Abstract: There are various sparsity conditions which define matroids on graphs, hypergraphs or incidence geometries. Such conditions have applications in combinatorial geometry, as well as some classical interpretations in terms of disjoint spanning trees in graphs. An algorithm that recognises 2,3 sparsity, called the pebble game, was developed by Jackson and Hendrickson (1997). Later this was generalised to the k-plane matroid by Berg and Jordan (2003), to other parameters by Lee and Streinu (2008), to hypergraphs by Theran and Streinu (2009) and to general count matroids by Frank (2011). In ongoing work together with Signe Lundqvist, Tovohery Randrianarisoa and Klara Stokes, we consider pebble games on posets.
