Short Directed Cycles in Bipartite Digraphs
- PDF / 455,278 Bytes
- 25 Pages / 442.205 x 665.008 pts Page_size
- 22 Downloads / 163 Views
Bolyai Society – Springer-Verlag
Combinatorica 25pp. DOI: 10.1007/s00493-019-4065-5
SHORT DIRECTED CYCLES IN BIPARTITE DIGRAPHS PAUL SEYMOUR∗ , SOPHIE SPIRKL Received September 21, 2018 Revised July 21, 2019 The Caccetta-H¨ aggkvist 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¨ aggkvist 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.
1. Introduction The Caccetta-H¨aggkvist conjecture [1] states: Conjecture 1.1 ([1]). For every integer k ≥ 1, and all n > 0, every nvertex digraph in which every vertex has out-degree at least n/k has girth at most k. (Digraphs in this paper are finite, and without loops or parallel edges; thus, there may be an edge uv and another edge vu, but not two edges uv. A digraph has girth at most k if it has a directed cycle of length at most k.) This is vacuous for k = 1 and trivial for k = 2; but for k ≥ 3 it remains open, Mathematics Subject Classification (2010): 05C20, 05C35 Supported by ONR grant N00014-14-1-0084 and NSF grant DMS-1265563.
2
PAUL SEYMOUR, SOPHIE SPIRKL
and indeed for k = 3 it is one of the most well-known open questions in graph theory. There are numerous partial results (see [7] for a survey). In this paper we study an analogue of 1.1 for bipartite digraphs. (A digraph is bipartite if the graph underlying it is bipartite, and a bipartition of a digraph means a bipartition of this graph.) If we take disjoint sets V1 , . . . , V2k+2 , each of cardinality t for some fixed t > 0, and make a digraph with vertex set V1 ∪ · · · ∪ V2k+2 , by making every vertex in Vi adjacent from every vertex in Vi−1 , for 1 ≤ i ≤ 2k + 2 (where V0 means V2k+2 ), we obtain a digraph with a bipartition into parts both of cardinality (k + 1)t (= n say), in which every vertex has out-degree n/(k + 1), and with no directed cycle of length at most 2k. This seems to be an extremal example, and motivates the following conjecture, the topic of this paper: Conjecture 1.2. For every integer k ≥ 1, if G is a bipartite digraph, with n > 0 vertices in each part, and every vertex has out-degree more than n/(k + 1), then G has girth at most 2k. We show in section 4 that this is implied by the Caccetta-H¨aggkvist conjecture 1.1. The latter is not known to be true for any k ≥ 3, but there have been many theorems showing that for certain values of k, there exi
Data Loading...
