On January 13, 2022, Ron Aharoni from the Technion gave an online talk at the Virtual Discrete Math Colloquium on a stronger version of the Caccetta-Haggkvist conjecture and recent results. The title of his talk was “A strong version of the Caccetta-Haggkvist conjecture“.
Ron Aharoni, A strong version of the Caccetta-Haggkvist conjecture
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.
Ron Aharoni gave an online talk on the colorful version of the KKM theorem and a method of dividing multiple cakes at the Virtual Discrete Math Colloquium
On February 3, 2021, Ron Aharoni from the Technion gave an online talk at the Virtual Discrete Math Colloquium about the colorful version of the KKM theorem on topology and the problem of fairly partitioning multiple cakes. The title of his talk was “Colorful KKM and multiple cakes division“.
Photo by Marcus Quigmire from Wikipedia. CC BY-SA 2.0
Ron Aharoni, Colorful KKM and multiple cakes division
In the “cake partition” problem n players have each a list of preferred parts for any partition of the [0,1] interval (“cake”) into n sub-intervals. Woodall, Stromquist and Gale proved independently that under mild conditions on the list of preferences (like continuity) there is always a partition and assignment of parts to the players, in which every player gets a piece belonging to her list of preferred parts. In fact, Gale proved a colorful version of the famous KKM theorem, not realizing that this is the same problem, but on the other hand, proved the problem its proper setting. I will discuss the case of partitioning more than one cake – how many players can you make happy, when there is a general number of cakes, and general number of players.
Joint work with Eli Berger, Joseph Briggs, Erel Segal-Halevi and Shira Zerbib.