Lectures and Colloquia during the semester

**July 16, 2001**

Humboldt-Universität zu Berlin

Rudower Chaussee 5, 12489 Berlin

Room 3.101

** Lecture - 14:15**

### Jeong Han Kim - Microsoft Research

### Survey on the nibble method

*Abstract:*
Probabilistic methods have recently become a very powerful tool in
extremal graph theory. The methods are useful in proving existence
of combinatorial structures satisfying certain properties.
Typically, one constructs an appropriate probability space and
proves that a randomly chosen object (in the probability space)
satisfies the desired properties with positive probability.
The nibble (or semi-random) method comprises one approach that has
attracted
much attention for its flexibility of construction. While the
random greedy method usually constructs the desired object
(independent set, matching, coloring, etc.) one by one, the
nibble method constructs it in small random increments, which
makes analysis easier. The method has been used to settle nice
extremal graph theory problems related to partial Steiner systems,
hypergraph matchings and colorings, chromatic numbers of triangle-free
graphs,
and Ramsey number *R(3,t)*. In this talk, which will be
self-contained, we will describe the method and its application
to the extremal graph theory problems.

** Colloquium - 16:00**

### Martin Thimm - Humboldt-Universität zu Berlin

### On the Approximability of the Steiner Tree Problem

*Abstract:*
Suppose that we are given a graph, a metric given by edge weights
and a set *T* of required vertices called
* terminals*. The * minimum Steiner tree problem* consists of finding a
tree of minimum weight that spans all vertices in *T*.
We show that it is *NP*-hard to approximate the minimum Steiner tree problem
within *frac{136}{135}*. This improves the currently best known lower bound
by a factor of three.
The reduction is from H\aa stad's nonapproximability result for
maximum satisfiability of linear equations modulo *2*. The improvement
on the nonapproximability ratio is mainly based on the fact that
our reduction does not use variable gadgets. This idea was introduced by
Papadimitriou an Vempala.

[top]