A note on the uniformity threshold for Berge hypergraphs

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

r g e 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

t h (F)

. They showed that

t h (F) l e 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

t h (F) l e R (K_{c h i (F)}, F^{'})

, and use the new bound to determine

t h (F)

exactly for several classes of graphs.

Review text

A Berge copy of a graph is a hypergraph obtained by enlarging the edges arbitrarily. \textit{D. Grósz} et al. [Eur. J. Comb. 88, Article ID 103109, 9 p. (2020; Zbl 1442.05146)] showed that for any graph \(F\), there is an integer \(r_0 = r_0(F )\), such that for any \(r \geq 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 ) \leq R(F , F^\prime)\), where \(R\) denotes the off-diagonal Ramsey number and \(F'\) is any graph obtained from \(F\) by deleting an edge. The author improves this bound to th(\(F ) \leq R(K_{\chi(F )}, F^\prime)\), and uses the new bound to determine th(\(F\) ) exactly for several classes of graphs: the \(k\)-fan, consisting of \(k\) triangles sharing a vertex, the book with \(t\) pages, which consists of \(t\) triangles sharing an edge, the wheel with \(k\) spokes, and the generalized book, formed by \(m\) copies of \(K_q\) each sharing a fixed set of \(p\) vertices. Note that in this paper the author also initiated the study of generalized cover Turán numbers for Berge hypergraphs.

Recommendations

Cites work

Cited in

(7)

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)