Bounds on the Number of Edges in Hypertrees

Katona, Gyula Y. and Szabó, Péter (2016) Bounds on the Number of Edges in Hypertrees. DISCRETE MATHEMATICS, 339 (7). pp. 1884-1991. ISSN 0012-365X

Preview

Text katona_szabo_jav4_u.pdf Download (299kB) | Preview

Abstract

Let $\mathcal{H}$ be a $k$-uniform hypergraph. A chain in $\mathcal{H}$ is a sequence of its vertices such that every $k$ consecutive vertices form an edge. In 1999 Katona and Kierstead suggested to use chains in hypergraphs as the generalisation of paths. Although a number of results have been published on Hamiltonian chains in recent years, the generalisation of trees with chains has still remained an open area. We generalise the concept of trees for uniform hypergraphs. We say that a $k$-uniform hypergraph $\mathcal{H}$ is a hypertree if every two vertices of $\mathcal{H}$ are connected by a chain, and an appropriate kind of cycle-free property holds. An edge-minimal hypertree is a hypertree whose edge set is minimal with respect to inclusion. After considering these definitions, we show that a $k$-uniform hypertree on $n$ vertices has at least $n-(k-1)$ edges if $n>n_0(k)$, and it has at most $\binom{n}{k-1}$ edges. The latter bound is asymptotically sharp in 3-uniform case.

Actions (login required)

Edit Item