Alex Engström: Higher connectivity and expansion of fiber graphs of Gröbner bases
Alex Engström, Aalto University
Tid: On 2012-10-24 kl 10.15 - 12.00
Plats: Room 3733, Lindstedtsvägen 25, 7th floor, Department of mathematics, KTH
The Metropolis-Hastings algorithm is commonly employed to run random walks on graphs to estimate different statistics. Properties of the underlying graph will determine the efficiency of the algorithm. Diaconis and Sturmfels invented a method to use fiber graphs of Gröbner bases in this context. These graphs are connected, but more refined structural information is missing in general.
A graph is k-connected if you have to remove at least k vertices to disconnect it, and the minimal degree of a graph is an upper bound for the connectivity. I have conjectured that this bound is realized for large fiber graphs of reduced Gröbner bases, and I will discuss two results supporting the conjecture: The first is by my student Samu Potka, who has proven it for graphs from contingency tables. The second result is that large fiber graphs essentially have a huge part that is D/2-connected where D is the maximal degree. Maximal -- not minimal!
Anders Björner and Kathrin Vorwerk wrote a paper regarding the connectivity of chamber graphs in buildings, and we use some techniques from there.
I will also report on results on expansion properties of fiber graphs. These results are mostly negative and follow from hyperbolic geometry.