Essentially tight bounds for rainbow cycles in proper edge-colourings

Abstract

An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremalproblems involving rainbow objects have been a focus of much research as they capture theessence of a number of interesting problems in a variety of areas. A particularly intensively studiedguestion due to Keevash, Mubayi, Sudakov and Verstrate from 2007 asks for the maximumpossible average degree of a properly edge-coloured graph on n vertices without a rainbow cycle.Improving upon a series of earlier bounds, Tomon proved an upper bound of (log n)(2+o(1)) for thisguestion. Very recently, Janzer-Sudakov and Kim-Lee-Liu-Tran independently removed the o(1)term in Tomon's bound. We show that the answer to the question is equal to (log n)(1+o(1)). Jointwork with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.

Speaker Intro

Matia Bucic is an Assistant professor in Mathematics at Princeton University. Before his currentposition, he studied at the University of Cambridge, received his PhD from ETH Zurich, and held aVeblen Research Instructorship, a joint position between lAS and Princeton. His research focuseson extremal and probabilistic combinatorics, as well as their applications to other areas ofcombinatorics and computer science.