Exact Minimum Codegree Threshold for K4--Factors

被引:6
作者
Han, Jie [1 ]
Lo, Allan [2 ]
Treglown, Andrew [2 ]
Zhao, Yi [3 ]
机构
[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
基金
英国工程与自然科学研究理事会; 巴西圣保罗研究基金会; 美国国家科学基金会;
关键词
3-UNIFORM HYPERGRAPHS; UNIFORM HYPERGRAPHS; GRAPHS;
D O I
10.1017/S0963548317000268
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:856 / 885
页数:30
相关论文
共 20 条
[1]   Hypergraphs Do Jump [J].
Baber, Rahil ;
Talbot, John .
COMBINATORICS PROBABILITY & COMPUTING, 2011, 20 (02) :161-171
[2]   Tiling 3-Uniform Hypergraphs With K43-2e [J].
Czygrinow, Andrzej ;
DeBiasio, Louis ;
Nagle, Brendan .
JOURNAL OF GRAPH THEORY, 2014, 75 (02) :124-136
[3]   DEGREES GIVING INDEPENDENT EDGES IN A HYPERGRAPH [J].
DAYKIN, DE ;
HAGGKVIST, R .
BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 1981, 23 (01) :103-109
[4]   SUPERSATURATED GRAPHS AND HYPERGRAPHS [J].
ERDOS, P ;
SIMONOVITS, M .
COMBINATORICA, 1983, 3 (02) :181-192
[5]   ON EXTREMAL PROBLEMS OF GRAPHS AND GENERALIZED GRAPHS [J].
ERDOS, P .
ISRAEL JOURNAL OF MATHEMATICS, 1964, 2 (03) :183-&
[6]   Minimum Codegree Threshold for C63-Factors in 3-Uniform Hypergraphs [J].
Gao, Wei ;
Han, Jie .
COMBINATORICS PROBABILITY & COMPUTING, 2017, 26 (04) :536-559
[7]  
Hajnal A., 1970, Colloq. Math. Soc. Janos Bolyai, V2, P601
[8]   Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs [J].
Han, Jie ;
Zang, Chuanyun ;
Zhao, Yi .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2017, 149 :115-147
[9]   Minimum Vertex Degree Threshold for C43-tiling [J].
Han, Jie ;
Zhao, Yi .
JOURNAL OF GRAPH THEORY, 2015, 79 (04) :300-317
[10]  
Keevash P., 2014, MEMOIRS AM MATH SOC, V233