Caccetta–Häggkvist cycle bound

6 selected milestones · Source coverage checked 2026-10-12 · Historical annotation and mathematical review remain separate.

1. 1978 publication

   Foundation

   The cycle bound is proposed

   Caccetta and Häggkvist formulate the directed cycle conjecture.

   Statements & sources

   • The full directed cycle bound →

   • AIM · Caccetta–Häggkvist workshop survey ↗Page 2, Conjecture 2.1

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

2. 1981 publication

   Special case proved

   The vertex-transitive case

   Hamidoune proves the bound for vertex-transitive digraphs.

   Statements & sources

   • The sharp bound for vertex-transitive graphs →

   • AIM · Caccetta–Häggkvist workshop survey ↗§2.1, vertex-transitive case

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

3. 1987 publication

   Special case proved

   Small degree cases are established

   The survey records proofs for degree parameters through five.

   Statements & sources

   • The sharp bound for out-degree two through five →

   • AIM · Caccetta–Häggkvist workshop survey ↗§2.1, known cases; references [8], [22], [25]

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

4. 2000 publication

   Special case proved

   A theorem for sufficiently large order

   Shen proves the sharp bound in a restricted order-degree regime.

   Statements & sources

   • The sharp bound when n ≥ 2r² − 3r + 1 →

   • AIM · Caccetta–Häggkvist workshop survey ↗§5, Theorem 5.1

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

5. 2017 publication

   Bound established

   A published triangle threshold

   The flag-algebra paper establishes the selected 0.3465 threshold.

   Statements & sources

   • A proved 0.3465 triangle threshold →

   • Counting flags in triangle-free digraphs ↗Theorem 1.2; §2 notation; §5 computation

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

6. May 2025 publication

   Related result

   Rainbow cycles with an additive error

   Hompe and Huynh prove an r-dependent additive bound.

   Statements & sources

   • An additive bound for rainbow cycles →

   • Aharoni’s rainbow cycle conjecture holds up to an additive constant ↗Corollary 1.8; r = 1 discussed in its proof

   Historical annotation review: pending. The date refers to the publication, with the precision supported by the source.

Scope & review: This event concerns the stated scope and does not resolve the full directed conjecture.