Near Perfect Matchings in k-Uniform Hypergraphs

Jie Han

doi:10.1017/S0963548314000613

Near Perfect Matchings in k-Uniform Hypergraphs

Jie Han^*

^*Corresponding author for this work

Georgia State University

Research output: Contribution to journal › Article › peer-review

18 Citations (Scopus)

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ö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.

Original language	English
Pages (from-to)	723-732
Number of pages	10
Journal	Combinatorics Probability and Computing
Volume	24
Issue number	5
DOIs	https://doi.org/10.1017/S0963548314000613
Publication status	Published - 25 Sept 2015
Externally published	Yes

Access to Document

10.1017/S0963548314000613

Cite this

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

Abstract

Access to Document

Other files and links

Fingerprint

Cite this