Leírás
Kedves Kommbinatorikusok!
Május 19-én 14:15-kor Abhishek Methuku (Zurich) ad elő zoomon, a nagyteremben kivetítve
Edge-disjoint cycles with the same vertex set
címmel
Abstract:
In 1975, Erdős asked for the maximum number of edges that an
n-vertex graph can have if it does not contain two edge-disjoint
cycles on the same vertex set. This problem has since been
reiterated by several authors in various contexts, including Bollobás in 1978in
his popular book _Extremal Graph Theory,_ Pyber, Rödl, and Szemerédi
in 1995, and Chen, Erdős, and Staton in 1996.
We asymptotically resolve this problem in a strong form, by showing
that, for any given k the maximum number of edges in an n-vertex graph
not containing k edge-disjoint cycles on the same vertex set is n^{1+o(1)}.
Our proof combines a variety of techniques including sublinear
expanders, absorption and a novel tool for regularisation, which is of
independent interest. Among other applications, this tool can be used
to regularise an expander while still preserving certain key expansion
properties. Joint work with Debsoumya Chakraborti, Oliver Janzer and
Richard Montgomery.
Zoom:
Mindenkit szeretettel várunk