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. |
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. |