TIGHT CODEGREE CONDITION FOR THE EXISTENCE OF LOOSE HAMILTON CYCLES IN 3-GRAPHS

被引：24

作者：

Czygrinow, Andrzej ^{[1
]}

Molla, Theodore ^{[1
]}

机构：

[1] Arizona State Univ, Sch Math & Stat Sci, Tempe, AZ 85287 USA

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2014年 / 28卷 / 01期

关键词：

hypergraphs; Hamilton cycle; absorbing lemma; 3-UNIFORM HYPERGRAPHS;

D O I：

10.1137/120890417

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In 2006, Kuhn and Osthus [J. Combin. Theory Ser. B, 96 (2006), pp. 767-821] showed that if a 3-graph H on n vertices has minimum codegree at least (1/4 + o(1)) n and n is even, then H has a loose Hamilton cycle. In this paper, we prove that the minimum codegree of n/4 suffices. The result is tight.

引用

页码：67 / 76

页数：10

共 5 条

[1] A MEASURE OF ASYMPTOTIC EFFICIENCY FOR TESTS OF A HYPOTHESIS BASED ON THE SUM OF OBSERVATIONS [J].

CHERNOFF, H .

ANNALS OF MATHEMATICAL STATISTICS, 1952, 23 (04) :493-507

[2]

KOH T., 1954, Colloq. Math., V3, P50

[3] Multicolored Hamilton cycles and perfect matchings in pseudorandom graphs [J].

Kuehn, Daniela ;

Osthus, Deryk .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (02) :273-286

[4] Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree [J].

Kuhn, Daniela ;

Osthus, Deryk .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (06) :767-821

[5] A Dirac-type theorem for 3-uniform hypergraphs [J].

Rödl, V ;

Rucinski, A ;

Szemerédi, E .

COMBINATORICS PROBABILITY & COMPUTING, 2006, 15 (1-2) :229-251

← 1 →