Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, September 17, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Miloš Trujić
A seminal result of Rödl and Ruciński from 1995 states that for every fixed graph H a random graph G(n, p) is w.h.p. such that every 2-colouring of its edges contains a monochromatic copy of H in one of the two colours, provided that p >> n^(-1/m_2(H)), where the value m_2(H) is a certain (natural) density parameter of the graph H. We extend this theorem to all 'large' graphs H with maximum degree three. Namely, there is a b > 0 and a C > 0 for which w.h.p. a random graph G(n, p) is such that every 2-colouring of its edges contains a monochromatic copy of every graph H with b*n vertices and maximum degree at most three, provided that p >= Cn^(-2/5). The value 2/5 in the density p is optimal, which stems from the Rödl-Ruciński theorem. The statement has immediate consequences for the size-Ramsey numbers of large graphs, improving a result of Kohayakawa, Rödl, Schacht, and Szemerédi. This is a joint work with David Conlon and Rajko Nenadov.
Automatic MiSe System Software Version 1.4803M | admin login