Clique Decompositions in Random Graphs via Refined Absorption

Abstract

We prove that if $p\ge n^{-\frac{1}{3}+{\hat{I}}^2}$ for some ${\hat{I}}^2>0$, then asymptotically almost surely the binomial random graph $G(n,p)$ has a $K_3$-packing containing all but at most $n+O(1)$ edges. Similarly, we prove that if $d\ge n^{\frac{2}{3}+{\hat{I}}^2}$ for some ${\hat{I}}^2>0$ and $d$ is even, then asymptotically almost surely the random $d$-regular graph $G_{n,d}$ has a triangle decomposition provided $3\mid d\cdot n$. We also show that $G(n,p)$ admits a fractional $K_3$-decomposition for such a value of $p$. We prove analogous versions for a $K_q$-packing of $G(n,p)$ with $p\ge n^{-\frac{1}{q+0.5}+{\hat{I}}^2}$ and leave of $(q-2)n+O(1)$ edges, for $K_q$-decompositions of $G_{n,d}$ with $(q-1)|d$ and $d\ge n^{1-\frac{1}{q+0.5}+{\hat{I}}^2}$ provided $q\mid d\cdot n$, and for fractional $K_q$-decompositions.

49 pages