TY - JOUR

T1 - Turán problems and shadows III

T2 - Expansions of graphs

AU - Kostochka, Alexandr

AU - Mubayi, Dhruv

AU - Verstraëte, Jacques

N1 - Publisher Copyright:
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PY - 2015

Y1 - 2015

N2 - The expansion G+ of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a new vertex disjoint from V (G) such that distinct edges are enlarged by distinct vertices. Let ex3(n, F) denote the maximum number of edges in a 3-uniform hypergraph with n vertices not containing any copy of a 3-uniform hypergraph F. The study of ex3(n,G+) includes some well-researched problems, including the case that F consists of k disjoint edges, G is a triangle, G is a path or cycle, and G is a tree. In this paper we initiate a broader study of the behavior of ex3(n,G+). Specifically, we show ex3(n,K+ s,t) = Φ(n3-3/s) whenever t > (s-1)! and s ≥ 3. One of the main open problems is to determine for which graphs G the quantity ex3(n,G+) is quadratic in n. We show that this occurs when G is any bipartite graph with Turán number o(nΦ) where Φ = 1+ √5 2 , and in particular this shows ex3(n,G+) = O(n2) when G is the three-dimensional cube graph.

AB - The expansion G+ of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a new vertex disjoint from V (G) such that distinct edges are enlarged by distinct vertices. Let ex3(n, F) denote the maximum number of edges in a 3-uniform hypergraph with n vertices not containing any copy of a 3-uniform hypergraph F. The study of ex3(n,G+) includes some well-researched problems, including the case that F consists of k disjoint edges, G is a triangle, G is a path or cycle, and G is a tree. In this paper we initiate a broader study of the behavior of ex3(n,G+). Specifically, we show ex3(n,K+ s,t) = Φ(n3-3/s) whenever t > (s-1)! and s ≥ 3. One of the main open problems is to determine for which graphs G the quantity ex3(n,G+) is quadratic in n. We show that this occurs when G is any bipartite graph with Turán number o(nΦ) where Φ = 1+ √5 2 , and in particular this shows ex3(n,G+) = O(n2) when G is the three-dimensional cube graph.

KW - Expansions

KW - Triple systems

KW - Turán problems

UR - http://www.scopus.com/inward/record.url?scp=84938063923&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84938063923&partnerID=8YFLogxK

U2 - 10.1137/140977138

DO - 10.1137/140977138

M3 - Article

AN - SCOPUS:84938063923

SN - 0895-4801

VL - 29

SP - 868

EP - 876

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -