Proved
Established result in cited source ↗
Observed Oct 12, 2026
Bound · version 1
An additive bound for rainbow cycles
Statement
For every fixed integer r ≥ 1 there is a constant α_r, independent of n, such that every simple n-vertex edge-colored graph with n color classes of size at least r has a rainbow cycle of length at most n/r + α_r; the constants can be chosen with α_r = O(r⁵ log² r) as r grows.
Assumptions
- The constant depends on r and is not removed by this theorem.
Evidence
Source reports
Connections
In this problem · publication v9 · Selected context
Caccetta–Häggkvist cycle bound →
Related result · Proved
Scope: The rainbow generalization holds with an r-dependent additive error.
Limit: The result does not remove the error or prove the sharp directed bound.
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.
In this problem · publication v11
Caccetta–Häggkvist cycle bound →
Related result · Proved
Scope: The rainbow generalization holds with an r-dependent additive error.
Limit: The result does not remove the error or prove the sharp directed bound.
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
Aharoni’s rainbow cycle conjecture holds up to an additive constant →
- Corollary 1.8; r = 1 discussed in its proof → · Original passage ↗
Recorded wording
For each fixed positive integer r, the authors prove a rainbow cycle bound n/r + α_r, with a constant depending on r and growth O(r⁵ log² r). This leaves the sharp ceiling bound unresolved.
paraphrase · Follow the original source for authoritative statements and reuse terms.
Patrick Hompe · Tony Huynh · Published · Publication date May 2025
Source-backed selection; publication and proof assessment are separate.
Revision & attribution
Source revision: arxiv-2212.05697v4. Observed Oct 12, 2026.
AI use is not reported in the selected source.
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-rainbow-additive
- Statement version
- 1
- SHA-256
- 38755fd4b54f342285f7e39785593079818a257e3590541c79e1e7bc0dade5a4