Asymptotic Sharpness of Bounds on Hypertrees

Abstract

The hypertree can be defined in many different ways. Katona and Szabó introduced a new, natural definition of hypertrees in uniform hypergraphs and investigated bounds on the number of edges of the hypertrees. They showed that a k-uniform hypertree on n vertices has at most (nk−1)$\left( {\matrix{n \cr {k - 1} } } \right)$ edges and they conjectured that the upper bound is asymptotically sharp. Recently, Szabó verified that the conjecture holds by recursively constructing an infinite sequence of k-uniform hypertrees and making complicated analyses for it. In this note we give a short proof of the conjecture by directly constructing a sequence of k-uniform k-hypertrees.

Keywords

• hypertree
• semicycle in hypergraph
• chain in hypergraph
• 05c65