Turán problems and shadows II: Trees

Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review


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 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+) 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+) 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+)≤([formula presented]+o(1))n2 or ex3(n,G+)≥(1+o(1))n2, thereby exhibiting a jump for the Turán number of expansions.

Original languageEnglish (US)
Pages (from-to)457-478
Number of pages22
JournalJournal of Combinatorial Theory. Series B
StatePublished - Jan 1 2017


  • Crosscuts
  • Expansions of graphs
  • Forests
  • Hypergraph Turán numbers

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Turán problems and shadows II: Trees'. Together they form a unique fingerprint.

Cite this