Paths in hypergraphs: a rescaling phenomenon

DOI10.1137/17M1122323zbMATH Open1427.05151arXiv1706.08465WikidataQ126769476 ScholiaQ126769476MaRDI QIDQ5244124FDOQ5244124

Authors: Tomasz Łuczak, Joanna Polcyn 

Publication date: 20 November 2019

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

Abstract: Let $P_e^{k}ll$ denote the loose $k$-path of length $ell$ and let define $f_e^{k}ll(n,m)$ as the minimum value of $Delta(H)$ over all $P_e^{k}ll$-free $k$-graphs $H$ with $n$ vertices and $m$ edges. In the paper we study the behavior of $f_2^4(n,m)$ and $f_3^3(n,m)$ and characterize the structure of extremal hypergraphs. In particular, it is shown that when $msim{n}^2/8$ the value of each of these functions drops down from $Theta(n^2)$ to $Theta(n)$.

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

Recommendations

• Turán problems and shadows. I: Paths and cycles
• Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths
• Ramsey number of hypergraph paths
• The Ramsey number of generalized loose paths in hypergraphs
• Hypergraphs with Few Berge Paths of Fixed Length between Vertices

zbMATH Keywords

pathshypergraphstransition phenomenon

Mathematics Subject Classification ID

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

Cites Work

• Forbidding just one intersection
• Multicolor Ramsey numbers and restricted Turán numbers for the loose 3-uniform path of length three
• Turán numbers for 3-uniform linear paths of length 3
• Turán problems and shadows. I: Paths and cycles
• The clique density theorem
• On the Minimal Density of Triangles in Graphs
• Set Systems with No Singleton Intersection
• The multipartite Ramsey number for the 3-path of length three
• A tale of stars and cliques

Cited In (2)

• On Multicolor Ramsey Numbers of Triple System Paths of Length 3
• A tale of stars and cliques

This page was built for publication: Paths in hypergraphs: a rescaling phenomenon

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