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

  1. 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.

  2. 29 Sept 2026 · Improved threshold [2]

    Jack Allsop, Candida Bowtell, Thomas Lesgourgues and Kalina Petrova Improved the sufficient partite degree to (0.769−η)n(0.769-\eta )n for some η>0\eta >0 and derived a partial Latin-square completion result.

  3. 30 Oct 2026 · Exact certificate [3][4]

    Juan Pablo Traverso Gianini with Claude Opus 5.5 Established the positivity step by exact rational Bernstein certificates at d=0.23105d=0.23105, yielding the fractional theorem at η=1/20000\eta =1/20000.

AI contribution

Fractional triangle decompositions of dense tripartite graphs in Lean 4

Juan Pablo Traverso Gianini

Traverso gives exact rational Bernstein certificates for the two quartic positivity tests in Proposition 4.4 at d=0.23105d = 0.23105. The certificates use 20 and 5 boxes, respectively, and recover the fractional triangle-decomposition bound at η=1/20000\eta = 1/20000.

AI involvementAI-centered
ImportanceModest
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Fractional triangle decompositions of dense 3-partite graphs
  2. Improved bounds on completion of partial Latin squares
  3. Fractional triangle decompositions of dense tripartite graphs in Lean 4
  4. Certificate generation and proof provenance
Publication history