On r-uniform hypergraphs with circumference less than r

DOI10.1016/J.DAM.2019.07.011zbMATH Open1435.05153arXiv1807.04683OpenAlexW2965343580MaRDI QIDQ2309554FDOQ2309554

Authors: Ruth Luo, Alexandr Kostochka 

Publication date: 1 April 2020

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

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.

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

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

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)

Cites Work

• On maximal paths and circuits of graphs
• Path Ramsey numbers in multicolorings
• Maximal circuits of graphs. I
• Hypergraph extensions of the Erdős-Gallai theorem
• On maximal circuits in directed graphs
• Stability in the Erdős-Gallai theorems on cycles and paths
• Title not available (Why is that?)
• Avoiding long Berge cycles
• The structure of hypergraphs without long Berge cycles

Cited In (23)

• 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
• The structure of hypergraphs without long Berge cycles
• On the cover Ramsey number of Berge hypergraphs
• 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
• Avoiding long Berge cycles: the missing cases \(k=r+1\) and \(k=r+2\)

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)