A note on the uniformity threshold for Berge hypergraphs

DOI10.1016/J.EJC.2022.103561MaRDI QIDQ2145761zbMATH OpenOpenAlexWikidataFDO

Authors Dániel Gerbner

Publication date 20 June 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

Berge hypergraphoff-diagonal Ramsey numberuniformity threshold

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Abstract: A Berge copy of a graph is a hypergraph obtained by enlarging the edges arbitrarily. Gr'osz, Methuku and Tompkins in 2020 showed that for any graph $F$, there is an integer $r_0=r_0(F)$, such that for any $rge{r}_0$, any $r$-uniform hypergraph without a Berge copy of $F$ has $o(n^2)$ hyperedges. The smallest such $r_0$ is called the uniformity threshold of $F$ and is denoted by $th(F)$. They showed that $th(F)leR(F,F^{\prime })$, where $R$ denotes the off-diagonal Ramsey number and $F^{\prime }$ is any graph obtained form $F$ by deleting an edge. We improve this bound to $th(F)leR(K_{chi(F)},F^{\prime })$, and use the new bound to determine $th(F)$ exactly for several classes of graphs.

Recommendations

• On Berge-Ramsey problems
• Linearity of saturation for Berge hypergraphs
• Ramsey problems for Berge hypergraphs
• Hypergraph based Berge hypergraphs
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs
• Hypergraphs with Few Berge Paths of Fixed Length between Vertices
• \(t\)-wise Berge and \(t\)-heavy hypergraphs
• On the cover Turán number of Berge hypergraphs
• On the cover Ramsey number of Berge hypergraphs
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs

Cites work

• A note on Ramsey numbers
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Counting copies of a fixed subgraph in F-free graphs
• Extremal results for Berge hypergraphs
• Generalizations of a Ramsey-theoretic result of chvátal
• scientific article; zbMATH DE number 3545699 (Why is no real title available?)
• scientific article; zbMATH DE number 969119 (Why is no real title available?)
• Hypergraphs with no cycle of a given length
• Large generalized books are \(p\)-good
• Many \(T\) copies in \(H\)-free graphs
• On ramsey numbers for books
• On the cover Turán number of Berge hypergraphs
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs

Cited in

(7)

• An Erdős-Gallai type theorem for uniform hypergraphs
• scientific article; zbMATH DE number 5630514 (Why is no real title available?)
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs
• Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs
• The maximum number of triangles in \(F_k\)-free graphs
• The Turán number of Berge book hypergraphs
• On Turán-type problems and the abstract chromatic number

This page was built for publication: A note on the uniformity threshold for Berge hypergraphs

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