Andreas Gördt -Technische Universität Chemnitz

Approximation algorithms on random structures

Abstract: It is one of the cores of the lore of random structures that random structures posess given properties with high probability. Sometimes, but not always the proofs come with an efficient algorithm to certify the property for a given random structure with high probability. For example in case of colouring properties one might produce a colouring in polynomial time.

We show some examples in which classical approximation algorithms can be used to the prescribed purpose. In particular we show how to certify non-k-colourability properties and unsatisfiability in the Not-All-Equal sense. These applications are relatively obvious.

Less obvious is the following application: We show that the classical unsatisfiability of 4-Sat instances with Cn^2 many random clauses can be certified efficiently. This improves a previous superquadratic bound obtained by a different method.

In all cases the approximation algorithms used are based on Max-cut approximation algorithms.

We discuss the open question whether the current bound for 3-Sat of n^{(3/2)+epsilon} random clauses can be similarly reduced to n^{3/2}.

Colloquium - 16 Uhr s.t.

Lingsheng Shi-Humboldt-Universität Berlin

Do Ramsey numbers grow polynomially for O(ln n)-degenerate graphs of order n?

Abstract: The Ramsey number of a graph G is the least integer n so that any graph of order n either contains a copy of G or its complement contains a copy of G. In 1973, Burr and Erdös offered a total of 25 $ for the conjecture that there is a constant c=c(d) so that the Ramsey number is at most cn for all d-degenerate graphs of order n. Here a graph is d-degenerate if its subgraphs all have minimum degree at most d. Recently, Kostochka and Rödl proved that the Ramsey number of any d-degenerate graph of order n with maximum degree Delta is bounded by cn Delta. If Delta is not restricted, this gives a polynomial bound for d-degenerate graphs of order n.

Shortly later, Kostochka and Sudakov improved this to the almost linear bound n^{1+o(1)}. It is also known that the Ramsey numbers grow at least polynomially for O(ln n)-degenerate graphs of order n. It would be interesting to decide whether there exists a polynomial upper bound as well. In the talk, I will show that this is indeed the case for bipartite O(ln n)-degenerate graphs of order n, by combining a combinatorial idea of Kostochka and Rödl as well as a probabilistic method of Kostochka and Sudakov.