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

Péter G.N. Szabó

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 2, page 259-278
  • ISSN: 2083-5892

Abstract

top
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 [...] .

How to cite

top

Péter G.N. Szabó. "Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees." Discussiones Mathematicae Graph Theory 36.2 (2016): 259-278. <http://eudml.org/doc/277128>.

@article{PéterG2016,
abstract = {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 [...] .},
author = {Péter G.N. Szabó},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypertree; chain in hypergraph; edge-minimal hypertree; edge-maximal hypertree; 2-hypertree; Steiner system},
language = {eng},
number = {2},
pages = {259-278},
title = {Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees},
url = {http://eudml.org/doc/277128},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Péter G.N. Szabó
TI - Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 2
SP - 259
EP - 278
AB - 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 [...] .
LA - eng
KW - hypertree; chain in hypergraph; edge-minimal hypertree; edge-maximal hypertree; 2-hypertree; Steiner system
UR - http://eudml.org/doc/277128
ER -

References

top
  1. [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. [2] C. Berge, Hypergraphs (North-Holland, Amsterdam, 1989). 
  3. [3] D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combin. 16 (1983) 5-10. Zbl0532.05037
  4. [4] H. Hanani, On quadruple systems, Canad. J. Math. 12 (1960) 145-157. doi:10.4153/CJM-1960-013-3[Crossref] Zbl0092.01202
  5. [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[Crossref] Zbl0924.05050
  6. [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. [7] P. Keevash, The existence of designs. arXiv:1401.3665 [math.CO] (2014). 
  8. [8] J.X. Lu, An existence theory for resolvable balanced incomplete block designs, Acta Math. Sinica 27 (1984) 458-468. Zbl0567.05011
  9. [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[Crossref] 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.