On Ramsey property for random graphs.

Abstract

A graph G is Ramsey for a pair of graphs (F 1 , F 2 ) if in every 2-edge-colouring of G, one can find a monochromatic copy of F 1 with the first colour or a monochromatic copy of F 2 with the second colour. The binomial random graph G n,p is a subgraph of K n , the complete graph on n vertices, obtained by choosing each edge of K n independently at random with probability p to belong to G n,p . For a graph F, let m 2 (F) be the maximum of d 2 (F0) = (e(F0) − 1)/(v(F0) − 2) over all the subgraphs F0 ⊆ F with v(F0) ≥ 3. If this maximum is reached for F0 = F, then we say that F is 2-balanced. Furthermore, we say that F is strictly 2-balanced if d 2 (F) > d 2 (F0), for all proper subgraph F0 of F with v(F0) ≥ 3. For a pair of graphs (F 1 , F 2 ), let m 2 (F 1 , F 2 ) be the maximum of e(F01)/(v(F01) − 2 + 1/m 2 (F 2 )) over all the subgraphs F01⊆ F 1 with v(F01) ≥ 3. This dissertation aims to present a proof that for every pair of graphs (F 1 , F 2 ) such that F 1 is 2-balanced and m 2 (F 1 ) > m 2 (F 2 ) > 1 or F 1 is strictly 2-balanced and m 2 (F 1 ) ≥ m 2 (F 2 ) > 1, there exists a positive constant C for which asymptotically almost surely G n,p is Ramsey for the pair (F 1 , F 2 ), whenever that p ≥ Cn−1/m2(F1,F2). This result was conjectured by Kohayakawa and Kreuter in 1997 without the balancing condition over F1. The proof of the main theorem uses a recently developed technique known as hypergraph containers.