Seminar series
Date
Tue, 24 May 2022
Time
14:00 -
15:00
Location
L3
Speaker
Nemanja Draganić
Organisation
ETH Zurich
The size-Ramsey number ˆr(H) of a graph H is the smallest number of edges a (host) graph G can have, such that for any red/blue coloring of G, there is a monochromatic copy of H in G. Recently, Conlon, Nenadov and Trujić showed that if H is a graph on n vertices and maximum degree three, then ˆr(H)=O(n8/5), improving upon the bound of n5/3+o(1) by Kohayakawa, Rödl, Schacht and Szemerédi. In our paper, we show that ˆr(H)≤n3/2+o(1). While the previously used host graphs were vanilla binomial random graphs, we prove our result by using a novel host graph construction.
We also discuss why our bound is a natural barrier for the existing methods.
This is joint work with Kalina Petrova.