On 3-uniform hypergraphs without a cycle of a given length

DOI10.1016/J.DAM.2016.10.013zbMATH Open1358.05203arXiv1412.8083OpenAlexW2962990090MaRDI QIDQ516784FDOQ516784

Authors: Lale Özkahya, Zoltán Füredi 

Publication date: 15 March 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We study the maximum number of hyperedges in a 3-uniform hypergraph on $n$ vertices that does not contain a Berge cycle of a given length $ell$. In particular we prove that the upper bound for $C_{2k+1}$-free hypergraphs is of the order $O(k^2{n}^{1+1/k})$, improving the upper bound of Gy"ori and Lemons by a factor of $Theta(k^2)$. Similar bounds are shown for linear hypergraphs.

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

Recommendations

• On 3-uniform hypergraphs without linear cycles
• 3-uniform hypergraphs without a cycle of length five
• On coloring uniform hypergraphs without 3-cycles
• 3-uniform hypergraphs avoiding a given odd cycle
• 3-uniform hypergraphs and linear cycles
• 3-uniform hypergraphs and linear cycles
• Cycle decompositions in 3-uniform hypergraphs
• On 3-regular digraphs without vertex disjoint cycles of different lengths
• Decompositions of complete 3-uniform hypergraphs into cycles of some special even lengths
• An upper bound to the chromatic number of a uniform hypergraph without cycles of length two or three

zbMATH Keywords

cyclesextremal graphstrianglestriple systems[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn+number&go=Go Tur��n number]

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Hypergraphs (05C65) Triple systems (05B07)

Cites Work

• On the number of pentagons in triangle-free graphs
• On maximal paths and circuits of graphs
• On the maximum number of five-cycles in a triangle-free graph
• On a problem of K. Zarankiewicz
• Cycles of even length in graphs
• On arithmetic progressions of cycle lengths in graphs
• A note on the Turán function of even cycles
• Pentagons vs. triangles
• 3-uniform hypergraphs avoiding a given odd cycle
• Hypergraphs with no cycle of a given length
• On the number of \(C_ 5's\) in a triangle-free graph
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• The maximum number of triangles in \(C_{2k+1}\)-free graphs
• Title not available (Why is that?)
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• Many \(T\) copies in \(H\)-free graphs

Cited In (58)

• On \(r\)-uniform hypergraphs with circumference less than \(r\)
• Turán number of special four cycles in triple systems
• Turán numbers for hypergraph star forests
• Triangles in C5‐free graphs and hypergraphs of girth six
• Hypergraphs with no cycle of a given length
• On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition
• The maximum number of paths of length four in a planar graph
• Saturation of Berge hypergraphs
• On 3-uniform hypergraphs without linear cycles
• A note on the maximum size of Berge-\( C_4\)-free hypergraphs
• Extremal results for Berge hypergraphs
• On 2-connected hypergraphs with no long cycles
• Multicolor Turán numbers
• 3-uniform hypergraphs without a cycle of length five
• Odd cycles and \(\Theta\)-cycles in hypergraphs
• 3-uniform hypergraphs and linear cycles
• Limiting distribution of short cycles in inhomogeneous random uniform hypergraph
• On hypergraphs without loose cycles
• On the generalized Turán problem for odd cycles
• Relative Turán numbers for hypergraph cycles
• \(t\)-wise Berge and \(t\)-heavy hypergraphs
• \(C\)-cycles in hypergraphs
• Book free 3-uniform hypergraphs
• 3-uniform hypergraphs avoiding a given odd cycle
• On the maximum number of odd cycles in graphs without smaller odd cycles
• Some findings on \(r\)-uniform hypergraph of order \(n\) which contains no \(k\)-C-cycle
• The maximum number of cliques in graphs without long cycles
• Generalized Turán problems for even cycles
• Generalized Turán problems for even cycles
• On the weight of Berge-\(F\)-free hypergraphs
• Forbidding \(K_{2,t}\) traces in triple systems
• On \(3\)-uniform hypergraphs avoiding a cycle of length four
• Spectral extremal results for hypergraphs
• Extremal numbers of hypergraph suspensions of even cycles
• Multicolor Turán numbers. II: A generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles
• A note on the Turán number of a Berge odd cycle
• On \(r\)-uniform linear hypergraphs with no Berge-\(K_{2,t}\)
• On the maximum number of odd cycles in graphs without smaller odd cycles
• Triangle-Free Hypergraphs
• Berge cycles in non-uniform hypergraphs
• Hypergraphs with no odd cycle of given length
• On tight cycles in hypergraphs
• General lemmas for Berge-Turán hypergraph problems
• The Turán Number of Berge K_4 in Triple Systems
• 3-uniform hypergraphs and linear cycles
• Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Exact results on generalized Erdős-Gallai problems
• On hypergraphs of girth five
• Phase transitions in a power-law uniform hypergraph
• Anti-Ramsey numbers of paths and cycles in hypergraphs
• Cycles of given lengths in hypergraphs
• On Hamiltonian Berge cycles in [3]-uniform hypergraphs
• Many \(T\) copies in \(H\)-free graphs
• The regularity method for graphs with few 4‐cycles
• Nearly-regular hypergraphs and saturation of Berge stars
• Saturation for the 3-uniform loose 3-cycle
• Avoiding long Berge cycles: the missing cases \(k=r+1\) and \(k=r+2\)

This page was built for publication: On 3-uniform hypergraphs without a cycle of a given length

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q516784)