Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs

Beka Ergemlidze, Ervin Győri, Abhishek Methuku

Research output: Contribution to journalArticlepeer-review

Abstract

Let F be a family of 3-uniform linear hypergraphs. The linear Turán number of F is the maximum possible number of edges in a 3-uniform linear hypergraph on n vertices which contains no member of F as a subhypergraph. In this paper we show that the linear Turán number of the five cycle C5 (in the Berge sense) is [Formula presented]n3/2 asymptotically. We also show that the linear Turán number of the four cycle C4 and {C3,C4} are equal asymptotically, which is a strengthening of a theorem of Lazebnik and Verstraëte [16]. We establish a connection between the linear Turán number of the linear cycle of length 2k+1 and the extremal number of edges in a graph of girth more than 2k−2. Combining our result and a theorem of Collier-Cartaino, Graber and Jiang [8], we obtain that the linear Turán number of the linear cycle of length 2k+1 is Θ(n1+[Formula presented]) for k=2,3,4,6.

Original languageEnglish (US)
Pages (from-to)163-181
Number of pages19
JournalJournal of Combinatorial Theory. Series A
Volume163
DOIs
StatePublished - Apr 2019
Externally publishedYes

Keywords

  • Berge cycle
  • Five cycle
  • Hypergraph Turán problem
  • Linear cycle
  • Linear Turán number
  • Loose cycle

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs'. Together they form a unique fingerprint.

Cite this