ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Conjecture 2.

  1. (L. Caccetta, R. H¨ aggkvist [5]) Every simple n-vertex digraph with minimum out-degree at least r has a cycle with length at most d n

r

e.

This can be restated in the following way: Let A be an n × n 0-1 matrix such that aij = 1 implies

aji 6 = 1 for all i 6 = j. Let aii = 1 for all i. If the sum of every row in A is at least r + 1, Adn/r e

has trace greater than n.

#2.1 Partial Results

The C-H conjecture has been proved for:

• r = 2 by Caccetta and H¨ aggkvist [5]

• r = 3 by Hamidoune [17]

• r = 4 and r = 5 by Ho´ ang and Reed [19]

• r ≤ √n/ 2 by Shen [30]. For the exact statement of his result, see Theorem 5.1. This shows that for any given r, the number of counterexamples to the conjecture (if any) is finite.

• Cayley graphs (which implies all vertex transitive graphs using coset representations) by Hamidoune [15]. This proof uses a lemma of Kemperman [21] (Lemma 5.9). Also, Shen [32] proved that if deg +(u) + deg +(v) ≥ 4 for all ( u, v ) ∈ E(G), then g ≤ d n/ 2e,where g denotes the girth of G. This is an average local outdegree version for the r = 2 case of the Caccetta-H¨ aggkvist conjecture.

#2.2 Approximate Results I - Additive Constant

Another approach is to show that if δ+

G

≥ r, then there is a cycle of length at most n

r

  • c for some small c. This has been proved for some values of c, as follows:

• c = 2500 by Chv´ atal and Szemer´ edi [9]

• c = 304 by Nishimura [27]

• c = 73 by Shen [31]. 22.3 Approximate Results II - Special Case n/3

The case r = n/ 2 is trivial, but r = n/ 3 has received much attention. Research has sought the minimum constant c such that δ+

G

≥ cn in an n-vertex simple digraph G forces a directed cycle of length at most 3. The conjecture is that c = 1 /3, and the current results are:

• c ≤ (3 − √5) /2 = 0.382 by Caccetta and H¨ aggkvist [5]

• c ≤ (2 √6 − 3) /5 = 0.3797 by Bondy in a neat subgraph counting argument [4]

• c ≤ 3 − √7 = 0.3542 by [29] Similarly, Seymour, Graaf, and Schrijver [12] asked for the minimum value of β so that when the minimum inand out-degrees of G are at least βn, G has a directed cycle of length at most 3. They proved that β ≤ 0.3487 and gave a formula relating β and c. Shen applied this formula to his 1998 result to get a slight improvement to β ≤ 0.3477 [29].

3 Seymour's Second Neighborhood Conjecture

This conjecture implies the special case of Caccetta-H¨ aggkvist when both inand out-degrees are at least n/ 3, and has received much attention of its own.

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.