Extremal graph theory group

Programme


Past seminars

MONDAY 22.1.2018 at 10:00 ÚI, room 318: Viresh Patel (University of Amsterdam) Decomposing tournaments into paths

Abstract: In this talk we consider a generalisation of Kelly's conjecture which is due Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by K{\"u}hn and Osthus for all sufficiently large tournaments. The conjecture of Alspach, Mason, and Pullman concerns general tournaments and asks for the minimum number of paths needed in an edge decomposition of each tournament into paths. There is a natural lower bound for this number in terms of the degree sequence of the tournament and they conjecture this bound is correct for tournaments of even order.
Almost all cases of the conjecture are open and we prove many of them.
This is joint work with Allan Lo, Jozef Skokan, and John Talbot.

FRIDAY 5.1.2018 at 10:00 ÚI, room 318: Jan Volec (McGill) On degree thresholds of cycles in oriented graphs

Abstract: Motivated by Caccetta-Haggkvist conjecture, Kelly, Kuhn and Osthus initiated the study of minimum out-degree and semi-degree conditions that force an oriented graph to contain an oriented cycle of a given length. In particular, they proved for every l>=4 that if G is a sufficiently large n-vertex oriented graph with semi-degree > n/3, then G contains an oriented cycle of length l. It is easy to show that the bound is sharp for every l not divisible by 3. However, they conjectured that for l>=4 which is a multiple of 3, one can always do better. The smallest open case, which has drawn quite some attention and was a few times mentioned in open problem sessions by Kuhn and Osthus, is the one when l=6, i.e., the case of 6-cycles.
In this talk, we will mainly focus on the 6-cycle threshold and prove that if G is a sufficiently large n-vertex oriented graph with semi-degrees > n/4+1, then it contains an oriented 6-cycle. Since the natural lower-bound n/4 coming from a blow-up of oriented 4-cycle could be improved by one when n=4k+3, our lower-bound is best possible. We also determine the semi-degree thresholds for closed walks of length l for every l>=9 which is a multiple of 3, which provides an asymptotic solution to the conjecture of Kelly, Kuhn and Osthus.
This is a joint work with Roman Glebov and Andrzej Grzesik

seminars in 2017

seminars in 2016