Matchings in 3-uniform hypergraphs of large minimum vertex degree

Andrew Treglown; Daniela Kühn; Deryk Osthus

doi:10.1016/j.endm.2011.10.036

Matchings in 3-uniform hypergraphs of large minimum vertex degree

Andrew Treglown^*, Daniela Kühn, Deryk Osthus

^*Corresponding author for this work

Mathematics

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

Abstract

We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph. More precisely, suppose that H is a sufficiently large 3-uniform hypergraph whose order n is divisible by 3. If the minimum vertex degree of H is greater than (^n-1₂)-(^2n/3₂), then H contains a perfect matching. This bound is tight and answers a question of Hàn, Person and Schacht. More generally, we determine the minimum vertex degree threshold that ensures that H contains a matching of size d≤n/3.

Original language	English
Pages (from-to)	813-818
Number of pages	6
Journal	Electronic Notes in Discrete Mathematics
Volume	38
DOIs	https://doi.org/10.1016/j.endm.2011.10.036
Publication status	Published - 1 Dec 2011

Keywords

Hypergraphs
Matchings
Vertex degree

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.endm.2011.10.036

Cite this

@article{2e9284f9566247929eb7a78fc762352d,

title = "Matchings in 3-uniform hypergraphs of large minimum vertex degree",

abstract = "We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph. More precisely, suppose that H is a sufficiently large 3-uniform hypergraph whose order n is divisible by 3. If the minimum vertex degree of H is greater than (n-12)-(2n/32), then H contains a perfect matching. This bound is tight and answers a question of H{\`a}n, Person and Schacht. More generally, we determine the minimum vertex degree threshold that ensures that H contains a matching of size d≤n/3.",

keywords = "Hypergraphs, Matchings, Vertex degree",

author = "Andrew Treglown and Daniela K{\"u}hn and Deryk Osthus",

year = "2011",

month = dec,

day = "1",

doi = "10.1016/j.endm.2011.10.036",

language = "English",

volume = "38",

pages = "813--818",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

T1 - Matchings in 3-uniform hypergraphs of large minimum vertex degree

AU - Treglown, Andrew

AU - Kühn, Daniela

AU - Osthus, Deryk

PY - 2011/12/1

Y1 - 2011/12/1

N2 - We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph. More precisely, suppose that H is a sufficiently large 3-uniform hypergraph whose order n is divisible by 3. If the minimum vertex degree of H is greater than (n-12)-(2n/32), then H contains a perfect matching. This bound is tight and answers a question of Hàn, Person and Schacht. More generally, we determine the minimum vertex degree threshold that ensures that H contains a matching of size d≤n/3.

AB - We determine the minimum vertex degree that ensures a perfect matching in a 3-uniform hypergraph. More precisely, suppose that H is a sufficiently large 3-uniform hypergraph whose order n is divisible by 3. If the minimum vertex degree of H is greater than (n-12)-(2n/32), then H contains a perfect matching. This bound is tight and answers a question of Hàn, Person and Schacht. More generally, we determine the minimum vertex degree threshold that ensures that H contains a matching of size d≤n/3.

KW - Hypergraphs

KW - Matchings

KW - Vertex degree

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

U2 - 10.1016/j.endm.2011.10.036

DO - 10.1016/j.endm.2011.10.036

M3 - Article

AN - SCOPUS:82955251144

SN - 1571-0653

VL - 38

SP - 813

EP - 818

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

Matchings in 3-uniform hypergraphs of large minimum vertex degree

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this