printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

math 269 - combinatorics seminar

dr. he guo

technion - israel institute of technology

non-uniform degrees and rainbow versions of the caccetta-häggkvist conjecture

abstract:

the famous caccetta-häggkvist conjecture states that for any $n$-vertex directed graph $d$, the directed girth of $d$ (the minimum length of a directed cycle in $d$) is at most $\lceil n/k \rceil$, where $k$ is the minimum out-degree of $d$. aharoni raised a strengthening conjecture: for any $n$-vertex graph $g$ equipped with an edge coloring (not necessarily proper) using $n$ colors, the rainbow girth of $g$ (the minimum length of a cycle in $g$ with distinctly colored edges) is at most $\lceil n/k \rceil$, where $k$ is the minimum size of the color class. we will discuss some results in the non-uniform degrees and rainbow versions of the caccetta-häggkvist conjecture.

based on joint work with ron aharoni, eli berger, maria chudnovsky, and shira zerbib.

 

november 28, 2023

2:00 pm

apm 7321 and remote (to be announced)

research areas

combinatorics

****************************