Exact Minimum Codegree Threshold for K-4(-)-Factors

Author(s)

Han, Jie ^[1] ; Lo, Allan ^[2] ; Treglown, Andrew ^[2] ; Zhao, Yi ^[3]

Affiliation

^[1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo, SP - Brazil

^[2] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands - England

^[3] Georgia State Univ, Dept Math & Stat, Atlanta, GA 30303 - USA

• Document type: Journal article
• Source: COMBINATORICS PROBABILITY & COMPUTING; v. 26, n. 6, p. 856-885, NOV 2017.
• Web of Science Citations: 2

Abstract

Given hypergraphs F and H, an F-factor in H is a set of vertex-disjoint copies of F which cover all the vertices in H. Let K-4(-) denote the 3-uniform hypergraph with four vertices and three edges. We show that for sufficiently large n is an element of 4N, every 3-uniform hypergraph H on n vertices with minimum codegree at least n/2 - 1 contains a K-4(-)-factor. Our bound on the minimum codegree here is best possible. It resolves a conjecture of Lo and Markstrom {[}15] for large hypergraphs, who earlier proved an asymptotically exact version of this result. Our proof makes use of the absorbing method as well as a result of Keevash and Mycroft {[}11] concerning almost perfect matchings in hypergraphs. (AU)

• FAPESP's process: 14/18641-5 - Hamilton cycles and tiling problems in hypergraphs
• Grantee: Jie Han
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• FAPESP's process: 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science
• Grantee: Carlos Eduardo Ferreira
• Support Opportunities: Research Projects - Thematic Grants