Monday, February 22, 3pm ET (8pm GMT, 9am Tue NZDT)
Geoff Whittle, Victoria University of Wellington
Monotone orders of connectivity functions
(Joint with Jasmine Hall and Susan Jowett)
A connectivity function is a symmetric submodular set function. Branch width of graphs, carving width of graphs, and branch width of matroids are all determined by connectivity functions associated with vertex connectivity in graphs, edge connectivity in graphs and connectivity in matroids respectively. A natural problem is to bound the size of structures that are “minimal” with respect to having a given branch width, where what is meant by minimal depends on the notion of substructure that one has in mind. In the talk I will discuss a general theorem on connectivity functions that gives sufficient conditions to bound the size of such minimal structures in a variety of situations.