Loading Events

« All Events

  • This event has passed.

Ron Aharoni, A strong version of the Caccetta-Haggkvist conjecture

Thursday, January 13, 2022 @ 4:30 PM - 5:30 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)


Ron Aharoni
Department of Mathematics, Technion

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.


Thursday, January 13, 2022
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:


Zoom ID: 869 4632 6610 (ibsdimag)


O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.