The paper tackles a problem in combinatorics about breaking graphs into triangles. Imagine a network where vertices are divided into three equal groups, and edges connect vertices across groups (a "balanced tripartite graph"). The question is whether you can perfectly partition all the edges of such a graph into triangles, with no edges left over. The paper proves that if every vertex has enough connections to the other two groups, specifically at least 4/5 of the maximum possible, and the graph satisfies a basic divisibility condition, then a "fractional" triangle decomposition always exists. A fractional decomposition is a relaxed version where triangles can be assigned fractional weights that sum to one on every edge, rather than requiring a clean integer partition.
The practical payoff of this result connects to a classical problem in combinatorics called Latin square completion. A Latin square is an arrangement of symbols in a grid where each symbol appears exactly once in every row and column, like a Sudoku. A partial Latin square is one that is only partly filled in, and the question is whether the partial filling can always be extended to a complete Latin square. The paper's fractional decomposition theorem, combined with earlier work by other researchers, implies that any partially filled Latin square of order n can be completed as long as fewer than 1/5 of the cells are already filled. This improves the previous best guarantee, which only worked when fewer than about 8% of cells were filled.
The proof strategy is technical but elegant. The authors use a result from linear programming called Farkas duality to reframe the fractional decomposition problem as one about edge weights. They then apply a minimum-weight perfect matching algorithm to normalize these weights into a convenient form. Finally, they construct an explicit routing scheme that directs flow through the graph in one or two steps, carefully ensuring that no edge becomes overloaded. The result is exact and works for finite graphs, not just in an asymptotic limit, which makes it stronger than many comparable results in this area.