pith. sign in

arxiv: 1809.08324 · v2 · pith:4FYPSDTJnew · submitted 2018-09-21 · 🧮 math.CO

Short directed cycles in bipartite digraphs

classification 🧮 math.CO
keywords betaeveryalphabipartiteconjecturedirectedout-degreeprove
0
0 comments X
read the original abstract

The Caccetta-H\"aggkvist conjecture implies that for every integer $k\ge 1$, if $G$ is a bipartite digraph, with $n$ vertices in each part, and every vertex has out-degree more than $n/(k+1)$, then $G$ has a directed cycle of length at most $2k$. If true this is best possible, and we prove this for $k = 1,2,3,4,6$ and all $k\ge 224,539$. More generally, we conjecture that for every integer $k\ge 1$, and every pair of reals $\alpha, \beta> 0$ with $k\alpha +\beta>1$, if $G$ is a bipartite digraph with bipartition $(A,B)$, where every vertex in $A$ has out-degree at least $\beta|B|$, and every vertex in $B$ has out-degree at least $\alpha|A|$, then $G$ has a directed cycle of length at most $2k$. This implies the Caccetta-H\"aggkvist conjecture (set $\beta>0$ and very small), and again is best possible for infinitely many pairs $(\alpha,\beta)$. We prove this for $k = 1,2$, and prove a weaker statement (that $\alpha+\beta>2/(k+1)$ suffices) for $k=3,4$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.