- This event has passed.
Ron Aharoni, A strong version of the Caccetta-Haggkvist conjecture
January 13 Thursday @ 4:30 PM - 5:30 PM KST
The Caccetta-Haggkvist conjecture, one of the best known in graph theory, is that in a digraph with $n$ vertices in which all outdegrees are at least $n/k$ there is a directed cycle of length at most $k$. This is known for large values of $k$, relatively to n, and asymptotically for n large. A few years ago I offered a generalization: given sets $F_1$, $\ldots$, $F_n$ of sets of undirected edges, each of size at least $n/k$, there exists a rainbow undirected cycle of length at most $k$. The directed version is obtained by taking as $F_i$ the set of edges going out of the vertex $v_i$ ($i \le n$), with the directions removed. I will tell about recent results on this conjecture, obtained together with He Guo, with Beger, Chudnovsky and Zerbib, and with DeVos and Holzman.