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

DOI10.1016/J.DISC.2018.06.006MaRDI QIDQ724883zbMATHOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• An Erdős-Gallai type theorem for uniform hypergraphs
• Connected graphs without long paths
• Hypergraph extensions of the Erdős-Gallai theorem
• On maximal paths and circuits of graphs
• The maximum number of cliques in graphs without long cycles

Cited in

(16)

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