THE BOLLOBAS SCOTT CONJECTURE FOR 4-UNIFORM HYPERGRAPHS

被引：4

作者：

Hou, Jianfeng ^{[1
]}

Wu, Shufei ^{[1
,2
]}

Zeng, Qinghou ^{[1
,3
]}

Zhu, Wenxing ^{[1
]}

机构：

[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350116, Fujian, Peoples R China

[2] Henan Polytech Univ, Sch Math & Informat Sci, Jiaozuo 454000, Henan, Peoples R China

[3] Univ Sci & Technol China, Sch Math Sci, Hefei 230026, Anhui, Peoples R China

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2018年 / 32卷 / 01期

基金：

中国国家自然科学基金;

关键词：

hypergraph; partition; Azuma-Hoeffding inequality; JUDICIOUS K-PARTITIONS; 3-UNIFORM HYPERGRAPHS; UNIFORM HYPERGRAPHS; GRAPHS; BOUNDS; BISECTIONS; CUT;

D O I：

10.1137/17M1128484

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let r >= 3 and k >= 2 be fixed integers. Bollobas and Scott conjectured that every r-uniform hypergraph with m edges has a vertex partition into k sets with at most m/k(r)+o(m) edges in each set, and proved the conjecture in the case r = 3. In this paper, we confirm this conjecture in the case r = 4 by showing that every 4-uniform hypergraph with m edges has a vertex partition into k sets with at most m/k(4) + O(m(8/9)) edges in each set.

引用

页码：505 / 521

页数：17

共 27 条

[1] Maximum cuts and judicious partitions in graphs without short cycles [J].

Alon, N ;

Bollobás, B ;

Krivelevich, M ;

Sudakov, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 88 (02) :329-346

[2]

[Anonymous], 2005, SURV COMB

[3]

Azuma K., 1967, TOHOKU MATH J, V19, P357, DOI DOI 10.2748/TMJ/1178243286

[4]

Bollobás B, 2002, BOLYAI MATH STUD, V10, P185

[5] Problems and results on judicious partitions [J].

Bollobás, B ;

Scott, AD .

RANDOM STRUCTURES & ALGORITHMS, 2002, 21 (3-4) :414-430

[6] Judicious partitions of hypergraphs [J].

Bollobas, B ;

Scott, AD .

JOURNAL OF COMBINATORIAL THEORY SERIES A, 1997, 78 (01) :15-31

[7] Exact bounds for judicious partitions of graphs [J].

Bollobás, B ;

Scott, AD .

COMBINATORICA, 1999, 19 (04) :473-486

[8] Judicious partitions of 3-uniform hypergraphs [J].

Bollobás, B ;

Scott, AD .

EUROPEAN JOURNAL OF COMBINATORICS, 2000, 21 (03) :289-300

[9] Max k-cut and judicious k-partitions [J].

Bollobas, Bela ;

Scott, Alex .

DISCRETE MATHEMATICS, 2010, 310 (15-16) :2126-2139

[10]

Bondy J.A., 2008, GRAD TEXTS MATH, V244

← 1 2 3 →