Turán problems and shadows I: Paths and cycles

Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review

Abstract

A k-path is a hypergraph Pk={e1, e2,..., ek} such that |ei∩ej|=1 if |j-i|=1 and ei∩ej=θ otherwise. A k-cycle is a hypergraph Ck={e1, e2,..., ek} obtained from a (k-1)-path {e1, e2,..., ek-1} by adding an edge ek that shares one vertex with e1, another vertex with ek-1 and is disjoint from the other edges. Let exr(n, G) be the maximum number of edges in an r-graph with n vertices not containing a given r-graph G. We prove that for fixed r≥3, k≥4 and (k, r)≠(4, 3), for large enough n: (equations) if k is odd, if k is even and we characterize all the extremal r-graphs. We also solve the case (k, r)=(4, 3), which needs a special treatment. The case k=3 was settled by Frankl and Füredi.

Original languageEnglish (US)
Pages (from-to)57-79
Number of pages23
JournalJournal of Combinatorial Theory. Series A
Volume129
DOIs
StatePublished - Jan 2015

Keywords

  • Cycles
  • Hypergraph Turán number
  • Paths
  • Uniform hypergraphs

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Turán problems and shadows I: Paths and cycles'. Together they form a unique fingerprint.

Cite this