Near Perfect Matchings in k-Uniform Hypergraphs

Jie Han

doi:10.1017/S0963548314000613

Near Perfect Matchings in k-Uniform Hypergraphs

Jie Han^*

^*此作品的通讯作者

Georgia State University

科研成果: 期刊稿件 › 文章 › 同行评审

18 引用（Scopus）

摘要

Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k - 1)-degree of H is at least [n/k], then H contains a matching with [n/k] edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k - 1)-degree n/k + O(logn) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.

源语言	英语
页（从-至）	723-732
页数	10
期刊	Combinatorics Probability and Computing
卷	24
期	5
DOI	https://doi.org/10.1017/S0963548314000613
出版状态	已出版 - 25 9月 2015
已对外发布	是

访问文件

10.1017/S0963548314000613

其它文件与链接

链接到 Scopus 的出版物

引用此

Han, J. (2015). Near Perfect Matchings in k-Uniform Hypergraphs. Combinatorics Probability and Computing, 24(5), 723-732. https://doi.org/10.1017/S0963548314000613

@article{41c54b8cd45f4055a5a50087f8e76a1a,

title = "Near Perfect Matchings in k-Uniform Hypergraphs",

abstract = "Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k - 1)-degree of H is at least [n/k], then H contains a matching with [n/k] edges. This confirms a conjecture of R{\"o}dl, Ruci{\'n}ski and Szemer{\'e}di [13], who proved that minimum (k - 1)-degree n/k + O(logn) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.",

author = "Jie Han",

note = "Publisher Copyright: {\textcopyright} Cambridge University Press 2014.",

year = "2015",

month = sep,

day = "25",

doi = "10.1017/S0963548314000613",

language = "English",

volume = "24",

pages = "723--732",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "5",

}

TY - JOUR

T1 - Near Perfect Matchings in k-Uniform Hypergraphs

AU - Han, Jie

PY - 2015/9/25

Y1 - 2015/9/25

N2 - Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k - 1)-degree of H is at least [n/k], then H contains a matching with [n/k] edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k - 1)-degree n/k + O(logn) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.

AB - Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k - 1)-degree of H is at least [n/k], then H contains a matching with [n/k] edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k - 1)-degree n/k + O(logn) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.

UR - http://www.scopus.com/inward/record.url?scp=84937779420&partnerID=8YFLogxK

U2 - 10.1017/S0963548314000613

DO - 10.1017/S0963548314000613

M3 - Article

AN - SCOPUS:84937779420

SN - 0963-5483

VL - 24

SP - 723

EP - 732

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 5

ER -

Near Perfect Matchings in k-Uniform Hypergraphs

摘要

访问文件

其它文件与链接

指纹

引用此