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
相关论文
共 38 条
  • [1] ALMOST PERFECT MATCHINGS IN k-PARTITE k-GRAPHS
    Lu, Hongliang
    Wang, Yan
    Yu, Xingxing
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) : 522 - 533
  • [2] Perfect Matching in k-partite k-graphs and 3-uniform HM-bipartite Hypergraphs
    Fang, Chun-qiu
    Lu, Mei
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2020, 36 (03): : 636 - 641
  • [3] Perfect Matching in k-partite k-graphs and 3-uniform HM-bipartite Hypergraphs
    Chun-qiu FANG
    Mei LU
    Acta Mathematicae Applicatae Sinica, 2020, 36 (03) : 636 - 641
  • [4] Perfect Matching in k-partite k-graphs and 3-uniform HM-bipartite Hypergraphs
    Chun-qiu Fang
    Mei Lu
    Acta Mathematicae Applicatae Sinica, English Series, 2020, 36 : 636 - 641
  • [5] Matchings in k-partite k-uniform hypergraphs
    Han, Jie
    Zang, Chuanyun
    Zhao, Yi
    JOURNAL OF GRAPH THEORY, 2020, 95 (01) : 34 - 58
  • [6] Coverings of k-graphs
    Pask, D
    Quigg, J
    Raeburn, I
    JOURNAL OF ALGEBRA, 2005, 289 (01) : 161 - 191
  • [7] On Perfect k-Matchings
    Hongliang Lu
    Wei Wang
    Graphs and Combinatorics, 2014, 30 : 229 - 235
  • [8] A GENERALIZATION OF HALL'S THEOREM FOR k-UNIFORM k-PARTITE HYPERGRAPHS
    Jafarpour-Golzari, Reza
    TRANSACTIONS ON COMBINATORICS, 2019, 8 (03) : 23 - 28
  • [9] AN EXISTENCE THEOREM OF PERFECT MATCHING ON k-PARTITE k-UNIFORM HYPERGRAPHS VIA DISTANCE SPECTRAL RADIUS
    Zhang, Lei
    Ren, Haizhen
    TRANSACTIONS ON COMBINATORICS, 2024, 13 (04) : 377 - 385
  • [10] On Perfect k-Matchings
    Lu, Hongliang
    Wang, Wei
    GRAPHS AND COMBINATORICS, 2014, 30 (01) : 229 - 235