Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.15877 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915627391778816 |
|---|---|
| author | Mahabaduge, Ghaura Simkin, Michael |
| author_facet | Mahabaduge, Ghaura Simkin, Michael |
| contents | We prove that with high probability $G(n,p)$ with $p \geq 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 \geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_15877 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On fractional triangle decompositions of random graphs Mahabaduge, Ghaura Simkin, Michael Combinatorics 05C80 We prove that with high probability $G(n,p)$ with $p \geq 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 \geq 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. |
| title | On fractional triangle decompositions of random graphs |
| topic | Combinatorics 05C80 |
| url | https://arxiv.org/abs/2511.15877 |