A note on the uniformity threshold for Berge hypergraphs
From MaRDI portal
Publication:2145761
DOI10.1016/J.EJC.2022.103561zbMath1492.05107arXiv2111.00356OpenAlexW3211008162WikidataQ114194262 ScholiaQ114194262MaRDI QIDQ2145761
Publication date: 20 June 2022
Published in: European Journal of Combinatorics (Search for Journal in Brave)
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)le R(F,F')$, where $R$ denotes the off-diagonal Ramsey number and $F'$ is any graph obtained form $F$ by deleting an edge. We improve this bound to $th(F)le R(K_{chi(F)},F')$, and use the new bound to determine $th(F)$ exactly for several classes of graphs.
Full work available at URL: https://arxiv.org/abs/2111.00356
Extremal problems in graph theory (05C35) Hypergraphs (05C65) Generalized Ramsey theory (05C55) Ramsey theory (05D10)
Cites Work
- Unnamed Item
- Unnamed Item
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- A note on Ramsey numbers
- Large generalized books are \(p\)-good
- On the cover Turán number of Berge hypergraphs
- Asymptotics for the Turán number of Berge-\(K_{2,t}\)
- Counting copies of a fixed subgraph in \(F\)-free graphs
- Hypergraphs with No Cycle of a Given Length
- Generalizations of a Ramsey-theoretic result of chvátal
- On ramsey numbers for books
- Extremal Results for Berge Hypergraphs
- Uniformity thresholds for the asymptotic size of extremal Berge-\(F\)-free hypergraphs
- Many \(T\) copies in \(H\)-free graphs
Related Items (2)
This page was built for publication: A note on the uniformity threshold for Berge hypergraphs
