Cycles of given lengths in hypergraphs

DOI10.1016/J.JCTB.2018.04.004MaRDI QIDQ1791703zbMATH OpenOpenAlexWikidataFDO

Authors Tao Jiang, Jie Ma

Publication date 11 October 2018

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

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

zbMATH Keywords

cycles of consecutive lengthsberge cyclesspecial-path lemmaZarankiewicz numbersTurán numbers

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: In this paper, we develop a method for studying cycle lengths in hypergraphs. Our method is built on earlier ones used in [21,22,18]. However, instead of utilizing the well-known lemma of Bondy and Simonovits [4] that most existing methods do, we develop a new and very simple lemma in its place. One useful feature of the new lemma is its adaptiveness for the hypergraph setting. Using this new method, we prove a conjecture of Verstra"ete [37] that for $rge3$, every $r$-uniform hypergraph with average degree $Omega(k^{r-1})$ contains Berge cycles of $k$ consecutive lengths. This is sharp up to the constant factor. As a key step and a result of independent interest, we prove that every $r$-uniform linear hypergraph with average degree at least $7r(k+1)$ contains Berge cycles of $k$ consecutive lengths. In both of these results, we have additional control on the lengths of the cycles, which therefore also gives us bounds on the Tur'an numbers of Berge cycles (for even and odd cycles simultaneously). In relation to our main results, we obtain further improvements on the Tur'an numbers of Berge cycles and the Zarankiewicz numbers of even cycles. We will also discuss some potential further applications of our method.

Recommendations

• On 3-uniform hypergraphs without a cycle of a given length
• On \(r\)-uniform hypergraphs with circumference less than \(r\)
• Avoiding long Berge cycles
• The structure of hypergraphs without long Berge cycles
• Avoiding long Berge cycles: the missing cases \(k=r+1\) and \(k=r+2\)

Cites work

• scientific article; zbMATH DE number 3547317 (Why is no real title available?)
• scientific article; zbMATH DE number 1117463 (Why is no real title available?)
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• 3-uniform hypergraphs avoiding a given odd cycle
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• A Note on Bipartite Graphs Without 2 k -Cycles
• A note on the Turán function of even cycles
• Counterexample to a conjecture of Györi on \(C_{2l}\)-free bipartite graphs
• Cycle lengths and minimum degree of graphs
• Cycle lengths in sparse graphs
• Cycles in bipartite graphs and an application in number theory
• Cycles in triangle-free graphs of large chromatic number
• Cycles of even length in graphs
• Cycles with consecutive odd lengths
• Distribution of cycle lengths in graphs
• Extremal problems for cycles in graphs
• Graph decomposition with applications to subdivisions and path systems modulo k
• Hypergraph Turán numbers of linear cycles
• Hypergraphs with no cycle of a given length
• Intersection Properties of Systems of Finite Sets
• Linear Turán Numbers of Linear Cycles and Cycle-Complete Ramsey Numbers
• Many \(T\) copies in \(H\)-free graphs
• On 3-uniform hypergraphs without a cycle of a given length
• On a class of degenerate extremal graph problems
• On arithmetic progressions of cycle lengths in graphs
• On coloring graphs to maximize the proportion of multicolored k-edges
• On maximal paths and circuits of graphs
• On product representation of powers. I
• On the structure of linear graphs
• Pentagons vs. triangles
• Rainbow Turán Problems
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Triangle-Free Hypergraphs
• Turán problems and shadows. I: Paths and cycles
• \(C_ 6\)-free bipartite graphs and product representation of squares

Cited in

(21)

• scientific article; zbMATH DE number 3929049 (Why is no real title available?)
• Supersaturation of C₄: from Zarankiewicz towards Erdős-Simonovits-Sidorenko
• Pósa-type results for Berge hypergraphs
• Exact bipartite Turán numbers of large even cycles
• Cycle lengths and chromatic number of graphs
• 3-uniform hypergraphs without a cycle of length five
• Large hypergraphs without tight cycles
• Book free 3-uniform hypergraphs
• Bipartite-ness under smooth conditions
• A note on the Turán number of a Berge odd cycle
• A note on cycle lengths in graphs
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
• Linear cycles of consecutive lengths
• Hypergraphs with no tight cycles
• Berge cycles in non-uniform hypergraphs
• Paths and cycles of hypergraphs
• On tight cycles in hypergraphs
• Cycles of Given Size in a Dense Graph
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Cycle Lengths in $A^k b$
• Anti-Ramsey numbers of paths and cycles in hypergraphs

This page was built for publication: Cycles of given lengths in hypergraphs

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