Asymptotic Sharpness of Bounds on Hypertrees

Yi Lin, Liying Kang, and Erfang Shan. "Asymptotic Sharpness of Bounds on Hypertrees." Discussiones Mathematicae Graph Theory 37.3 (2017): 789-795. <http://eudml.org/doc/288341>.

@article{YiLin2017,
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( \{\{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.},
author = {Yi Lin, Liying Kang, Erfang Shan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypertree; semicycle in hypergraph; chain in hypergraph},
language = {eng},
number = {3},
pages = {789-795},
title = {Asymptotic Sharpness of Bounds on Hypertrees},
url = {http://eudml.org/doc/288341},
volume = {37},
year = {2017},
}

TY - JOUR
AU - Yi Lin
AU - Liying Kang
AU - Erfang Shan
TI - Asymptotic Sharpness of Bounds on Hypertrees
JO - Discussiones Mathematicae Graph Theory
PY - 2017
VL - 37
IS - 3
SP - 789
EP - 795
AB - 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( {{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.
LA - eng
KW - hypertree; semicycle in hypergraph; chain in hypergraph
UR - http://eudml.org/doc/288341
ER -