Tag: RonAharoni

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.

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.