2016/12/13 by Kim Nguyen Pham, Pham, Kim Nguyen, Landon Settle +5
Computer Science · Engineering · Mathematics · #05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1612.04069
openalex publication_date 2016/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A triangle decomposition of a graph G is a partition of the edges of G into triangles. Two necessary conditions for G to admit such a decomposition are that |E(G)| is a multiple of three and that the degree of any vertex in G is even; we call such graphs tridivisible. Kirkman's work on Steiner triple systems established that for G ≃ Kn, G admits a triangle decomposition precisely when G is tridivisible. In 1970, Nash-Williams conjectured that tridivisiblity is also sufficient for "almost-complete" graphs, which for this talk's purposes we interpret as any graph G on n vertices with δ(G) ≥ (1 -ε)n, E(G) ≥ (1 - ξ)\binomn2 for some appropriately small constants ε, ξ. Nash-Williams conjectured that ε= ξ=1/4 would suffice; in 1991, Gustavsson demonstrated in his dissertation that ε= ξ< 10-24 suffices for all n ≡ 3, 9 \mod 18, and in 2015 Keevash's work on the existence conjecture for combinatorial designs established that some value of ε existed for any n. In this paper, we prove that for any ε< (1)/(432), there is a constant ξ such that any G with δ(G) ≥ (1 - ε)n and |E(G)| ≥ (1 - ξ)\binomn2 admits such a decomposition, and offer an algorithm that explicitly constructs such a triangulation. Moreover, we note that our algorithm runs in polynomial time on such graphs. (This last observation contrasts with Holyer's result that finding triangle decompositions in general is a NP-complete problem.)