TURAN PROBLEMS.pdf (170.02 kB)

Download file# TURAN PROBLEMS AND SHADOWS III: EXPANSIONS OF ´ GRAPHS

journal contribution

posted on 01.02.2016, 00:00 authored by A. KOSTOCHKA, D. MUBAYI, J. VERSTRAETEThe 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´an 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