2021arXiv (Cornell University)Open access

A note on the uniformity threshold for Berge hypergraphs

Dániel Gerbner

Open full text 0 citations

Abstract

A Berge copy of a graph is a hypergraph obtained by enlarging the edges arbitrarily. Grósz, Methuku and Tompkins in 2020 showed that for any graph $F$, there is an integer $r_0=r_0(F)$, such that for any $r\ge 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_{χ(F)},F')$, and use the new bound to determine $th(F)$ exactly for several classes of graphs.

Open-access reader

About this research paper

What this paper is about

A Berge copy of a graph is a hypergraph obtained by enlarging the edges arbitrarily. Grósz, Methuku and Tompkins in 2020 showed that for any graph $F$, there is an integer $r_0=r_0(F)$, such that for any $r\ge 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_{χ(F)},F')$, and use the new bound to determine $th(F)$ exactly for several classes of graphs.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

A Berge copy of a graph is a hypergraph obtained by enlarging the edges arbitrarily. Grósz, Methuku and Tompkins in 2020 showed that for any graph $F$, there is an integer $r_0=r_0(F)$, such that for any $r\ge 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_{χ(F)},F')$, and use the new bound to determine $th(F)$ exactly for several classes of graphs.

Key concepts: Hypergraph, Combinatorics, Mathematics, Graph, Diagonal, Upper and lower bounds, Integer (computer science), Discrete mathematics

Related papers

Back to paper searchBrowse research topicsOriginal source
A note on the uniformity threshold for Berge hypergraphs — Research Paper | ScholarLens