Yuster's triangle-decomposition conjecture for random regular graphs

Let Gn,dG_{n,d} be the uniformly random dd-regular graph on nn vertices. A graph is K3K_3-divisible when its degrees are even and its number of edges is divisible by 33; for a dd-regular graph this requires dd even and 3dn3\mid dn.

Yuster's triangle-decomposition conjecture. If dnlognd\gg\sqrt{n\log n} and dd is even, then asymptotically almost surely Gn,dG_{n,d} has a K3K_3-decomposition provided 3dn3\mid dn.

This is the random-regular-graph counterpart of Yuster's triangle-packing conjecture. The supplied source does not report a resolution, so it remains open.

Sources & referencesView supporting material

Primary source

Michelle Delcourt, Tom Kelly and Luke Postle, “Clique Decompositions in Random Graphs via Refined Absorption”, arXiv:2402.17857 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.