Speaker:  Matija Bucic  (Princeton/IAS)

Title:  New Bounds Towards the Erdős-Gallai Cycle Decomposition Conjecture

Abstract: 

Graph decomposition questions make for some of the most fundamental and well-studied problems in extremal combinatorics with many interesting applications and connections. Some of the most classical instances of such questions, dating back over a hundred years, are concerned with decompositions into cycles. One of the most appealing, often repeated and well-studied conjectures in this direction, due to Erdős and Gallai from the 1960's, asserts that one can decompose any n-vertex graph into O(n) cycles and edges. We improve upon the previously best bound of O(n log log n) cycles and edges due to Conlon, Fox and Sudakov by showing that one can always decompose an n-vertex into O(nlog*n) cycles and edges.

Based on a joint work with Richard Montgomery.