Short Directed Cycles in Bipartite Digraphs

Paul Seymour; Sophie Spirkl

doi:10.1007/s00493-019-4065-5

Short Directed Cycles in Bipartite Digraphs

Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

Research output: Contribution to journal › Article › peer-review

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 language	American English
Pages (from-to)	575-599
Number of pages	25
Journal	Combinatorica
Volume	40
Issue number	4
DOIs	https://doi.org/10.1007/s00493-019-4065-5
State	Published - Aug 1 2020

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-019-4065-5

Cite this

@article{afae860a50294118ab8803d9739015e3,

title = "Short Directed Cycles in Bipartite Digraphs",

abstract = "The Caccetta-H{\"a}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{\"a}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.",

author = "Paul Seymour and Sophie Spirkl",

note = "Publisher Copyright: {\textcopyright} 2020, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag.",

year = "2020",

month = aug,

day = "1",

doi = "10.1007/s00493-019-4065-5",

language = "American English",

volume = "40",

pages = "575--599",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - Short Directed Cycles in Bipartite Digraphs

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2020/8/1

Y1 - 2020/8/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85083964379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85083964379&partnerID=8YFLogxK

U2 - 10.1007/s00493-019-4065-5

DO - 10.1007/s00493-019-4065-5

M3 - Article

SN - 0209-9683

VL - 40

SP - 575

EP - 599

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

Short Directed Cycles in Bipartite Digraphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this