Back to Search
Start Over
TURÁN PROBLEMS AND SHADOWS III: EXPANSIONS OF GRAPHS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2015, Vol. 29 Issue 2, p868-876. 9p. - Publication Year :
- 2015
-
Abstract
- 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 Turan number o(nφ) where φ = 1+√5/2, and in particular this shows ex3 (n, G+) = O(n²) when G is the three-dimensional cube graph. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 29
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 108624107
- Full Text :
- https://doi.org/10.1137/140977138