June 22 , 2009
Humboldt-Universität zu Berlin
room 4.112
Institut für Informatik
Johann von Neumann-Haus,
Rudower Chaussee 25
Lecture - 14:15
Abstract:
We characterize the fundamental group of a locally finite graph $G$
with ends in two ways: combinatorially, as a group of infinite words,
and algebraically, as a subgroup in the inverse limit of the free
groups $\pi_1(G')$ with $G'\sub G$ finite. As an application, we can
now describe the topological cycle space of $G$ by a singular-type
homology theory that works for any locally compact Hausdorff space $X$
with a given compactification~$\hat X$. This homology assigns a
special role to the `boundary points' in $\hat X\setminus X$, similar
to the crucial role which the ends of a graph play in its topological
cycle space.
Colloquium - 16:00
Abstract:
A bramble in a graph is a set of connected subgraphs, such that each two of them touch. The order of a bramble is the minimum number of vertices needed to cover everey element of the bramble. Brambles were introduced by Robertson and Seymour in the Graph Minor Series and are the dual notion to treewidth: the maximum order of any bramble in a graph is equal to the treewidth of G plus 1. Marx and Grohe (2009) showed that if we are looking for a bramble of polynomial size, the best order we can hope for is the square-root of the treewidth. We present a polynomial time algorithm to compute a bramble in a graph of order square-root of the treewidth up to logarithmic factors. We use this algorithm to construct grid-like minors, as defined by Reed and Wood (2008), in polynomial time. Grid-like minors were introduced as a kind of replacement for grid-minors, a central notion in graph minor theory. They have the crucial property that their order is known to be polynomial in the treewidth (whereas for grid-minors this is not known). We apply the grid-like minors in two ways: (i) we define the notion of a perfect bramble and obtain a meta-theorem for many subgraph-closed graph properties; (ii) we use the algorithm for constructing grid-like minors to show that the model-checking problem for Monadic Second-Order Logic (MSO_2) is not fixed-parameter tractable on (colored) graph classes with polylogarithmic treewidth.
This is joint work with Stephan Kreutzer.