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
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.