On 3-uniform hypergraphs without a cycle of a given length

被引：38

作者：

Furedi, Zoltan ^{[1
]}

Ozkahya, Lale ^{[2
]}

机构：

[1] Hungarian Acad Sci, Alfred Renyi Inst Math, POB 127, H-1364 Budapest, Hungary

[2] Hacettepe Univ, Dept Comp Engn, Ankara, Turkey

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 216卷

基金：

欧洲研究理事会; 美国国家科学基金会;

关键词：

Turan number; Triangles; Cycles; Extremal graphs; Triple systems; GRAPHS; NUMBER;

D O I：

10.1016/j.dam.2016.10.013

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We study the maximum number of hyperedges in a 3-uniform hypergraph on n vertices that does not contain a Berge cycle of a given length l. In particular we prove that the upper bound for C2k+1-free hypergraphs is of the order O(k(2)n(1+1/k)), improving the upper bound of Gyori and Lemons (2012) by a factor of Theta (k(2)). Similar bounds are shown for linear hypergraphs. (C) 2016 Elsevier B.V. All rights reserved.

引用

页码：582 / 588

页数：7

共 6 条

[1] The Maximum Number of Triangles in C2k+1-Free Graphs [J].

Gyori, Ervin ;

Li, Hao .

COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) :187-191

[2] Hypergraphs with No Cycle of a Given Length [J].

Gyori, Ervin ;

Lemons, Nathan .

COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) :193-201

[3] On the number of pentagons in triangle-free graphs [J].

Hatami, Hamed ;

Hladky, Jan ;

Kral, Daniel ;

Norine, Serguei ;

Razborov, Alexander .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (03) :722-732

[4]

Kovari T., 1954, C MATH, V3, P50

[5] A NOTE ON THE TURAN FUNCTION OF EVEN CYCLES [J].

Pikhurko, Oleg .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 2012, 140 (11) :3687-3692

[6] On arithmetic progressions of cycle lengths in graphs [J].

Verstraëte, J .

COMBINATORICS PROBABILITY & COMPUTING, 2000, 9 (04) :369-373

← 1 →