Turán problems and shadows II: Trees

详细信息    查看全文

• 作者：Alexandr Kostochka^a ; ^b ; ¹ ; ^{kostochk@math.uiuc.edu} ; Dhruv Mubayi^c ; ² ; ^{mubayi@uic.edu} ; Jacques Verstraë ; te^d ; ³ ; ^{jverstra@math.ucsd.edu}
• 关键词：Hypergraph Turá ; n numbers ; Expansions of graphs ; Forests ; Crosscuts
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：457-478
• 全文大小：493 K
• 卷排序：122

文摘

The expansion G+G+ of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G   with a vertex disjoint from V(G)V(G) such that distinct edges are enlarged by distinct vertices. Let exr(n,F)exr(n,F) denote the maximum number of edges in an r-uniform hypergraph with n vertices not containing any copy of F. The authors [10] recently determined ex3(n,G+)ex3(n,G+) when G is a path or cycle, thus settling conjectures of Füredi–Jiang [8] (for cycles) and Füredi–Jiang–Seiver [9] (for paths).Here we continue this project by determining the asymptotics for ex3(n,G+)ex3(n,G+) when G is any fixed forest. This settles a conjecture of Füredi [7]. Using our methods, we also show that for any graph G  , either ex3(n,G+)≤(12+o(1))n2 or ex3(n,G+)≥(1+o(1))n2ex3(n,G+)≥(1+o(1))n2, thereby exhibiting a jump for the Turán number of expansions.