AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

The standard randomization of Ramsey’s theorem asks for a fixed graph F and a fixed number r of colors: for what densities p = p(n) can we asymptotically almost surely color the edges of the random graph G(n, p) with r colors without creating a monochromatic copy of F. This question was solved in full generality by Rödl and Rucinski (1993,1995). In this talk we consider a different randomization that was recently suggested by Allen et al. Let R_F(n, q) be a random subset of all copies of F on a vertex set V_n of size n, in which every copy is present independently with probability q. For which functions q = q(n) can we color the edges of the complete graph on V_n with r colors such that no monochromatic copy of F is contained in R_F(n, q)? We answer this question for strictly 2-balanced graphs F. Even more, we can combine both sources of randomness and prove a threshold result for the property that there exists an r-edge-coloring of G(n, p) such that no monochromatic copy of F is contained in R_F(n, q).

Reto Spöhel

--email hidden

passcode not visible

logged in users only