Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees

• Autorzy: Péter G.N. Szabó
• Języki publikacji: EN

Abstrakty

EN

In their paper, Bounds on the number of edges in hypertrees, G.Y. Katona and P.G.N. Szabó introduced a new, natural definition of hypertrees in k- uniform hypergraphs and gave lower and upper bounds on the number of edges. They also defined edge-minimal, edge-maximal and l-hypertrees and proved an upper bound on the edge number of l-hypertrees. In the present paper, we verify the asymptotic sharpness of the [...] upper bound on the number of edges of k-uniform hypertrees given in the above mentioned paper. We also make an improvement on the upper bound of the edge number of 2-hypertrees and give a general extension construction with its consequences. We give lower and upper bounds on the maximal number of edges of k-uniform edge-minimal hypertrees and a lower bound on the number of edges of k-uniform edge-maximal hypertrees. In the former case, the sharp upper bound is conjectured to be asymptotically [...] .

Słowa kluczowe

EN

hypertree; chain in hypergraph; edge-minimal hypertree; edge-maximal hypertree; 2-hypertree; Steiner system

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 2
• Strony: 259-278

Daty

wydano

2016-05-01

otrzymano

2014-09-04

poprawiono

2015-05-05

zaakceptowano

2015-06-13

online

2016-04-15

Twórcy

autor

Péter G.N. Szabó

• Department of Computer Science and Information Theory Budapest University of Technology and Economics 3-9., Müegyetem rkp., H-1111 Budapest, Hungary

Identyfikatory

DOI

10.7151/dmgt.1855