## Hypergraph based Berge hypergraphs

Martin Balko 1 ∗ D´ aniel Gerbner 2 † Dong Yeap Kang 3 ‡ Younjin Kim 4 § Cory Palmer 5

August 2, 2019

1 Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Czech Republic balko@kam.mff.cuni.cz

2 Alfr´d R´ enyi Institute of Mathematics, Hungarian Academy of Sciences, Budapest, Hungary e gerbner@renyi.hu

3 Department of Mathematical Sciences, KAIST, South Korea dyk90@kaist.ac.kr

4 Institute of Mathematical Sciences, Ewha Womans University, Seoul, South Korea younjinkim@ewha.ac.kr

5

University of Montana, Missoula, Montana 59812, USA

cory.palmer@umontana.edu

## Abstract

Fix a hypergraph F . A hypergraph H is called a Berge copy of F or BergeF if we can choose a subset of each hyperedge of H to obtain a copy of F . A hypergraph H is BergeF -free if it does not contain a subhypergraph which is Berge copy of F . This is a generalization of the usual, graph based Berge hypergraphs, where F is a graph.

In this paper, we study extremal properties of hypergraph based Berge hypergraphs and generalize several results from the graph based setting. In particular, we show

∗ The first author was supported by the grant no. 19-04113Y of the Czech Science Foundation (GA ˇ R) and C by the Center for Foundations of Modern Computer Science (Charles University project UNCE/SCI/004).

† The second author was supported in part by the J´nos Bolyai Research Fellowship of the Hungarian a Academy of Sciences and the National Research, Development and Innovation Office - NKFIH under the grants K 116769, KH 130371 and SNN 12936.

‡ The third author was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2017R1A2B4005020) and also by TJ Park Science Fellowship of POSCO TJ Park Foundation.

§ The fourth author is a corresponding author and was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (2017R1A6A3A04005963).

that for any r -uniform hypregraph F , the sum of the sizes of the hyperedges of a (not necessarily uniform) BergeF -free hypergraph H on n vertices is o n ( r ) when all the hyperedges of H are large enough. We also give a connection between hypergraph based Berge hypergraphs and generalized hypergraph Tur´n problems. a

## 1 Introduction

Berge [5] defined hypergraph cycles in the following way. A cycle of length k corresponds to k vertices v , . . . , v 1 k and k distinct hyperedges h , . . . , h 1 k such that v i and v i +1 are both contained in h i for i &lt; k , while h k contains both v k and v 1 . Observe that for 2-uniform hypergraphs these are the usual graph cycles, but in case of larger hyperedges there are several non-isomorphic cycles of length k . Note that there are several other definitions of hypergraph cycles; these ones are usually referred to as Berge cycles .

Berge did not study extremal properties of these cycles. Lazebnik and Verstra¨ ete [23] were the first to consider such problems. They gave bounds on the number of hyperedges in an r -uniform hypergraph without a Berge cycle of length at most 4. Many similar results followed for Berge cycles (see, for example, [19, 21]) and Berge paths [20], where a Berge path is obtained from a Berge cycle by removing a hyperedge (similarly for the graph case).

Gerbner and Palmer [15] observed that the way we obtain a Berge cycle from a graph cycle C k or a Berge path from a path P k can be generalized to any graph G .

Definition 1. A hypergraph H is a Berge copy of a graph G (in short: BergeG ) if V ( G ) ⊆ V ( H ) and there is a bijection f : E G ( ) → E ( H ) such that for any e ∈ E G ( ) we have e ⊆ f ( e ) .

In other words, H is BergeG if we can choose a pair of vertices (i.e., a graph edge) in each hyperedge of H to obtain a copy of G . The maximum number (or weight) of hyperedges in BergeG -free hypergraphs has been studied by a number of authers (see, for example, [7, 13, 14, 26, 29], and Subsection 5.2.2. of [17] for a short survey). Others have investigated saturation problems [8, 9], Ramsey problems [4, 12, 28] or spectral radius [22] for Berge hypergraphs.

It has been observed in several different settings [3, 8, 17, 28] that one can analogously define Berge copies of a hypergraph. More precisely we have the following definition.

Definition 2. Fix a hypergraph F . A hypergraph H is a Berge copy of F (in short: BergeF ) if V ( F ) ⊆ V ( H ) and there is a bijection f : E ( F ) → E ( H ) such that for any h ∈ E ( F ) we have h ⊆ f ( h ) . In the case when H is k -uniform, we say H is Berge k F .

Fix a family of hypergraphs C . A hypergraph H is a Berge copy of C (in short: BergeC ) if it is a Berge copy of some member F ∈ C . In the case when H is k -uniform, we say H is Berge k C .

We call such hypergraphs hypergraph based Berge hypergraphs . So far there has been no systematic study of their properties. In this paper we focus on the maximum number (or sum of weights) of edges in hypergraphs avoiding Berge copies of a given hypergraph F .

Note that the BergeF and Berge k F are defined even if F is not r -uniform for some r ≤ k . However, here we will only deal with the case when F is r -uniform.

As we often consider several hypergraphs simultaneously, for the sake of brevity we will use the term r -graph in place of r -uniform hypergraph. The term r -edge refers to a hyperedge of an r -graph. Given a family C of r -graphs, we denote by ex ( r n, C ) the maximum possible number of hyperedges in an n -vertex r -graph that does not contain any member of C as a sub-hypergraph. Thus, when C is the family BergeF for some hypergraph F , we use the notation ex ( r n, BergeF ).

## 1.1 Graph based Berge hypergraphs

In this subsection we state several known results for the ordinary, graph based Berge hypergraphs, that we will generalize. First we deal with BergeF -free hypergraphs that are not necessarily uniform, where F is a graph. Observe that replacing a hyperedge with a larger hyperedge cannot destroy a copy of BergeF , thus in order to maximize hyperedges in a BergeF -free hypergraph it is preferable to use small hyperedges. Instead, we will assign a weight to each hyperedge that depends on the size of the hyperedge. Such problems were studied by Gy˝ri [19] for triangles, by Gy˝ri and Lemons [21] for cycles, and by Gerbner and o o Palmer [15] for arbitrary graphs. In these papers the weight of a hyperedge h is | h | or | h |-c for some constant c . Recently English, Gerbner, Methuku and Palmer [7] considered more general weight functions.

Before stating their results, we state a result of Gr´sz, Methuku, and Tompkins [18] that o deals with k -uniform BergeF -free hypergraphs (where F is a graph), for k large enough. Let us denote by R ( r ) ( F K , ) the two-color r -uniform Ramsey number of r -graphs F and K . When r = 2, put R F, K ( ) = R (2) ( F, K ).

Theorem 3 (Gr´ osz, Methuku, Tompkins [18]) . Let F be a graph and let H be a k -uniform BergeF -free hypergraph. If k ≥ R F, F ( ) , then

$$| E ( \mathcal { H } ) | = o ( n ^ { 2 } ). \$$

Using ideas from Gr´sz, Methuku, and Tompkins [18], English, Gerbner, Methuku, and o Palmer [7] showed that for any fixed graph F the sum of the sizes of the hyperedges of a BergeF -free hypergraph on n vertices is o n ( 2 ) when all the hyperedges are large enough. This follows from the two results below.

Theorem 4 (English, Gerbner, Methuku, Palmer [7]) . Let F be a fixed graph and let H be a BergeF -free hypergraph on n vertices. If every hyperedge of H has size at least | V ( F ) | , then

$$\sum _ { h \in E ( \mathcal { H } ) } | h | ^ {$$

Furthermore, if every hyperedge of H has size at least R F, F ( ) and at most o n ( ) , then

$$\sum _ { h \in E ( \mathcal { H } ) } | h | ^ {$$

Corollary 5 (English, Gerbner, Methuku, Palmer [7]) . Let F be a fixed graph and let H be a BergeF -free hypergraph on n vertices. Let w : Z + → Z + be a weight function such that w m ( ) = o m ( 2 ) . If every hyperedge of H has size at least R F, F ( ) , then

$$\sum _ { h \in E ( \mathcal { H } ) } w ( | h |$$

For uniform BergeF -free hypergraphs, Gerbner and Palmer [16] established a connection to generalized Tur´ an problems. Given two graphs H and F , let ex( n, H, F ) denote the maximum number of copies of H in an F -free graph on n vertices. More formally, if N H,G ( ) denotes the number of subgraphs of G that are isomorphic to H , then

$$\begin{array} {$$

When H = K 2 , this is the ordinary Tur´n function ex( a n, F ). The first result concerning other graphs H was the exact determination of ex( n, K , K k r ) for each k and r by Zykov [31]. Several more sporadic results followed it, and the systematic study of ex( n, H, F ) was initiated by Alon and Shikhelman [1]. The area is sometimes referred to as generalized Tur´n a problems .

A connection between (graph based) Berge hypergraphs and generalized Tur´n problems a was obtained by Gerbner and Palmer [16], who proved that for any graph F , any r , and any n , we have

$$\exp ( n, K _ { r }, F ) \leq \exp _ { r } ( n, \text{Berge-} F ) \leq \exp ( n, K _ { r }, F ) + \exp ( n, F ). \\ \sum \lim _ { \alpha \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \end{array}$$

This was later generalized by Gerbner, Methuku, and Palmer [13]. To state their result, we need to introduce some definitions. We say that a graph G is red-blue if each of its edges is colored with one of the colors red and blue. Then for a red-blue graph G , we denote by G red the subgraph spanned by the red edges and G blue the subgraph spanned by the blue edges. Put g r ( G ) = | E G ( red ) + | N K ,G ( r blue ).

Lemma 6 (Gerbner, Methuku, Palmer [13]) . For any graph F and integers r, n there is a red-blue F -free graph G on n vertices, such that ex ( r n, BergeF ) ≤ g r ( G ) .

This lemma was used to prove several new bounds on ex ( r n, BergeF ) for various graphs F . Note that an essentially equivalent version was obtained by F¨redi, u Kostochka, and Luo [10].

## 2 Hypergraph based Berge hypergraphs

The main results of this paper are hypergraph analogues of Theorem 4, Corollary 5, and Lemma 6.

Theorem 7. Let F be an r -graph with r ≥ 2 and let H be a BergeF -free hypergraph on n vertices. If every hyperedge of H has size at least | V ( F | ) , then

$$\sum _ { h \in E ( \mathcal { H } ) } | h | ^ { r } = O ( n ^ { r } ).$$

Furthermore, if every hyperedge of H has size at least R ( r ) ( F F , ) and at most o n ( ) , then

$$\sum _ { \ h \in E ( \mathcal { H } ) } | h | ^ { r } = o ( n ^ { r } ). \\. \quad \dots \quad \cdot \ \cdot \ \cdot \dots.$$

Corollary 8. Let F be an r -graph with r ≥ 2 and let H be a BergeF -free hypergraph on n vertices. Let w : Z + → Z + be a weight function such that w m ( ) = o m ( r ) . If every hyperedge of H has size at least R ( r ) ( F F , ) , then

$$\sum _ { h \in E ( \mathcal { H } ) } w ( | h | ) = o ( n ^ { r } ). \\. \cdot \cdot \cdot \cdot \cdot \cdot \cdot.$$

Note that the above corollary is sharp in the sense that we cannot take a larger weight function as the hypergraph of a single hyperedge of size Ω( n ) has weight Ω( n r ). We will prove Theorem 7 and Corollary 8 in Section 3. Another corollary is the following hypergraph analogue of Theorem 3.

Corollary 9. Let F be an r -graph with r ≥ 2 and let H be a k -uniform BergeF -free hypergraph on n vertices. If k ≥ R ( r ) ( F F , ) , then we have

$$| E ( \mathcal { H } ) | = o ( n ^ { r } ).$$

In the above corollaries the upper bound cannot be improved by much, even if the threshold R ( r ) ( F F , ) on the sizes of the hyperedges is increased (as long as the threshold does not depend on n ). Indeed, let F be an r -graph consisting of three hyperedges on r +1 vertices. Then a k -uniform BergeF has three hyperedges on at most 3( k -r )+ k +1 vertices. Alon and Shapira [2] constructed for any 2 ≤ r &lt; k a k -uniform hypergraph with the property that any 3( k -r ) + k + 1 vertices span less than 3 edges, with n r -o (1) hyperedges. These hypergraphs are obviously BergeF -free, giving the lower bound of n r -o (1) for this particular F in both corollaries.

( ) As in the graph case we say that a hypergraph H is red-blue if each of its hyperedges is colored with one of the colors red and blue. Let H red and H blue be the subhypergraphs of H spanned by the red hyperedges and the blue hyperedges of H , respectively. Put g k r ( H ) = | E ( H red ) + | N ( K ( k ) r , H blue ).

Before stating our analogue of Lemma 6 we need to introduce further definitions. Given two k -graphs H and F , let ex ( k n, H F , ) denote the maximum number of copies of H in F -free k -graphs on n vertices. Let N ( H H , ′ ) denote the number of subhypergraphs of H ′ that are isomorphic to H . Let K ( k ) s be the complete k -graph on s vertices (containing all possible s k hyperedges).

Lemma 10. For any k -graph F and integers r, n there is a red-blue F -free k -graph H on n vertices such that H red is K ( k ) r -free and ex ( r n, BergeF ) ≤ g r ( H ) .

Note that the lemma implies

$$\text{ex} _ { k } ( n, \mathcal { K } _ { r } ^ { ( k ) }, \mathcal { F } ) \leq \text{ex} _ { r } ( n, \text{Berg} \prec \mathcal { F } ) \leq \text{ex} _ { k } ( n, \mathcal { K } _ { r } ^ { ( k ) }, \mathcal { F } ) + \text{ex} _ { k } ( n, \mathcal { F } ).$$

We prove Lemma 10 in Section 5. We also obtain some simple results in case F itself is a graph based hypergraph (for example F is a specific Berge copy of a graph F 0 ). Recall that the expansion F + k 0 of a graph F 0 is the Berge copy of F 0 which is constructed by adding r -2 new and distinct vertices to each edge of F 0 . Using Lemma 10 we can establish asymptotics for ex k ( n, K ( k ) r , F + k 0 ) in case χ F ( 0 ) &gt; r &gt; k .

## 3 Proof of Theorem 7

Proof of Theorem 7. For r ≥ 2, let us consider the r -graph Γ ( r ) ( S ) with vertex set S and whose edge set is the collection of all subsets of S of size r . For a hypergraph H , its r -shadow , Γ ( r ) ( H ), is the r -graph with vertex set V (Γ ( r ) ( H )) := V ( H ) and whose edge set is the set of all r -tuples contained in at least one hyperedge of H . We will use the following theorem of de Caen [6] about the Tur´n number of a K ( r ) s for s &gt; r &gt; 2.

Theorem 11 (de Caen [6]) . For s &gt; r &gt; 2 ,

$$\exp _ { r } ( n, \mathcal { K } _ { s } ^ { ( r ) } ) & \leq \binom { n } { r } \left ( 1 - \frac { n - r + 1 } { ( n - s + 1 ) \binom { s - 1 } { r - 1 } } \right ). \\ \text{ly, we will use the following simple corollary: for $n\geq s$, $t$} \exp _ { r } ( n, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cd:, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots, \cdots$$

( ) Let F be an r -graph and H be BergeF -free hypergraph on n vertices. We call an r -edge in Γ ( r ) ( H ) blue if it is contained in at most | E ( F |-) 1 hyperedges of H .

More precisely, we will use the following simple corollary: for n ≥ s , there is an α = α r, s ( ) &lt; 1, such that ex ( r n, K ( r ) s ) ≤ α n r . This also holds for r = 2 by Tur´n's theorem. a

Claim 12. There exists a constant α = α r, ( | V ( F | ) ) &lt; 1 such that for any hyperedge h ∈ E ( H ) , the number of blue r -edges in Γ ( r ) ( h ) is at least (1 -α ) ( | h | r ) .

Fix a hyperedge h ∈ E ( H ) and consider the subhypergraph of Γ ( r ) ( h ) formed by non-blue r -edges. By the above argument, this subhypergraph of Γ ( r ) ( h ) is F -free. By Theorem 11 there exists a constant α = α r, ( | V ( F | ) ) &lt; 1 such that the number of non-blue r -edges in Γ ( r ) ( h ) is at most α ( | h | r ) , as | h |≥ | V ( F | ) . Thus, the number of blue r -edges in Γ ( r ) ( h ) is at least (1 -α ) ( | h | r ) . By applying Claim 12, we obtain the following inequality.

Proof of Claim 12. We first show that every copy of F in Γ ( r ) ( H ) contains a blue r -edge. Suppose otherwise for the sake of a contradiction. Then, by the definition of a blue r -edge, every r -edge in a copy of F is contained in at least | E ( F | ) hyperedges of H . Therefore, we can construct greedily a copy of a BergeF in H by choosing, for each r -edge f of F a unique hyperedge of H that contains f ; a contradiction.

$$\sum _ { h \in E ( \mathcal { H } ) } ( 1 - \alpha ) \binom { | h | } { r } \leq | \{ \text{blue $r$-edges in $\Gamma^{(r)}(\mathcal{H})$} \} | \cdot ( | E ( F ) | - 1 ) = O ( n ^ { r } ).$$

This implies that

$$\sum _ { h \in E ( \mathcal { H } ) } | h | ^ { r } = O ( n ^ { r } ) \\ \intertext { o f T h o o r m } 7$$

which proves the first part of Theorem 7.

It remains to prove the second part of Theorem 7. We may now assume that every hyperedge of H has size at least R ( r ) ( F F , ) and at most o n ( ).

Claim 13. The number of copies of F in Γ ( r ) ( H ) is o n ( | V ( F | ) ) .

Proof of Claim 13. Since H is BergeF -free, any copy of F in Γ ( r ) ( H ) has at least two r -edges contained in a common hyperedge h of H . Thus at least r +1 vertices of F are contained in h and | h |≥ r +1. Now let us estimate the number of vertex sets that can span a copy of cF as follows. First pick a hyperedge h of H , then pick r + 1 vertices in h , and then pick | V ( F |-) r -1 other vertices. Now, there are at most | V ( F | ) ! copies of F with the same vertex set. Thus

$$| \ast \nmid / | \quad \ast \nmid \text{www.source} \quad \nu, \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \rho \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nu \quad \nolimits \quad \quad \quad$$

Here we used the assumption | h | = ( ) as well as (1). o n

By the hypergraph removal lemma and Claim 13, there exists a collection R of o n ( r ) r -edges such that each copy of F in Γ ( r ) ( H ) contains at least one r -edge from R . Let R ⊆ R ′ be the r -edges in R that are blue, i.e., that are contained in at most | E ( F |-) 1 hyperedges of H . We now show that for any hyperedge h ∈ E ( H ), that every subset S ⊆ h of size R ( r ) ( F F , ) contains an r -edge from R ′ . Suppose otherwise, then every r -edge in Γ ( r ) ( S ) ∩R is not blue, i.e., is in at least | E ( F | ) hyperedges of H .

Let us color the r -edges in Γ ( r ) ( S ) \R red and the r -edges in Γ ( r ) ( S ) ∩ R green to get a 2-coloring of the r -edges of Γ ( r ) ( S ). Then there is a monochromatic copy of F in Γ ( r ) ( S ), as | S | = R ( r ) ( F F , ). Every copy of F in Γ ( r ) ( H ) has a hyperedge in R , so this monochromatic copy cannot be red; hence it is green. Thus every hyperedge of this copy of F is contained in at least | E ( F | ) hyperedges of H . This implies that we can find a BergeF in H by choosing, for each r -edge f of F a unique hyperedge of H that contains f ; a contradiction. Therefore, for any subset S of size R ( r ) ( F F , ) in a hyperedge h ∈ E ( H ) contains an r -edge from R ′ .

Claim 14. There exists a constant β = β r, ( | V ( F | ) ) &lt; 1 such that for any hyperedge h ∈ E ( H ) , the number of r -edges of R ′ in Γ ( r ) ( h ) is at least (1 -β ) ( | h | r ) .

Proof of Claim 14. Fix a hyperedge h ∈ E ( H ) and a subset S ⊆ h of size R ( r ) ( F F , ). By the argument above, Γ ( r ) ( S ) contains an r -edge from R ′ . Therefore, Γ ( r ) ( h ) \R ′ does not contain a clique of size R ( r ) ( F F , ). So, by Theorem 11, there is a constant β = β r, ( | V ( F | ) ) &lt; 1 such that Γ ( r ) ( h ) \R ′ contains at most β ( | h | r ) r -edges. Thus Γ ( r ) ( h ) ∩ R ′ contains at least (1 -β ) ( | h | r ) r -edges. By Claim 14,

$$\sum _ { h \in E ( \mathcal { H } ) } ( 1 - \beta ) \binom { | h | } { r } & \leq \sum _ { h \in E ( \mathcal { H } ) } \left ( \Gamma ^ { ( r ) } ( h ) \cap \mathcal { R } ^ { \prime } \right ) \\ & \leq | \mathcal { R } ^ { \prime } | \ ( | E ( \mathcal { F } ) | - 1 ) \\ & \leq | \mathcal { R } | \ ( | E ( \mathcal { F } ) | - 1 ) = o ( n ^ { r } ).$$

This implies that

$$\sum _ { h \in E ( \mathcal { H } ) } | h | ^ { r } = o ( n ^ { r } ), \\ \underset { 7 } { \text{ram } 7 }$$

which completes the proof of Theorem 7.

We finish this section with the proof of Corollary 8 (which immediately implies Corollary 9).

Proof of Corollary 8. Let us partition H into H ∪ H 1 2 , where H 1 consists of the hyperedges of size at most √ n and H 2 consists of the hyperedges of size greater than √ n . Then ∑ h ∈ E ( H 1 ) w h ( | | ) = o n ( r ) by Theorem 7, using the assumption that every hyperedge of H 1 has size at most √ n = ( ) and at least o n R ( r ) ( F F , ).

On the other hand, as w m ( ) ≤ o m ( r ) we have

$$\sum _ { h \in E ( \mathcal { H } _ { 2 } ) } w ( | h | ) \leq \sum _ { h \in E ( \mathcal { H } _ { 2 } ) } o ( | h | ^ { r } ) = o \left ( \sum _ { h \in E ( \mathcal { H } _ { 2 } ) } | h | ^ { r } \right ) = o ( n ^ { r } ). \\ \text{g these two bounds completes the proof.}$$

Adding these two bounds completes the proof.

## 4 Graph based hypergraphs

In this section we consider the problem of estimating the maximum number of hyperedges in a BergeF -free k -graph if the r -graph F itself is based on a (hyper)graph. First we observe that it is possible to extend a hypergraph F to a Berge k F in multiple steps.

Observation 15. For an r -graph F and k ≥ l ≥ r we have that the family of hypergraphs in Berge k F is isomorphic to the family of hypergraphs in Berge -Berge k l F .

This simple observation implies bounds when F is one particular Berge copy of a graph F 0 . An obvious choice is the expansion F + r 0 of F 0 . Recall that F + r 0 is obtained by adding r -2 new vertices to each edge of F 0 such that these new vertices are distinct for distinct edges (thus all the intersections of the hyperedges are inherited from the graph). Tur´ an problems for expansions have been widely studied; see [25] for a survey.

Obviously, for k ≤ r , the hypergraph F + r 0 is a Berge copy of F + k 0 . On the other hand, every Berge r F + k 0 is a Berge copy of F 0 . Thus

## Proposition 16. Let F 0 be a fixed graph and let k ≤ r . Then

$$\text{ex} _ { r } ( n, \text{Berge} _ { r } - F _ { 0 } ) \leq \text{ex} _ { r } ( n, \text{Berge} _ { r } - F _ { 0 } ^ { + k } ) \leq \text{ex} _ { r } ( n, F _ { 0 } ^ { + r } ).$$

In particular, for F 0 = K m , with m&gt;r and for n large enough, we know that the upper and lower bounds in the above proposition coincide, using a result of Pikhurko [27] and the following construction. Let us partition an n -element set V into m -1 parts such that the difference between the size of two parts is at most 1 and let the hyperedges be the r -sets that intersect every part in at most one vertex. This r -uniform hypergraph is called the Tur´ an hypergraph and is denoted by T r ( n, m -1). It is BergeK m -free, as a K m would have two vertices u and v in the same part by the pigeonhole principle, but there is no hyperedge containing both u and v .

Moreover, for any graph with chromatic number m &gt; r , the upper bound is asymptotically the same as the lower bound (given by T r ( n, m -1)) in the above proposition due to a result of Palmer, Tait, Timmons, and Wagner [26].

Corollary 17. Let F 0 be a fixed graph and let m = χ F ( 0 ) &gt; r &gt; k . Then

$$\exp _ { r } ( n, \text{Berge} _ { r } - F _ { 0 } ^ { + k } ) = ( 1 + o ( 1 ) ) | E ( T ^ { r } ( n, m - 1 ) |.$$

However, note that the bounds in Proposition 16 are far from each other for any given F 0 , if r is large enough. Indeed, ex ( r n, Berge r F 0 ) = O n ( 2 ) by a result of Gerbner and Palmer [15] while ex ( r n, F + r 0 ) = Ω( n r -1 ) if F 0 is not a star (by having all the r -sets containing a fixed vertex), and ex ( r n, F + r 0 ) = Ω( n r -2 ) if F 0 is a star (by having all the r -sets containing two fixed vertices).

Note that similar statements can be obtained for other specific Berge copies of F 0 . There are several different kinds of graph based hypergraphs (i.e., ways to extend a graph to a hypergraph) studied in [17], and each of them results in specific Berge copies of F 0 .

## 5 Generalized hypergraph Tur´n problems a

In this section we will prove Lemma 10. Our proof is based on the proof of Lemma 6. We use the following lemma from [11] (most of which already appears in [13]).

Lemma 18. Let G be a finite bipartite graph with parts A and B and let M be a maximum matching in G . Let B ′ denote the set of vertices in B that are incident to M . Then we can partition A into A 1 and A 2 and partition B ′ into B 1 and B 2 such that the vertices of A 1 are joined to the vertices of B 1 by edges of M and every neighbor of the vertices of A 2 is in B 2 . Moreover, every vertex in A 1 has a neighbor in B \ B ′ .

Proof of Lemma 10. Let H 0 be a BergeF -free r -graph on n vertices with the largest number of r -edges and consider the following auxiliary bipartite graph G . Part A consists of the hyperedges of H 0 and part B consists of their k -shadows. A vertex u ∈ A is adjacent to a vertex v ∈ B if and only if v ⊆ u . Let M be a maximum matching in G and let B ′ denote the set of vertices in B that are incident to M . By Lemma 18, we can partition A into A 1 and A 2 and partition B ′ into B 1 and B 2 such that the vertices of A 1 are joined to the vertices of B 1 by edges of M and every neighbor of the vertices of A 2 is in B 2 . Let H be the red-blue k -graph with red hyperedges B 1 and blue hyperedges B 2 . Then

$$\exp _ { r } ( n, \text{Berge} \mathcal { F } ) = | E ( \mathcal { H } _ { 0 } ) | = | A _ { 1 } | + | A _ { 2 } | \leq | B _ { 1 } | + | A _ { 2 } | \leq | B _ { 1 } | + N ( \mathcal { K } _ { r } ^ { ( k ) }, \mathcal { H } _ { b l u e } ) = g _ { r } ( \mathcal { H } ).$$

For the first inequality we used that that M joins vertices of A 1 to B 1 and for the second inequality we used that that for a vertex v ∈ A 2 , all its neighbors are in B 2 , which means all its k -subsets are in B 2 , thus there is a K ( k ) r on those r vertices.

Corollary 19. For any k -graph F and integers r, n we have

$$\text{ex} _ { k } ( n, \mathcal { K } _ { r } ^ { ( k ) }, \mathcal { F } ) \leq \text{ex} _ { r } ( n, \text{Berg} \prec \mathcal { F } ) \leq \text{ex} _ { k } ( n, \mathcal { K } _ { r } ^ { ( k ) }, \mathcal { F } ) + \text{ex} _ { k } ( n, \mathcal { F } ).$$

Note that the lower bound is given by replacing each K ( k ) r in an F -free k -graph by an r -edge. Also note that Corollary 19 is very useful for graph based Berge hypergraphs, given that there are several results concerning the Tur´ an and the generalized Tur´ an problems. In the hypergraph case, much less is known about the Tur´n numbers. a The situation is even worse for the generalized hypergraph Tur´n problems, where we are aware of only a a few such results due to Ma, Yuan and Zhang [24] and Xu, Zhang and Ge [30]. Therefore, Corollary 19 is more useful in giving bounds for the generalized hypergraph Tur´n problem, a i.e., ex ( k n, H F , ). For example, combining Corollary 17 and Corollary 19 with the fact that ex ( k n, F + k 0 ) = O n ( k ) = o n ( r ) gives

Corollary 20. Let F 0 be a graph and let m = χ F ( 0 ) &gt; r &gt; k . Then

$$\exp _ { k } ( n, \mathcal { K } _ { r } ^ { ( k ) }, F _ { 0 } ^ { + k } ) = ( 1 + o ( 1 ) ) | E ( T ^ { r } ( n, m - 1 ) |.$$

## 6 Concluding remarks

Let us note that one can define Berge copies of other discrete structures in a similar manner to hypergraphs. Assume that F is a subset of an underlying set X and there is a set Y with a partial relation ≤ between elements of X and Y . Then a Berge copy of F is obtained

by replacing every element x of F by an element of y ∈ Y with x ≤ y in such a way that we replace the elements of X with distinct elements of Y . In this paper, X is the system of k -subsets of a finite set, Y consists of subsets of size at least k of a potentially larger underlying finite set, and the relation ≤ corresponds to inclusion. To give another example, Anstee and Salazar [3] considered 0-1 matrices with the relation being 'larger or equal in every entry'.

There are many other settings where defining Berge copies makes sense, including permutations, vertex ordered graphs, edge ordered graphs, Boolean functions, et cetera. Lemma 18 can be used in all these settings to connect the problem of counting the elements of Y in a BergeF -free subset of Y to the following problem: what is the maximum number of elements y of Y such that every x ∈ X with x ≤ y belongs to S , where S is an F -free subset of X ?

## References

- [1] N. Alon and C. Shikhelman. Many T copies in H-free graphs. Journal of Combinatorial Theory, Series B , 121 :146-172, 2016.
- [2] N. Alon and A. Shapira. On an extremal hypergraph problem of Brown, Erd˝s and S´s. p o Combinatorica , 26 (6), 627-645, 2006.
- [3] R. Anstee and S. Salazar. Forbidden Berge hypergraphs. Electronic Journal of Combinatorics, 24(1), 2017. P1.59.
- [4] M. Axenovich, A. Gy´rf´s. A note on Ramsey numbers for Bergea a G hypergraphs, arXiv preprint arXiv:1807.10062, 2018.
- [5] C. Berge. Graphs and hypergraphs. North-Holland Pub. Co., 1973.
- [6] D. de Caen. Extension of a theorem of Moon and Moser on complete subgraphs. Ars Combinatoria, 16, 5-10, 1983.
- [7] S. English, D. Gerbner, A. Methuku, C. Palmer. On the weight of BergeF -free hypergraphs, manuscript
- [8] S. English, D. Gerbner, A. Methuku and M. Tait. Linearity of Saturation for Berge Hypergraphs, arXiv preprint arXiv:1807.06947 (2018).
- [9] S. English, N. Graber, P. Kirkpatrick, A. Methuku, E.C. Sullivan, Saturation of Berge hypergraphs. (2017). arXiv preprint arXiv:1710.03735.
- [10] Z. F¨redi, A. Kostochka, R. Luo. Avoiding long Berge cycles. u Journal of Combinatorial Theory, Series B , to appear
- [11] D. Gerbner. A note on the Tur´ an number of a Berge odd cycle. arXiv preprint arXiv:1903.01002 (2019).

| [12]   | D. Gerbner, A. Methuku, G. Omidi, M. Vizer Ramsey problems for Berge hypergraphs. (2018) arXiv preprint arXiv:1808.10434.                                             |
|--------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [13]   | D. Gerbner, A. Methuku, C. Palmer. General lemmas for Berge-Tur´n a hypergraph prob- lems. arXiv preprint arXiv:1808.10842 (2018).                                    |
| [14]   | D. Gerbner, A. Methuku, and M. Vizer. Asymptotics for the Tur´n a number of Berge- K 2 ,t . Journal of Combinatorial Theory, Series B , to appear                     |
| [15]   | D. Gerbner, C. Palmer. Extremal Results for Berge Hypergraphs. SIAM Journal on Discrete Mathematics , 31 .4: 2314-2327, 2017.                                         |
| [16]   | D. Gerbner, C. Palmer. Counting copies of a fixed subgraph in F -free graphs. arXiv preprint arXiv:1805.07520 (2018).                                                 |
| [17]   | D. Gerbner, B. Patk´s. o Extremal Finite Set Theory, 1st Edition, CRC Press, 2018.                                                                                    |
| [18]   | D. Gr´sz, o A. Methuku, C. Tompkins. Uniformity thresholds for the asymptotic size of extremal Berge- F -free hypergraphs. arXiv preprint arXiv:1803.01953 (2018).    |
| [19]   | E. Gy˝ri. o Triangle-free hypergraphs. Combinatorics, Probability and Computing , 15(1- 2), 185-191, 2006.                                                            |
| [20]   | E. Gy˝ri, o G. Y. Katona, N. Lemons. Hypergraph extensions of the Erd˝s-Gallai o theorem. European Journal of Combinatorics , 58, 238-246, 2016.                      |
| [21]   | E. Gy˝ri, o N. Lemons. Hypergraphs with no cycle of a given length. Combinatorics, Probability and Computing , 21(1-2):193-201, 2012.                                 |
| [22]   | L. Kang, L. Liu, L. Lu, Z. Wang, The extremal p -spectral radius of Berge-hypergraphs. (2018). arXiv preprint arXiv:1812.06032.                                       |
| [23]   | F. Lazebnik, J. Verstra¨te. e On hypergraphs of girth five. The electronic journal of com- binatorics, (2003) 10(1), 25.                                              |
| [24]   | J. Ma, X. Yuan, and M. Zhang. Some extremal results on complete degenerate hyper- graphs. Journal of Combinatorial Theory, Series A, 154:598-609, 2018.               |
| [25]   | D. Mubayi, J Verstra¨te. e A survey of Tur´n a problems for expansions. Recent Trends in Combinatorics, 117-143, 2016.                                                |
| [26]   | C. Palmer, M. Tait, C. Timmons, A.Z. Wagner, Tur´n a numbers for Berge-hypergraphs and related extremal problems. (2017). arXiv preprint arXiv:1706.04249.            |
| [27]   | O. Pikhurko. Exact computation of the hypergraph Tur´n a function for expanded com- plete 2-graphs. Journal of Combinatorial Theory, Series B , 103.2: 220-225, 2013. |

- [28] N. Salia, C. Tompkins, Z. Wang, O. Zamora. Ramsey numbers of Berge-hypergraphs and related structures. arXiv preprint arXiv:1808.09863, 2018.
- [29] C. Timmons, On r -uniform linear hypergraphs with no BergeK 2 ,t . arXiv preprint arXiv:1609.03401 (2016).
- [30] Z. Xu, T. Zhang, G. Ge. Some extremal results on hypergraph Tur´n problems. arXiv a preprint arXiv:1905.01685, 2019.
- [31] A. A. Zykov. On some properties of linear complexes. Matematicheskii sbornik , 66 (2):163-188, 1949.
Martin Balko Daniel Gerbner Dong Yeap Kang Younjin Kim Cory Palmer
Hypergraph based Berge hypergraphs
Fix a hypergraph $\mathcal{F}$. A hypergraph $\mathcal{H}$ is called a {\it
Berge copy of $\mathcal{F}$} or {\it Berge-$\mathcal{F}$} if we can choose a
subset of each hyperedge of $\mathcal{H}$ to obtain a copy of $\mathcal{F}$. A
hypergraph $\mathcal{H}$ is {\it Berge-$\mathcal{F}$-free} if it does not
contain a subhypergraph which is Berge copy of $\mathcal{F}$. This is a
generalization of the usual, graph based Berge hypergraphs, where $\mathcal{F}$
is a graph.
  In this paper, we study extremal properties of hypergraph based Berge
hypergraphs and generalize several results from the graph based setting. In
particular, we show that for any $r$-uniform hypregraph $\mathcal{F}$, the sum
of the sizes of the hyperedges of a (not necessarily uniform)
Berge-$\mathcal{F}$-free hypergraph $\mathcal{H}$ on $n$ vertices is $o(n^r)$
when all the hyperedges of $\mathcal{H}$ are large enough. We also give a
connection between hypergraph based Berge hypergraphs and generalized
hypergraph Tur\'an problems.