Geodesic
Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 259-278 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 nk-1 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 1/k-1n2.
Keywords: hypertree, chain in hypergraph, edge-minimal hypertree, edge-maximal hypertree, 2-hypertree, Steiner system 
@article{DMGT_2016_36_2_a1,
     author = {Szab\'o, P\'eter G.N.},
     title = {Bounds on the {Number} of {Edges} of {Edge-Minimal,} {Edge-Maximal} and {L-Hypertrees}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {259--278},
     year = {2016},
     volume = {36},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a1/}
}
TY  - JOUR
AU  - Szabó, Péter G.N.
TI  - Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 259
EP  - 278
VL  - 36
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a1/
LA  - en
ID  - DMGT_2016_36_2_a1
ER  - 
%0 Journal Article
%A Szabó, Péter G.N.
%T Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 259-278
%V 36
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a1/
%G en
%F DMGT_2016_36_2_a1
Szabó, Péter G.N. Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 2, pp. 259-278. http://geodesic.mathdoc.fr/item/DMGT_2016_36_2_a1/

[1] Z. Baranyai, On the factorization of the complete uniform hypergraph, in: A. Hajnal, R. Rado and V.T. S´os (Eds.), Proceedings of a Colloquium held at Keszthely, June 25-July 1, 1973, Infinite and Finite Sets 1 (North-Holland, Amsterdam, 1975) 91-108.

[2] C. Berge, Hypergraphs (North-Holland, Amsterdam, 1989).

[3] D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combin. 16 (1983) 5-10.

[4] H. Hanani, On quadruple systems, Canad. J. Math. 12 (1960) 145-157. doi:10.4153/CJM-1960-013-3

[5] G.Y. Katona and H. Kierstead, Hamiltonian chains in hypergraphs, J. Graph Theory 30 (1999) 205-212. doi:10.1002/(SICI)1097-0118(199903)30:3h205::AID-JGT5i3.0.CO;2-O

[6] G.Y. Katona and P.G.N. Szab´o, Bounds on the number of edges in hypertrees. arXiv:1404.6430 [math.CO] (2014).

[7] P. Keevash, The existence of designs. arXiv:1401.3665 [math.CO] (2014).

[8] J.X. Lu, An existence theory for resolvable balanced incomplete block designs, Acta Math. Sinica 27 (1984) 458-468.

[9] D.K. Ray-Chaudhuri and R.M. Wilson, The existence of resolvable block designs, in: J.N. Srivastava (Ed.), A Survey of Combinatorial Theory (North-Holland, Amsterdam, 1973) 361-375. doi:10.1016/b978-0-7204-2262-7.50035-1