Campus Event Calendar
Event Entry
What and Who
Upper bounds for asymmetric Ramsey properties of random graphs
Reto Spöhel
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 6 March 2012
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
Consider the following problem: Is there a coloring of the edges of the random graph $G_{n,p}$ with two colors such that there is no monochromatic copy of some fixed graph $F$? A celebrated result by Rödl and Rucinski (1995) states a general threshold function $p_0(F,n)$ for the existence of such a coloring. Kohayakawa and Kreuter (1997) conjectured a general threshold function for the asymmetric case (where different graphs $F_1$ and $F_2$ are forbidden in the two colors), and verified this conjecture for the case where both graphs are cycles.
Implicit in their work is the following more general statement: The conjectured threshold function is an upper bound on the actual threshold provided that i) the two graphs satisfy some balancedness condition, and ii) the so-called K{\L}R-Conjecture is true for the sparser of the two graphs. We present a new upper bound proof that does not depend on the K{\L}R-Conjecture. Together with earlier lower bound results [Marciniszyn, Skokan, S., Steger (2006)], this yields in particular a full proof of the Kohayakawa-Kreuter conjecture for the case where both graphs are cliques.
Joint work with Yoshiharu Kohayakawa (Sao Paulo) and Mathias Schacht (Hamburg).
Contact
Reto Spöhel
--email hidden
passcode not visible
logged in users only
Reto Spöhel, 03/02/2012 13:58 -- Created document.