Back to Search Start Over

Asymptotics for Tur\'an numbers of cycles in 3-uniform linear hypergraphs

Authors :
Ergemlidze, Beka
Győri, Ervin
Methuku, Abhishek
Publication Year :
2017

Abstract

Let $\mathcal{F}$ be a family of $3$-uniform linear hypergraphs. The linear Tur\'an number of $\mathcal F$ is the maximum possible number of edges in a $3$-uniform linear hypergraph on $n$ vertices which contains no member of $\mathcal{F}$ as a subhypergraph. In this paper we show that the linear Tur\'an number of the five cycle $C_5$ (in the Berge sense) is $\frac{1}{3 \sqrt3}n^{3/2}$ asymptotically. We also show that the linear Tur\'an number of the four cycle $C_4$ and $\{C_3, C_4\}$ are equal asmptotically, which is a strengthening of a theorem of Lazebnik and Verstra\"ete. We establish a connection between the linear Tur\'an 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, we obtain that the linear Tur\'an number of the linear cycle of length $2k+1$ is $\Theta(n^{1+\frac{1}{k}})$ for $k = 2, 3, 4, 6$.<br />Comment: 19 pages. Final version incorporating the changes suggested by the referees. Accepted by JCTA

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1705.03561
Document Type :
Working Paper