The degree threshold for covering with all the connected \(3\)-graphs with \(3\) edges

Yue Ma¹ ; Xinmin Hou² ; Zhi Yin²

¹Nanjing University of Science and Technology
²School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui 230026, China.

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

Résumé

Given two $r$-uniform hypergraphs $F$ and $H$, we say that $H$ has an $F$-covering if every vertex in $H$ is contained in a copy of $F$. Let $c_{i}(n,F)$ be the least integer such that every $n$-vertex $r$-graph $H$ with $\delta_{i}(H)>c_i(n,F)$ has an $F$-covering. Falgas-Ravry, Markström and Zhao (Combin. Probab. Comput., 2021) asymptotically determined $c_1(n,K_{4}^{(3)-})$, where $K_{4}^{(3)-}$ is obtained by deleting an edge from the complete $3$-graph on $4$ vertices. Later, Tang, Ma and Hou (Electron. J. Combin., 2023) asymptotically determined $c_1(n,C_{6}^{(3)})$, where $C_{6}^{(3)}$ is the linear triangle, i.e. $C_{6}^{(3)}=([6],\{123,345,561\})$. In this paper, we determine $c_1(n,F_5)$ asymptotically, where $F_5$ is the generalized triangle, i.e. $F_5=([5],\{123,124,345\})$. We also determine the exact values of $c_1(n,F)$, where $F$ is any connected $3$-graph with $3$ edges and $F\notin\{K_4^{(3)-}, C_{6}^{(3)}, F_5\}$.

Détail

DOI : 10.37236/12325

Classification : 05C70, 05C35, 05C07, 05C65
Mots-clés : \(r\)-uniform hypergraphs, \(F\)-covering