Benny Sudakov-Princeton University

Dependent random choice and its applications to Ramsey and Turan type problems

Abstract: The Probabilistic Method is a powerful tool in tackling many problems in Combinatorics. It belongs to those areas of mathematics that have experienced a most impressive growth in recent years. Extremal Combinatorics is one of the branches of discrete mathematics where this approach has proved to be especially useful. In fact, many of the strongest results in this area in the last few decades are examples of this method.

In this talk we discuss a few recent applications of this method. In particular, we present simple but yet surprisingly powerful probabilistic arguments which were used recently to make progress on some long-standing Ramsey and Turan type problems.

Colloquium - 16 Uhr s.t.

Arnold Waßmer -Technische Universität Berlin

On the independence complexes of paths, trees, and cycles

Abstract: An independent set (or stable set) of a graph is a set of pairwise not adjacent nodes. To illustrate the family of independent sets of a graph one defines the independence complex: It is a simplicial complex with the nodes of the graph as its vertices. A set of vertices forms a simplex if it corresponds to an independent set in the graph.

But already some rather simple graphs have rather complicated independence complexes. For example the inclusion-maximal independent sets of a graph usually have different cardinalities: This happens already for the path with 5 nodes. In general it is NP-hard to find an independent set of maximal cardinality.

In this talk I will present for the cases of paths, trees and cycles, the construction of a better-behaved version of the independence complex. The vertices of this complex correspond to maximal independent sets of the graph. Its bigger cells correspond to certain smaller independent sets. If the graph is a path then this complex will be a nice cell decomposition of a sphere or a ball.