Turán problems and shadows. II: Trees

DOI10.1016/J.JCTB.2016.06.011zbMATH Open1350.05113arXiv1402.0544OpenAlexW1648902078MaRDI QIDQ345098FDOQ345098

Authors: Dhruv Mubayi, J. Verstraëte, Alexandr Kostochka 

Publication date: 25 November 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: The expansion $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)$ such that distinct edges are enlarged by distinct vertices. Let ex${}_r(n,F)$ denote the maximum number of edges in an $r$-uniform hypergraph with $n$ vertices not containing any copy of $F$. The authors cite{KMV} recently determined ex${}_3(n,G^{+})$ more generally, namely when $G$ is a path or cycle, thus settling conjectures of F"uredi-Jiang cite{FJ} (for cycles) and F"uredi-Jiang-Seiver cite{FJS} (for paths). Here we continue this project by determining the asymptotics for ex${}_3(n,G^{+})$ when $G$ is any fixed forest. This settles a conjecture of F"uredi cite{Furedi}. Using our methods, we also show that for any graph $G$, either ex${}_3(n,G^{+})leqleft(frac12+o(1)ight)n^2$ or ex${}_3(n,G^{+})geq(1+o(1))n^2,$ thereby exhibiting a jump for the Tur'an number of expansions.

Full work available at URL: https://arxiv.org/abs/1402.0544

Recommendations

• Turán Problems and Shadows III: Expansions of Graphs
• A survey of Turán problems for expansions
• Linear trees in uniform hypergraphs
• Turán numbers for forests of paths in hypergraphs
• A linear hypergraph extension of Turán's theorem

zbMATH Keywords

forestscrosscutsexpansions of graphshypergraph Turán numbers

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65)

Cites Work

• On extremal problems of graphs and generalized graphs
• A hypergraph extension of Turán's theorem
• Intersection Theorems for Systems of Sets
• Exact solution of some Turán-type problems
• Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths
• Turán problems and shadows. I: Paths and cycles
• A Combinatorial Theorem
• Title not available (Why is that?)
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• Proof of a conjecture of Erdős on triangles in set-systems
• Hypergraph Turán numbers of linear cycles
• Linear trees in uniform hypergraphs
• On families of finite sets no two of which intersect in a singleton

Cited In (18)

• Turán numbers for hypergraph star forests
• Extremal Problems for Hypergraph Blowups of Trees
• Linear trees in uniform hypergraphs
• Extremal results for Berge hypergraphs
• A linear hypergraph extension of the bipartite Turán problem
• Linearity of saturation for Berge hypergraphs
• Extremal \(P_8\)-free/\(P_9\)-free planar graphs
• Intersecting families without unique shadow
• Turán numbers of general star forests in hypergraphs
• Hypergraph removal lemmas via robust sharp threshold theorems
• A survey of Turán problems for expansions
• On non-degenerate Turán problems for expansions
• Hypergraphs not containing a tight tree with a bounded trunk
• Turán numbers for Berge-hypergraphs and related extremal problems
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• Turán Problems and Shadows III: Expansions of Graphs
• Exact computation of the hypergraph Turán function for expanded complete 2-graphs
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)

This page was built for publication: Turán problems and shadows. II: Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q345098)