On decomposing complete tripartite graphs into 5-cycles
Pith reviewed 2026-05-24 21:56 UTC · model grok-4.3
The pith
The 1995 conjecture on 5-cycle decompositions of complete tripartite graphs holds when all part sizes are multiples of 5 and satisfy a given bound.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
When r ≤ s ≤ t are all multiples of 5, t + 90 ≤ 4rs/(r + s), and t ≠ s + 10, the graph K_{r,s,t} admits a decomposition into 5-cycles.
What carries the argument
Verification of the Mahmoodian-Mirzakhani conjecture for 5-cycle decompositions of K_{r,s,t} restricted to the regime where all partite sizes are multiples of 5 and obey the stated inequality.
If this is right
- All sufficiently balanced K_{r,s,t} with parts multiples of 5 admit 5-cycle decompositions.
- The remaining open cases are restricted to part sizes not all congruent to 0 mod 5 or lying outside the inequality.
- Explicit constructions become available for every such triple obeying the bound.
- The 1995 necessary conditions are confirmed as sufficient inside this arithmetic class.
Where Pith is reading between the lines
- The excluded line t = s + 10 may require a separate argument or may reveal an additional obstruction not captured by the 1995 conditions.
- The factor of 90 in the bound likely arises from a finite number of small exceptional configurations that must be handled by hand before the main construction applies.
- Similar proofs might extend to other cycle lengths whose order divides the part sizes.
Load-bearing premise
The only obstructions to a 5-cycle decomposition are the divisibility and size conditions already identified in 1995, and these remain sufficient when the part sizes are multiples of 5.
What would settle it
Exhibit a specific triple r ≤ s ≤ t, all multiples of 5, satisfying t + 90 ≤ 4rs/(r + s) and t ≠ s + 10, for which K_{r,s,t} has no decomposition into 5-cycles.
read the original abstract
The problem of finding necessary and sufficient conditions to decompose a complete tripartite graph $K_{r,s,t}$ into 5-cycles was first considered by E.S. Mahmoodian and Maryam Mirzakhani (1995). They stated some necessary conditions and conjectured that those conditions are also sufficient. Since then, many cases of the problem have been solved by various authors; however, the case when the partite sets $r\leq s\leq t$ have odd and distinct sizes remained open. We show the conjecture is true when $r$, $s$ and $t$ are all multiples of 5, $t+90 \leq \frac{4rs}{r+s}$, and $t \neq s+10$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript proves that the 1995 Mahmoodian-Mirzakhani conjecture on 5-cycle decompositions of K_{r,s,t} holds when r, s, t are multiples of 5, t + 90 ≤ 4rs/(r + s), and t ≠ s + 10.
Significance. If correct, the result resolves the conjecture on an infinite family of instances in the open case of odd distinct part sizes. It verifies sufficiency of the 1995 necessary conditions inside the stated regime and may supply reusable constructions or inductive steps for adjacent cases.
minor comments (1)
- [Abstract] Abstract: the result is asserted without any indication of the proof method (direct construction, induction, or otherwise), which is standard for a theorem paper and would help readers assess scope quickly.
Simulated Author's Rebuttal
We thank the referee for the positive recommendation of minor revision and for the accurate summary of our result on the Mahmoodian-Mirzakhani conjecture. The significance noted for resolving an infinite family in the open case is appreciated.
Circularity Check
No significant circularity identified
full rationale
The manuscript proves sufficiency of the 1995 necessary conditions for K_{r,s,t} 5-cycle decompositions in the restricted regime where r,s,t are multiples of 5, t satisfies the explicit bound t+90 ≤ 4rs/(r+s), and t ≠ s+10. No equations, parameter fits, or reductions are exhibited that collapse the claimed result to its inputs by construction. The citation to the 1995 Mahmoodian-Mirzakhani conjecture supplies the target statement but is not used to justify any load-bearing step of the new proof; the argument is presented as a direct combinatorial construction within the carved-out parameter region. This is the normal case of an independent partial resolution of an open conjecture.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.