Arboricity: An acyclic hypergraph decomposition problem motivated by database theory

Abstract: The arboricity of a hypergraph is the minimum number of acyclic hypergraphs that partition . The determination of the arboricity of hypergraphs is a problem motivated by database theory. The exact arboricity of the complete -uniform hypergraph of order is previously known only for . The arboricity of the complete -uniform hypergraph of order is determined asymptotically when , positive, and determined exactly when . This proves a conjecture of Wang (2008)  in the asymptotic sense. [Copyright &y& Elsevier]