Progress towards Nash-Williams' conjecture on triangle decompositions

Series
Graph Theory Seminar
Time
Tuesday, February 9, 2021 - 12:30pm for 1 hour (actually 50 minutes)
Location
https://us04web.zoom.us/j/77238664391. For password, please email Anton Bernshteyn (bahtoh ~at~ gatech.edu)
Speaker
Michelle Delcourt – Ryerson University – mdelcourt@ryerson.cahttps://www.ryerson.ca/graphs-group/group-members/michelle-delcourt/
Organizer
Anton Bernshteyn

Please Note: Note the unusual time!

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.