Essentially Tight Bounds for Rainbow Cycles in Proper Edge-Colourings

Start Date: March 18, 2024
Event Start Time: 2:00 PM
Event End Time: 3:00 PM
Seminar Series: Rutgers Discrete Mathematics Seminar
Presenter(s): Matija Bucic - Princeton University and Institute for Advanced Study
Event Location: Conference Room 705 | Rutgers University | Hill Center | 110 Frelinghuysen Rd
Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
Presentation Type: Stand Alone Presentation
Abstract:
An edge-coloured graph is said to be rainbow if it uses no colour more than once. Extremal problems involving rainbow objects have been a focus of much research as they capture the essence of a number of interesting problems in a variety of areas. A particularly intensively studied question due to Keevash, Mubayi, Sudakov and Verstraëte from 2007 asks for the maximum possible 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 this question. 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)).

Joint work with: Noga Alon, Lisa Sauermann, Dmitrii Zakharov and Or Zamir.

Events