Arboricity: An acyclic hypergraph decomposition problem motivated by database theory

Abstract

The arboricity of a hypergraph H is the minimum number of acyclic hypergraphs that partition H. The determination of the arboricity of hypergraphs is a problem motivated by database theory. The exact arboricity of the complete k-uniform hypergraph of order n is previously known only for k∈1,2,n-2,n-1,n. The arboricity of the complete k-uniform hypergraph of order n is determined asymptotically when k=n-O(log 1-δn), δ positive, and determined exactly when k=n-3. This proves a conjecture of Wang (2008) [20] in the asymptotic sense. © 2011 Elsevier B.V. All rights reserved.