On the maximum size of connected hypergraphs without a path of given length

DOI10.1016/J.DISC.2018.06.006zbMATH Open1392.05032arXiv1710.08364OpenAlexW2964297058WikidataQ129609981 ScholiaQ129609981MaRDI QIDQ724883FDOQ724883

Authors: Abhishek Methuku, Nika Salia, Casey Tompkins, Máté Vizer, Ervin Győri 

Publication date: 26 July 2018

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

Abstract: In this note we asymptotically determine the maximum number of hyperedges possible in an $r$-uniform, connected $n$-vertex hypergraph without a Berge path of length $k$, as $n$ and $k$ tend to infinity. We show that, unlike in the graph case, the multiplicative constant is smaller with the assumption of connectivity.

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

Recommendations

• Connected hypergraphs without long Berge-paths
• On 2-connected hypergraphs with no long cycles
• Hypergraphs with Few Berge Paths of Fixed Length between Vertices
• On \(r\)-uniform hypergraphs with circumference less than \(r\)
• An Erdős-Gallai type theorem for uniform hypergraphs

zbMATH Keywords

Berge hypergraphconnected hypergraphErdős-Gallai theorem

Mathematics Subject Classification ID

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

Cites Work

• On maximal paths and circuits of graphs
• Hypergraph extensions of the Erdős-Gallai theorem
• Title not available (Why is that?)
• Connected graphs without long paths
• The maximum number of cliques in graphs without long cycles
• An Erdős-Gallai type theorem for uniform hypergraphs

Cited In (16)

• Connected hypergraphs without long Berge-paths
• A Dirac-type theorem for uniform hypergraphs
• On 2-connected hypergraphs with no long cycles
• Stability of extremal connected hypergraphs avoiding Berge-paths
• \((k-2)\)-linear connected components in hypergraphs of rank \(k\)
• \(t\)-wise Berge and \(t\)-heavy hypergraphs
• Stability of extremal connected hypergraphs avoiding Berge-paths
• Extremal graphs without long paths and a given graph
• The structure of hypergraphs without long Berge cycles
• Linear three-uniform hypergraphs with no Berge path of given length
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Exact results on generalized Erdős-Gallai problems
• Ramsey problems for Berge hypergraphs
• Connected graphs without long paths
• Extensions of the Erdős-Gallai theorem and Luo's theorem
• Avoiding long Berge cycles: the missing cases \(k=r+1\) and \(k=r+2\)

This page was built for publication: On the maximum size of connected hypergraphs without a path of given length

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