On r-uniform hypergraphs with circumference less than r

DOI10.1016/J.DAM.2019.07.011MaRDI QIDQ2309554zbMATH OpenOpenAlexFDO

Authors Ruth Luo, Alexandr Kostochka

Publication date 1 April 2020

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

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

zbMATH Keywords

cycles and pathsextremal hypergraph theoryTurán problem

Mathematics Subject Classification ID

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

Abstract: We show that for each $kgeq4$ and $n>rgeqk+1$, every $n$-vertex $r$-uniform hypergraph with no Berge cycle of length at least $k$ has at most $frac(k-1)(n-1)r$ edges. The bound is exact, and we describe the extremal hypergraphs. This implies and slightly refines the theorem of GyH{o}ri, Katona and Lemons that for $n>rgeqkgeq3$, every $n$-vertex $r$-uniform hypergraph with no Berge path of length $k$ has at most $frac(k-1)nr+1$ edges. To obtain the bounds, we study bipartite graphs with no cycles of length at least $2k$, and then translate the results into the language of multi-hypergraphs.

Recommendations

• Avoiding long Berge cycles. II: Exact bounds for all \(n\)
• Avoiding long Berge cycles
• On 3-uniform hypergraphs without a cycle of a given length
• The structure of hypergraphs without long Berge cycles
• On 2-connected hypergraphs with no long cycles

Cites work

• Avoiding long Berge cycles
• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• Hypergraph extensions of the Erdős-Gallai theorem
• Maximal circuits of graphs. I
• On maximal circuits in directed graphs
• On maximal paths and circuits of graphs
• Path Ramsey numbers in multicolorings
• Stability in the Erdős-Gallai theorems on cycles and paths
• The structure of hypergraphs without long Berge cycles

Cited in

(26)

• Cycles of given lengths in hypergraphs
• On the cover Turán number of Berge hypergraphs
• General lemmas for Berge-Turán hypergraph problems
• The structure of hypergraphs without long Berge cycles
• On Hamiltonian Berge cycles in [3]-uniform hypergraphs
• Connected hypergraphs without long Berge-paths
• Avoiding long Berge cycles. II: Exact bounds for all \(n\)
• 3-uniform hypergraphs without a cycle of length five
• Super-pancyclic hypergraphs and bipartite graphs
• Conditions for a bigraph to be super-cyclic
• Avoiding long Berge cycles
• On 2-connected hypergraphs with no long cycles
• Some findings on \(r\)-uniform hypergraph of order \(n\) which contains no \(k\)-C-cycle
• Avoiding long Berge cycles: the missing cases k=r+1 and k=r+2
• Longest cycles in 3‐connected hypergraphs and bipartite graphs
• Exact bipartite Turán numbers of large even cycles
• Counting hypergraphs with large girth
• Dirac-type theorems for long Berge cycles in hypergraphs
• Pósa-type results for Berge hypergraphs
• The structure of hypergraphs without long Berge cycles
• 3-uniform linear hypergraphs without a long Berge path (extended abstract)
• A hypergraph analog of Dirac's theorem for long cycles in 2-connected graphs. II: Large uniformities
• Berge pancyclic hypergraphs
• On the maximum size of connected hypergraphs without a path of given length
• On the cover Ramsey number of Berge hypergraphs
• Berge cycles in non-uniform hypergraphs

This page was built for publication: On \(r\)-uniform hypergraphs with circumference less than \(r\)

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