Seminar: Progress towards Nash-Williams' Conjecture on Triangle Decompositions

Partitioning the edges of a graph into edge disjoint triangles forms a triangle decomposition of the graph. A famous conjecture by Nash-Williams from 1970 asserts that any sufficiently large, triangle divisible graph on n vertices with minimum degree at least 0.75n admits a triangle decomposition. In the light of recent results, the fractional version of this problem is of central importance. A fractional triangle decomposition is an assignment of non-negative weights to each triangle in a graph such that the sum of the weights along each edge is precisely one.

We show that for any graph on n vertices with minimum degree at least 0.827327n admits a fractional triangle decomposition. Combined with results of Barber, Kühn, Lo, and Osthus, this implies that for every sufficiently large triangle divisible graph on n vertices with minimum degree at least 0.82733n admits a triangle decomposition. This is a significant improvement over the previous asymptotic result of Dross showing the existence of fractional triangle decompositions of sufficiently large graphs with minimum degree more than 0.9n. This is joint work with Luke Postle.