Perfect matchings in 4-uniform hypergraphs

被引：31

作者：

Khan, Imdadullah ^{[1
]}

机构：

[1] Lahore Univ Management Sci, Syed Babar Ali Sch Sci & Engn, Dept Comp Sci, Lahore 54792, Pakistan

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2016年 / 116卷

关键词：

Hypergraphs; Perfect matching; Vertex degree; UNIFORM HYPERGRAPHS;

D O I：

10.1016/j.jctb.2015.09.005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A perfect matching in a 4-uniform hypergraph on n vertices is a subset of left perpendicular n/4 right perpendicular disjoint edges. We prove that if H is a sufficiently large 4-uniform hypergraph on n = 4k vertices such that every vertex belongs to more than ((n-1)(3)) - (3(3n/4)) edges, then H contains a perfect matching. A construction due to Han, Person, and Schacht shows that this result is the best possible. (C) 2015 Elsevier Inc. All rights reserved.

引用

页码：333 / 366

页数：34

共 21 条

[1] Perfect matchings in r-partite r-graphs [J].

Aharoni, Ron ;

Georgakopoulos, Agelos ;

Spruessel, Philipp .

EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (01) :39-42

[2] Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels [J].

Alon, Noga ;

Frank, Peter ;

Huang, Hao ;

Roedl, Vojtech ;

Rucinski, Andrzej ;

Sudakov, Benny .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2012, 119 (06) :1200-1215

[3]

[Anonymous], 1952, Proceedings of the London Mathematical Society, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]

[4]

[Anonymous], 2000, WIL INT S D, DOI 10.1002/9781118032718

[5] SETS OF INDEPENDENT EDGES OF A HYPERGRAPH [J].

BOLLOBAS, B ;

DAYKIN, DE ;

ERDOS, P .

QUARTERLY JOURNAL OF MATHEMATICS, 1976, 27 (105) :25-32

[6]

Bollobas B., 2004, Extremal Graph Theory

[7] DEGREES GIVING INDEPENDENT EDGES IN A HYPERGRAPH [J].

DAYKIN, DE ;

HAGGKVIST, R .

BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY, 1981, 23 (01) :103-109

[8] ON EXTREMAL PROBLEMS OF GRAPHS AND GENERALIZED GRAPHS [J].

ERDOS, P .

ISRAEL JOURNAL OF MATHEMATICS, 1964, 2 (03) :183-&

[9] ON PERFECT MATCHINGS IN UNIFORM HYPERGRAPHS WITH LARGE MINIMUM VERTEX DEGREE [J].

Han, Hiep ;

Person, Yury ;

Schacht, Mathias .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (02) :732-748

[10] PERFECT MATCHINGS IN 3-UNIFORM HYPERGRAPHS WITH LARGE VERTEX DEGREE [J].

Khan, Imdadullah .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (02) :1021-1039

← 1 2 3 →