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

extremal hypergraph theorycycles and pathsTurá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

• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• Avoiding long Berge cycles
• 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

(23)

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