MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

An algorithmic framework for obtaining lower bounds for random Ramsey problems

Angelika Steger
ETH Zürich
AG1 Mittagsseminar (own work)
AG 1, MMCI  
AG Audience
English

Date, Time and Location

Wednesday, 17 December 2014
15:00
30 Minutes
E1 5
029
Saarbrücken

Abstract

In this talk we consider various versions of Ramsey-type questions in a random graph setting: the classical Ramsey problem, anti-Ramsey questions, Maker-Breaker games. It is easy to see that one should expect the same threshold (namely, the m2-density of the forbidden graph F) for all these problems. The aim of this talk is to provide a general framework for proving 0-statements and to then apply it to the three problems mentioned above. We also provide an extension to hypergraphs.

Contact

Karl Bringmann
--email hidden
passcode not visible
logged in users only

Karl Bringmann, 12/11/2014 21:10
Karl Bringmann, 10/28/2014 14:30 -- Created document.