- Tytuł:
- Bounds on the Number of Edges of Edge-Minimal, Edge-Maximal and L-Hypertrees
- Autorzy:
- Szabó, Péter G.N.
- Tematy:
-
hypertree
chain in hypergraph
edge-minimal hypertree
edge-maximal hypertree
2-hypertree
Steiner system - Pokaż więcej
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Powiązania:
- https://bibliotekanauki.pl/articles/31341093.pdf Link otwiera się w nowym oknie
- Opis:
- 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 \( \binom{n}{k-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 \( \frac{1}{k-1} \binom{n}{2} \).
- Dostawca treści:
- Biblioteka Nauki
Artykuł