Proved
Established result in cited source ↗
AIM · Caccetta–Häggkvist workshop survey · §5, Theorem 5.1 →
Observed Oct 21, 2026
Replaces an earlier source assessment. Version history ↓
Theorem · version 2
The sharp bound when n ≥ 2r² − 3r + 1
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 v11 · Selected context
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, Partial Results; references [5], [17], [19] → · Original passage ↗
Recorded wording
The survey records the conjecture for out-degree parameters two through five, with separate proofs by Caccetta–Häggkvist (r = 2), Hamidoune (r = 3) and Hoàng–Reed (r = 4, 5).
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-sha256-98251ac3
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 21, 2026 · Source passage →
Replaces an earlier source assessment; see the original source for its history.
Record details
- Claim ID
- claim-ch-large-order
- Statement version
- 2
- SHA-256
- fbc79b0158fa4745402ea597761cb48883b6d54b0ccf8dbbf909ecc3bb6870bc