Turán Number for Bushes

Alexandr Kostochka¹ ; Zoltán Füredi²

¹University of Illinois at Urbana-Champaign
²Alfréd Rényi Institute of Mathematics, Budapest, Hungary

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

Let $ a,b \in {\bf Z}^+$, $r=a + b$, and let $T$ be a tree with parts $U = \{u_1,u_2,\dots,u_s\}$ and $V = \{v_1,v_2,\dots,v_t\}$. Let $U_1, \dots ,U_s$ and $V_1, \dots, V_t$ be disjoint sets, such that $|U_i|=a$ and $|V_j|=b$ for all $i,j$. The $(a,b)$-blowup of $T$ is the $r$-uniform hypergraph with edge set$ {\{U_i \cup V_j : u_iv_j \in E(T)\}.}$ We use the $\Delta$-systems method to prove the following Turán-type result. Suppose $a,b,t\in {\bf Z}^+$, $r=a+b\geq 3$, $a\geq 2$, and $T$ is a fixed tree of diameter $4$ in which the degree of the center vertex is $t$. Then there exists a $C=C(r,t,T)>0$ such that $ |\mathcal{H}|\leq (t-1){n\choose r-1} +Cn^{r-2}$ for every $n$-vertex $r$-uniform hypergraph $\mathcal{H}$ not containing an $(a,b)$-blowup of $T$. This is asymptotically exact when $t\leq |V(T)|/2$. A stability result is also presented.

Détail

DOI : 10.37236/12197