On 2-connected hypergraphs with no long cycles

MaRDI QIDQ2335701zbMATH OpenFDO

Authors Ruth Luo, Zoltán Füredi, Alexandr Kostochka

Publication date 15 November 2019

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.11159, https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p31

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

maximum number of edges

Mathematics Subject Classification ID

Distance in graphs (05C12) Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Hypergraphs (05C65) Structural characterization of families of graphs (05C75) Extremal set theory (05D05)

Abstract: We give an upper bound for the maximum number of edges in an $n$-vertex 2-connected $r$-uniform hypergraph with no Berge cycle of length $k$ or greater, where $ngeqkgeq4rgeq12$. For $n$ large with respect to $r$ and $k$, this bound is sharp and is significantly stronger than the bound without restrictions on connectivity. It turned out that it is simpler to prove the bound for the broader class of Sperner families where the size of each set is at most $r$. For such families, our bound is sharp for all $ngeqkgeqrgeq3$.

Review text

Summary: We give an upper bound for the maximum number of edges in an \(n\)-vertex 2-connected \(r\)-uniform hypergraph with no Berge cycle of length \(k\) or greater, where \(n\ge k \ge 4r\ge 12\). For \(n\) large with respect to \(r\) and \(k\), this bound is sharp and is significantly stronger than the bound without restrictions on connectivity. It turned out that it is simpler to prove the bound for the broader class of Sperner families where the size of each set is at most \(r\). For such families, our bound is sharp for all \(n\ge k\geq r\ge 3\).

Recommendations

• On \(r\)-uniform hypergraphs with circumference less than \(r\)
• Avoiding long Berge cycles
• On the maximum size of connected hypergraphs without a path of given length
• On 3-uniform hypergraphs without a cycle of a given length
• Avoiding long Berge cycles. II: Exact bounds for all \(n\)

Cites work

• A variation of a theorem by Pósa
• An Erdős-Gallai type theorem for uniform hypergraphs
• Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs
• Avoiding long Berge cycles
• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• scientific article; zbMATH DE number 3485842 (Why is no real title available?)
• Hypergraph extensions of the Erdős-Gallai theorem
• Long paths and large cycles in finite graphs
• Maximal circuits of graphs. I
• On \(r\)-uniform hypergraphs with circumference less than \(r\)
• On maximal circuits in directed graphs
• On maximal paths and circuits of graphs
• On the maximum size of connected hypergraphs without a path of given length
• Path Ramsey numbers in multicolorings
• The history of degenerate (bipartite) extremal graph problems
• The maximum number of cliques in graphs without long cycles
• The structure of hypergraphs without long Berge cycles

Cited in

(15)

• The structure of hypergraphs without long Berge cycles
• Connected hypergraphs without long Berge-paths
• Avoiding long Berge cycles. II: Exact bounds for all \(n\)
• \( \mathbb{Z}_2 \times \mathbb{Z}_2\)-cordial cycle-free hypergraphs
• On \(r\)-uniform hypergraphs with circumference less than \(r\)
• Avoiding long Berge cycles
• Longest cycles in 3‐connected hypergraphs and bipartite graphs
• Stability of extremal connected hypergraphs avoiding Berge-paths
• A Dirac-type theorem for uniform hypergraphs
• Stability of extremal connected hypergraphs avoiding Berge-paths
• A hypergraph analog of Dirac's theorem for long cycles in 2-connected graphs
• Linear three-uniform hypergraphs with no Berge path of given length
• 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
• On the maximum size of connected hypergraphs without a path of given length

This page was built for publication: On 2-connected hypergraphs with no long cycles

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