Paths in hypergraphs: a rescaling phenomenon

DOI10.1137/17M1122323MaRDI QIDQ5244124zbMATH OpenWikidataFDO

Authors Tomasz Łuczak, Joanna Polcyn

Publication date 20 November 2019

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

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

zbMATH Keywords

pathshypergraphstransition phenomenon

Mathematics Subject Classification ID

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

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)$.

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

Cites work

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

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)