Minimum codegree condition for perfect matchings in k-partite k-graphs

被引:0
作者
Lu, Hongliang [1 ]
Wang, Yan [2 ]
Yu, Xingxing [2 ]
机构
[1] Xi An Jiao Tong Univ, Sch Math & Stat, Xian 710049, Shaanxi, Peoples R China
[2] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA
基金
中国国家自然科学基金;
关键词
k-graph; k-partite k-graph; matching; perfect matching; UNIFORM HYPERGRAPHS; DEGREE THRESHOLDS;
D O I
10.1002/jgt.22448
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let H be a k-partite k-graph with n vertices in each partition class, and let delta(k-1) (H) denote the minimum codegree of H. We characterize those H with delta(k-1) (H) >= n/2 and with no perfect matching. As a consequence, we give an affirmative answer to the following question of Rodl and Rucinski: if k is even or n not equivalent to 2 (mod 4), does delta(k-1) (H) >= n/2 imply that H has a perfect matching? We also give an example indicating that it is not sufficient to impose this degree bound on only two types of (k - 1)-sets.
引用
收藏
页码:207 / 229
页数:23
相关论文
共 39 条
[31]   Factor-critical graphs with the minimum number of near-perfect matchings [J].
Doslic, Tomislav ;
Rautenbach, Dieter .
DISCRETE MATHEMATICS, 2015, 338 (12) :2318-2319
[32]   Tight co-degree condition for perfect matchings in 4-graphs [J].
Czygrinow, Andrzej ;
Kamat, Vikram .
ELECTRONIC JOURNAL OF COMBINATORICS, 2012, 19 (02)
[33]   Some bounds on spectral radius of signless Laplacian matrix of k-graphs [J].
Zhang, Junhao ;
Zhu, Zhongxun .
RAIRO-OPERATIONS RESEARCH, 2023, 57 (04) :2267-2278
[34]   NEAR PERFECT MATCHINGS IN k-UNIFORM HYPERGRAPHS II [J].
Han, Jie .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (03) :1453-1469
[35]   Self-similar groupoid actions on k-graphs, and invariance of K-theory for cocycle homotopies [J].
Mundey, Alexander ;
Sims, Aidan .
ANNALS OF FUNCTIONAL ANALYSIS, 2025, 16 (03)
[36]   DECISION PROBLEM FOR PERFECT MATCHINGS IN DENSE k-UNIFORM HYPERGRAPHS [J].
Han, Jie .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 2017, 369 (07) :5197-5218
[37]   Perfect matching and Hamilton cycle decomposition of complete balanced (k+1)-partite k-uniform hypergraphs [J].
Zhang, Yi ;
Lu, Mei ;
Liu, Ke .
APPLIED MATHEMATICS AND COMPUTATION, 2020, 386
[38]   A type of perfect matchings extend to hamiltonian cycles in k-ary n-cubes [J].
Wang, Fan ;
Sun, Wuyang .
THEORETICAL COMPUTER SCIENCE, 2018, 731 :28-35
[39]   The perfect matching and tight Hamilton cycle decomposition of complete n-balanced mk-partite k-uniform hypergraphs [J].
Jiang, Taijiang ;
Sun, Qiang ;
Zhang, Shunzhe ;
Zhang, Chao .
DISCRETE MATHEMATICS, 2023, 346 (12)