On fractional triangle decompositions of random graphs

Abstract

We prove that with high probability $G(n,p)$ with $p\ge n^{-4/11+o(1)}$ admits a fractional triangle decomposition (FTD), i.e., a nonnegative weighting of its triangles such that for each edge, the total weight of the triangles containing it equals one. This improves on the state of the art, due to Delcourt, Kelly, and Postle, that $p\ge n^{-1/3+o(1)}$ suffices. The proof is algorithmic: Given $G\sim G(n,p)$, we first construct an approximate FTD by taking a uniform weighting of the triangles. We then use specialized gadgets to iteratively shift weights and obtain successively better approximations of an FTD.

31 pages, 9 figures