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

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

Zoltán Füredi, Lale Özkahya

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 (38)

• $t$-Wise Berge and $t$-Heavy Hypergraphs
• 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
• 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
• Multicolor Turán numbers
• A note on the Tur\'an number of a Berge odd cycle
• 3-uniform hypergraphs without a cycle of length five
• On Tight Cycles in Hypergraphs
• Limiting distribution of short cycles in inhomogeneous random uniform hypergraph
• On the generalized Turán problem for odd cycles
• On the maximum number of odd cycles in graphs without smaller odd cycles
• 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
• Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs
• Spectral extremal results for hypergraphs
• Nearly-Regular Hypergraphs and Saturation of Berge Stars
• Multicolor Turán numbers. II: A generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles
• On \(r\)-uniform linear hypergraphs with no Berge-\(K_{2,t}\)
• On the maximum number of odd cycles in graphs without smaller odd cycles
• General lemmas for Berge-Turán hypergraph problems
• The Turán Number of Berge K_4 in Triple Systems
• 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
• Extremal Results for Berge Hypergraphs
• On hypergraphs of girth five
• Phase transitions in a power-law uniform hypergraph
• Cycles of given lengths in hypergraphs
• Many \(T\) copies in \(H\)-free graphs
• The regularity method for graphs with few 4‐cycles

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)