Asymptotic Sharpness of Bounds on Hypertrees

• Autorzy: Yi Lin , Liying Kang , Erfang Shan
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hypertree; semicycle in hypergraph; chain in hypergraph

Kategorie tematyczne

• 05C65: Hypergraphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 789-795

Daty

wydano

2017-08-01

otrzymano

2016-04-30

poprawiono

2016-07-14

zaakceptowano

2016-07-14

online

2017-07-06

Twórcy

autor

Yi Lin

• , , , P.R.

autor

Liying Kang

• , , , P.R.

autor

Erfang Shan

• , , , P.R.

Identyfikatory

DOI

10.7151/dmgt.1947