Minimum codegree threshold for C₆³-factors in 3-uniform Hypergraphs

2015/08/21 by Wei Gao, Jie Han, Gao, Wei +1
Computer Science · Engineering · Mathematics · #05C65 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1508.05152

openalex publication_date 2015/08/21 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

Let C₆³ be the 3-uniform hypergraph on \1,…, 6\ with edges 123, 345,561, which can be seen as the triangle in 3-uniform hypergraphs. For sufficiently large n divisible by 6, we show that every n-vertex 3-uniform hypergraph H with minimum codegree at least n/3 contains a C₆³-factor, i.e., a spanning subhypergraph consisting of vertex-disjoint copies of C₆³. The minimum codegree condition is best possible. This improves the asymptotical result obtained by Mycroft and answers a question of Rödl and Ruciński exactly.

Citations

• The Factorization of Linear Graphs
• On the maximal number of independent circuits in a graph
• On the Complexity of General Graph Factor Problems
• On extremal problems of graphs and generalized graphs
• Decision problem for Perfect Matchings in Dense k-uniform Hypergraphs
• A note on perfect matchings in uniform hypergraphs
• Perfect Matchings in 4-uniform hypergraphs

Related

• Minimum codegree threshold for (K₄³-e)-factors
• Exact minimum codegree threshold for K^- ₄-factors
• The degree and codegree threshold for linear triangle covering in 3-graphs
• Codegree thresholds for covering 3-uniform hypergraphs
• Codegree conditions for (fractional) Steiner triple systems