Proved
Established result in cited source ↗
AIM · Caccetta–Häggkvist workshop survey · §5, Theorem 5.1 →
Observed Oct 12, 2026
Theorem · version 1
The sharp bound when n ≥ 2r² − 3r + 1
Earlier version 1. View current version 2 →
Statement
Every finite loopless simple digraph with n vertices, minimum out-degree at least r ≥ 1 and n ≥ 2r² − 3r + 1 contains a directed cycle of length at most ⌈n/r⌉.
Assumptions
- Shen’s theorem restricts the order relative to the minimum-degree parameter.
Evidence
Source reports
Connections
In this problem · publication v9
Caccetta–Häggkvist cycle bound →
Special case · Proved
Scope: The sharp bound holds when n ≥ 2r² − 3r + 1.
Limit: This leaves other ratios of graph order to degree untreated.
These results can cover the same graphs; their coverage is not added or expressed as a percentage.
Relationship not independently reviewed. This concerns its use in this problem.
Sources
AIM · Caccetta–Häggkvist workshop survey →
- §5, Theorem 5.1 → · Original passage ↗
Recorded wording
Shen’s theorem gives the sharp ceiling bound when the vertex count is at least 2r² − 3r + 1.
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
- §2.1, known cases; references [8], [22], [25] → · Original passage ↗
Recorded wording
The survey records the conjecture for out-degree parameters two through five, with separate proofs by Caccetta–Häggkvist, Hamidoune and Hoang–Reed.
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
- §2.1, vertex-transitive case → · Original passage ↗
Recorded wording
Vertex-transitive directed graphs satisfy the cycle bound, by Hamidoune’s connectivity argument.
paraphrase · Store metadata and original OpenMath paraphrases; follow the original source for authoritative wording.
Blair D. Sullivan; hosted by American Institute of Mathematics · Revision 2006-04-14
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Established result in cited source ↗
Observed Oct 12, 2026 · Source passage →
Record details
- Claim ID
- claim-ch-large-order
- Statement version
- 1
- SHA-256
- 351e59ccf0289b54c4b2ddfd7dcb54ac5e5dfea0047a385fe53d684e26b9ea96