Codegree threshold for tiling balanced complete \(3\)-partite \(3\)-graphs and generalized \(4\)-cycles

Xinmin Hou ; Boyuan Liu¹ ; Yue Ma

¹University of Science and Technology of China

The electronic journal of combinatorics, Tome 27 (2020) no. 3

Résumé

Given two $k$-graphs $F$ and $H$, a perfect $F$-tiling (also called an $F$-factor) in $H$ is a set of vertex-disjoint copies of $F$ that together cover the vertex set of $H$. Let $t_{k-1}(n, F)$ be the smallest integer $t$ such that every $k$-graph $H$ on $n$ vertices with minimum codegree at least $t$ contains a perfect $F$-tiling. Mycroft (JCTA, 2016) determined the asymptotic values of $t_{k-1}(n, F)$ for $k$-partite $k$-graphs $F$ and conjectured that the error terms $o(n)$ in $t_{k-1}(n, F)$ can be replaced by a constant that depends only on $F$. In this paper, we determine the exact value of $t_2(n, K_{m,m}^{3})$, where $K_{m,m}^{3}$ (defined by Mubayi and Verstraëte, JCTA, 2004) is the 3-graph obtained from the complete bipartite graph $K_{m,m}$ by replacing each vertex in one part by a 2-elements set. Note that $K_{2,2}^{3}$ is the well known generalized 4-cycle $C_4^3$ (the 3-graph on six vertices and four distinct edges $A, B, C, D$ with $A\cup B= C\cup D$ and $A\cap B=C\cap D=\emptyset$). The result confirms Mycroft's conjecture for $K_{m,m}^{3}$. Moreover, we improve the error term $o(n)$ to a sub-linear term when $F=K^3(m)$ and show that the sub-linear term is tight for $K^3(2)$, where $K^3(m)$ is the complete $3$-partite $3$-graph with each part of size $m$.

Détail

DOI : 10.37236/9061

Classification : 05C35, 05C65, 05C70