| [home] - [up] |
Abstract: The classical infinite Ramsey theorem, every infinite graph either has an infinite clique or an infinite independent subset, cannot be generalized to higher cardinals: Sierpinski noticed that there is a graph on the set of real numbers whose cliques and independent subsets are at most countable.
The situation is getting better once we restrict ourselves to clopen graphs on topological spaces that are close to the real line (namely to Polish spaces, i.e., separable complete metric spaces) However, the classical Ramsey invariants of graphs, the maximal size of a clique or the maximal size of an independent subset, are not very interesting in this situation. As it turns out, the right invariant to study is the least size of a family consisting of cliques and indepent subsets that covers the whole graph.
The analysis of this cardinal invariant involves meta-mathematics (independence results in set theory) and a new Ramsey type theorem by Noga Alon about finite perfect graphs. As an application one obtains a (meta-mathematical) classification of closed sets in the Euclidean plane that cannot be covered by countably many of its of convex subsets.
Colloquium - 16:00
Abstract: Given a rectilinear polygon P, possibly with holes, we would like to cover P with a minimal number of axis-parallel rectangles. Thinking of P as a set of discrete pixels, we are looking for a smallest cardinality set of rectangles, the union of which is exactly the set of pixels.
Even though (or because) this classical problem can be stated so easily, it defied several attacks by a prominent list of researchers. The problem is known to be NP-hard, and the existence of a constant factor approximation algorithm is a big open question.
The dual problem is to find a largest cardinality set of pixels, no two of which can be simultaneously covered by any rectangle. The cardinality of such a stable set clearly gives a lower bound on the size of an optimal rectangle cover. It has been the typical tool to devise (non-constant factor) approximation algorithms.
In this colloquium, we provide some evidence, also with data sets from practical applications, that the problem is extremely well-behaved from a computational point of view. Secondly, we sketch our ongoing attempts to obtain a constant factor approximation using a fractional stable set as a lower bound in an LP duality based approach. (co-author: Laura Heinrich-Litan)