Codegree Thresholds for Covering 3-Uniform Hypergraphs

Abstract

Given two 3-uniform hypergraphs $F$ and $G=(V,E)$, we say that $G$ has an $F$-covering if we can cover $V$ with copies of $F$. The minimum codegree of $G$ is the largest integer $d$ such that every pair of vertices from $V$ is contained in at least $d$ triples from $E$. Define $c_2(n,F)$ to be the largest minimum codegree among all $n$-vertex 3-graphs $G$ that contain no $F$-covering. Determining $c_2(n,F)$ is a natural problem intermediate (but distinct) from the well-studied Turán problems and tiling problems. In this paper, we determine $c_2(n, K_4)$ (for $n>98$) and the associated extremal configurations (for $n>998$), where $K_4$ denotes the complete 3-graph on 4 vertices. We also obtain bounds on $c_2(n,F)$ which are apart by at most 2 in the cases where $F$ is $K_4^ -$ ($K_4$ with one edge removed), $K_5^-$, and the tight cycle $C_5$ on 5 vertices.

Locations

• SIAM Journal on Discrete Mathematics - View
• arXiv (Cornell University) - View - PDF