Turán Problems for Vertex-disjoint Cliques in Multi-partite Hypergraphs

Erica L. L. Liu; Jian Wang

doi:10.1063/1.4768737

paper

Turán Problems for Vertex-disjoint Cliques in Multi-partite Hypergraphs

arXiv:1908.05983 · doi:10.1063/1.4768737

Abstract

For two $s$ -uniform hypergraphs $H$ and $F$ , the Turán number $e x_{s} (H, F)$ is the maximum number of edges in an $F$ -free subgraph of $H$ . Let $s, r, k, n_{1}, \dots, n_{r}$ be integers satisfying $2 \leq s \leq r$ and $n_{1} \leq n_{2} \leq \dots \leq n_{r}$ . De Silva, Heysse and Young determined $e x_{2} (K_{n_{1}, \dots, n_{r}}, k K_{2})$ and De Silva, Heysse, Kapilow, Schenfisch and Young determined $e x_{2} (K_{n_{1}, \dots, n_{r}}, k K_{r})$ . In this paper, as a generalization of these results, we consider three Turán-type problems for $k$ disjoint cliques in $r$ -partite $s$ -uniform hypergraphs. First, we consider a multi-partite version of the Erdős matching conjecture and determine $e x_{s} (K_{n_{1}, \dots, n_{r}}^{(s)}, k K_{s}^{(s)})$ for $n_{1} \geq s^{3} k^{2} + sr$ . Then, using a probabilistic argument, we determine $e x_{s} (K_{n_{1}, \dots, n_{r}}^{(s)}, k K_{r}^{(s)})$ for all $n_{1} \geq k$ . Recently, Alon and Shikhelman determined asymptotically, for all $F$ , the generalized Turán number $e x_{2} (K_{n}, K_{s}, F)$ , which is the maximum number of copies of $K_{s}$ in an $F$ -free graph on $n$ vertices. Here we determine $e x_{2} (K_{n_{1}, \dots, n_{r}}, K_{s}, k K_{r})$ with $n_{1} \geq k$ and $n_{3} = \dots = n_{r}$ . Utilizing a result on rainbow matchings due to Glebov, Sudakov and Szabó, we determine $e x_{2} (K_{n_{1}, \dots, n_{r}}, K_{s}, k K_{r})$ for all $n_{1}, \dots, n_{r}$ with $n_{4} \geq r^{r} (k - 1) k^{2 r - 2}$ .

After the paper appeared in Discrete Mathematics, we are informed that a much stronger form of Theorems 1.1 and 1.3 have already been proved by Frankl in 2012, where a beautiful proof is given via Katona's Cyclic Permutation Method. Please see "P. Frankl, Disjoint edges in separated hypergraphs, Moscow Journal of Combinatorics and Number Theory 2012, vol.2, iss. 4, pp 19-26."