Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, October 11, 2018, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Rajko Nenadov

Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties

We say that a graph G is Ramsey for graphs F₁, F₂, ..., F_r if in every colouring of the edges of G with colours {1,...,r} there exists a copy of F_i in G which is completely in colour i, for some i. It is well-known that if G is a complete graph on n vertices, for a sufficiently large n depending on F_i's, then G is Ramsey for given graphs. In this talk we consider the threshold probability p for which G = G(n,p), a binomial random graph, has such a Ramsey property.

The case where F₁ = F₂ = ... = F_r =: F, the so-called symmetric case, was completely resolved in a series of papers by Rödl and Ruciński in the '90s. It turns out that here the threshold coincides with the property that every edge of G(n,p) belongs to many copies of F, and moreover that it can take a role of any edge of F. Soon after, a conjecture of what the threshold should be in the general case was formulated by Kohayakawa and Kreuter. Apart from some special cases such as when F_i's are cycles or complete graphs, it is still wide open. We prove that the 1-statement holds, that is, the threshold is upper bounded by the conjectured value of Kohayakawa and Kreuter.

This is joint work with Frank Mousset and Wojciech Samotij.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login