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

DOI10.1016/J.JCTA.2018.12.004zbMath1403.05107arXiv1705.03561OpenAlexW2964027893WikidataQ114162694 ScholiaQ114162694MaRDI QIDQ1713504

Beka Ergemlidze, Abhishek Methuku, Ervin Gyoeri

Publication date: 25 January 2019

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

Abstract: Let $mathcalF$ be a family of $3$-uniform linear hypergraphs. The linear Tur'an number of $mathcalF$ is the maximum possible number of edges in a $3$-uniform linear hypergraph on $n$ vertices which contains no member of $mathcalF$ 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 $frac13sqrt3n^{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+frac1k})$ for $k=2,3,4,6$.

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

zbMATH Keywords

loose cycleBerge cyclehypergraph Turán problemfive cyclelinear cyclelinear Turán number

Mathematics Subject Classification ID

Hypergraphs (05C65) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Cites Work

• Unnamed Item
• Unnamed Item
• Turán numbers of bipartite graphs plus an odd cycle
• 3-uniform hypergraphs avoiding a given odd cycle
• On 3-uniform hypergraphs without a cycle of a given length
• Pentagons vs. triangles
• On hypergraphs of girth five
• On \(r\)-uniform linear hypergraphs with no Berge-\(K_{2,t}\)
• A note on the maximum number of triangles in a \(C_5\)-free graph
• Compactness results in extremal graph theory
• Cycles of even length in graphs
• On the existence of triangulated spheres in 3-graphs, and related problems
• On Arithmetic Progressions of Cycle Lengths in Graphs
• A note on the Turán function of even cycles
• A new series of dense graphs of high girth
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• Extremal Results for Berge Hypergraphs
• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• Minimal Regular Graphs of Girths Eight and Twelve
• On Minimal graphs of maximum even girth

Related Items (22)

The exact linear Turán number of the sail ⋮ Turán numbers for hypergraph star forests ⋮ Multicolor Turán numbers ⋮ The weighted hypergraph with the maximum spectral radius ⋮ Spectral Radius on Linear $r$-Graphs without Expanded $K_{r+1}$ ⋮ 3-uniform hypergraphs without a cycle of length five ⋮ Linear cycles of consecutive lengths ⋮ On the spectral radius of uniform weighted hypergraph ⋮ On \(3\)-uniform hypergraphs avoiding a cycle of length four ⋮ A linear hypergraph extension of the bipartite Turán problem ⋮ Turán numbers for Berge-hypergraphs and related extremal problems ⋮ Saturation of Berge hypergraphs ⋮ Linear saturation numbers of Berge-\(C_3\) and Berge-\(C_4\) ⋮ Relative Turán numbers for hypergraph cycles ⋮ Multicolor Turán numbers. II: A generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles ⋮ Spectral extremal results for hypergraphs ⋮ Asymptotics for the Turán number of Berge-\(K_{2,t}\) ⋮ Supersaturation of even linear cycles in linear hypergraphs ⋮ On 2-connected hypergraphs with no long cycles ⋮ Asymptotic Turán number for linear 5-cycle in 3-uniform linear hypergraphs ⋮ Multicolor Ramsey numbers for Berge cycles ⋮ A linear hypergraph extension of Turán's theorem

This page was built for publication: Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs