Partitioning a tournament into sub-tournaments of high connectivity

Organizer

Benjamin Sudakov

Speaker

Antonio Girao

Time

Tuesday, February 20, 2024 5:05 PM - 6:15 PM

Venue

Online

Zoom 787 662 9899 (BIMSA)

Abstract

A classical result of Hajnal and Thomassen asserts that for every$k$ there exists $K$ such that the vertices of every $K$-connected graph can be partitioned into two sets inducing $k$-connected subgraphs. Moreover they showed $K=O(k)$. There is now a whole area of combinatorial problems concerned with questions of this type; namely, to understand whether for a certain (di)graph property any (di)graph which $\textit{strongly}$ satisfies that property has a vertex-partition into many parts where each part still has the property. K\"uhn, Osthus and Townsend proved the analogous result of Hajnal and Thomassen but in the tournament setting. More precisely, they showed that every tournament which is $f(k,t)$-strongly-connected can be partitioned into $t$ parts such that each part is $k$-strongly connected. In this talk, we will discuss a recent result jointly with Shoham Letzter where we show $f(k,t)=O(kt)$ which is best possible and resolves a conjecture of the said authors. Short bio: Antonio Girao obtained his PhD at Cambridge under the supervision of Bela Bollobas. He has since then been a postdoc working with Daniela Kuhn and Deryk Osthus at Birmingham, with Felix Joos at Heidelberg and currently he is based at Oxford working with Alex Scott and Peter Keevash. His research is focused on extremal and probabilistic combinatorics, Ramsey theory and random graphs.