Turán problems for star-path forests in hypergraphs

Abstract

An $r$-uniform hypergraph ($r$-graph for short) is linear if any two edges intersect at most one vertex. Let $\mathcal{F}$ be a given family of $r$-graphs. An $r$-graph $H$ is called $\mathcal{F}$-free if $H$ does not contain any member of $\mathcal{F}$ as a subgraph. The Turán number of $\mathcal{F}$ is the maximum number of edges in any $\mathcal{F}$-free $r$-graph on $n$ vertices, and the linear Turán number of $\mathcal{F}$ is defined as the Turán number of $\mathcal{F}$ in linear host hypergraphs. An $r$-uniform linear path $P_{\ell }^r$ of length $\ell$ is an $r$-graph with edges $e_1,\dots ,e_{\ell }$ such that $|V(e_i)\cap V(e_j)|=1$ if $|i-j|=1$, and $V(e_i)\cap V(e_j)=\varnothing$ for $i\ne j$ otherwise. Gyárfás et al. [\textit{European J. Combin.} (2022) 103435] obtained an upper bound for the linear Turán number of $P_{\ell }^3$. In this paper, an upper bound for the linear Turán number of $P_{\ell }^r$ is obtained, which generalizes the known result of $P_{\ell }^3$ to any $P_{\ell }^r$. Furthermore, some results for the linear Turán number and Turán number of several linear star-path forests are obtained.

Accepted to Discrete Mathematics