Fractional triangle decompositions of dense tripartite graphs
A fractional triangle decomposition gives each triangle a nonnegative weight so that the weights through every edge sum to one. In a balanced tripartite graph, each vertex must have equally many neighbors in the other two parts for such a decomposition to exist. The question is how large those degrees must be to guarantee a decomposition.
Why it matters and what counts as progress
Why it matters: For sufficiently large balanced tripartite graphs, results that turn fractional decompositions into exact ones can transfer a better degree bound to the completion of partial Latin squares.
What counts as progress: Lower the minimum partite degree sufficient for decomposition or strengthen the proof of a known bound. For a claimed exact decomposition or Latin-square completion, state the additional hypotheses of the transfer.
How the problem developed
- 2019 · Minimum-degree bound [1]
Flora C. Bowditch and Peter J. Dukes Proved a fractional triangle decomposition threshold of 0.96 in the balanced tripartite setting.
- 29 Sept 2026 · Improved threshold [2]
Jack Allsop, Candida Bowtell, Thomas Lesgourgues and Kalina Petrova Improved the sufficient partite degree to for some and derived a partial Latin-square completion result.
Juan Pablo Traverso Gianini with Claude Opus 5.5 Established the positivity step by exact rational Bernstein certificates at , yielding the fractional theorem at .
AI contribution
Fractional triangle decompositions of dense tripartite graphs in Lean 4
Traverso gives exact rational Bernstein certificates for the two quartic positivity tests in Proposition 4.4 at . The certificates use 20 and 5 boxes, respectively, and recover the fractional triangle-decomposition bound at .
Sources
Publication history
Fractional triangle decompositions of dense tripartite graphs in Lean 4
Daily emails by default, only when there’s an update.