Short Directed Cycles in Bipartite Digraphs

Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticle

Abstract

The Caccetta-Häggkvist conjecture implies that for every integer k ≥ 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 ≥ 224,539. More generally, we conjecture that for every integer k ≥ 1, and every pair of reals α,β < 0 with kα + β < 1, if G is a bipartite digraph with bipartition (A, B), where every vertex in A has out-degree at least β|B|, and every vertex in B has out-degree at least α|A|, then G has a directed cycle of length at most 2k. This implies the Caccetta-Häggkvist conjecture (set β < 0 and very small), and again is best possible for infinitely many pairs (α,β). We prove this for k = 1,2, and prove a weaker statement (that α + β < 2/(k + 1) suffices) for k = 3,4.

Original languageEnglish (US)
JournalCombinatorica
DOIs
StateAccepted/In press - Jan 1 2020

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Short Directed Cycles in Bipartite Digraphs'. Together they form a unique fingerprint.

  • Cite this