1 Introduction

Given a hypergraph \({{\mathcal {H}}}\) and a graph G, we say that \({{\mathcal {H}}}\) is a Berge copy of G (in short: a Berge-G) if there is a bijection between the hyperedges of \({{\mathcal {H}}}\) and the edges of G such that each hyperedge contains its image.

Berge hypergraphs were introduced by Gerbner and Palmer [8] as a generalization of the notion of hypergraph cycles due to Berge.

A closely connected area is that of generalized Turán problems. Given graphs H and G, we let \({{\mathcal {N}}}(H,G)\) denote the number of copies of H in G. Let \(\text {ex}(n,H,F):=\max \{{{\mathcal {N}}}(H,G): G{ isan}n\text{-vertex } \text{ F-free } \text{ graph }\}\). The sytematic study of this topic was initiated by Alon and Shikhelman [1] after several sporadic results.

The connection between Berge–Turán problems and generalized Turán problems was established by Gerbner and Palmer [9], who showed that \(\textrm{ex}(n,K_k,F)\le \textrm{ex}_k(n,Berge- F)\le \textrm{ex}(n,K_k,F)+\textrm{ex}(n,F)\). The upper bound was strengthened by Füredi, Kostochka, and Luo [3] and independently by Gerbner, Methuku and Palmer [11]. To state this result, we need some definition.

A blue–red graph G is a graph with each edge colored blue or red. We denote by \(G_{blue}\) the subgraph consisting of the blue edges and by \(G_{red}\) the subgraph consisting of the red edges. We say that a blue–red graph G is F-free if G does not contain F (here we do not care about the colors). Given an integer \(k\ge 3\), let \(g(G):={{\mathcal {N}}}(K_k,G_{blue})+|E(G_{red})|\). Let \(\text {ex}^{{\mathrm col}}(n,F):=\max \{g(G): G{ isan}n\text{-vertex } \text{ F-free } \text{ graph }\}\).

Lemma 1.1

([3, 11]) Let F be a graph. For every n-vertex Berge-F-free k-uniform hypergraph \({{\mathcal {H}}}\), there is a partition of the hyperedges to \({{\mathcal {H}}}_1\) and \({{\mathcal {H}}}_2\) and a blue-red graph G on the same vertex set such that the vertices of each hyperedge of \({{\mathcal {H}}}_1\) induce a blue \(K_k\) in G and there is a bijection between the hyperedges in \({{\mathcal {H}}}_2\) and the red edges in G such that each hyperedge contains its image. In particular, for any F we have \(\textrm{ex}_k(n,Berge- F)\le \textrm{ex}^{{\mathrm col}}(n,F)\).

A hypergraph Turán problem is called degenerate if the order of magnitude of the extremal function is smaller than the largest possible, i.e. smaller than \(n^k\) in our case. By the above bounds, \(\textrm{ex}_k(n,Berge- F)=o(n^k)\) if and only if \(\textrm{ex}(n,K_k,F)=o(n^k)\), which happens if and only if \(\chi (F)\le k\) by a result of Alon and Shikhelman [1]. Another result of Alon and Shikhelman [1] shows that if \(\chi (F)=r+1>k\), then \(\textrm{ex}(n,K_k,F)=(1+o(1)){{\mathcal {N}}}(K_k,T(n,r))=(1+o(1))\left( {\begin{array}{c}r\\ k\end{array}}\right) \left( \frac{n}{r}\right) ^k\). Here T(n, r) denotes the Turán graph, which is the complete r-partite n-vertex graph with each part of order \(\lfloor n/r\rfloor \) or \(\lceil n/r\rceil \).

In the non-degenerate case, for \(k\ge 3\) we have that \(\textrm{ex}(n,F)=O(n^2)=o(\textrm{ex}(n,K_k,F))\), thus \(\textrm{ex}_k(n,Berge- F)=(1+o(1)) \textrm{ex}(n,K_k,F)\). We believe that a stronger connection also holds.

Conjecture 1.2

If \(\chi (F)>k\) and n is sufficiently large, then \(\textrm{ex}_k(n,Berge- F)=\textrm{ex}(n,K_k,F)\).

The above conjecture is known to hold in the case F has a color-critical edge (an edge whose deletion decreases the chromatic number) due to an unpublished result of Alon and Pikhurko. The k-uniform expansion \(F^{+k}\) of a graph F is the specific k-uniform Berge copy that contains the most vertices, i.e., the \(k-2\) vertices added to each edge of F are distinct for different edges, and distinct from the vertices of F. Pikhurko [14] showed that for \(r\ge k\), the Turán number of \(K_{r+1}^{+k}\) is equal to \({{\mathcal {N}}}(K_k,T(n,r))\) if n is sufficiently large. According to the survey [13] on expansions, Alon and Pikhurko observed that Pikhurko’s proof generalizes to the case F is an \((r+1)\)-chromatic graph with a color-critical edge. Simpler proofs can be found for \(ex_k(n, Berge -K_{r+1})\) in [11], and for \(\textrm{ex}_k(n,Berge- F)\) in [7].

In general, the above observations imply that \(\textrm{ex}_k(n,Berge- F)= \textrm{ex}(n,K_k,F)+O(n^2)\). This was improved to \(\textrm{ex}_k(n,Berge- F)= \textrm{ex}(n,K_k,F)+o(n^2)\) in [4]. We further improve this bound in our next result.

Theorem 1.3

\(\textrm{ex}_k(n,Berge- F)= \textrm{ex}(n,K_k,F)+O(1)\).

We show that Conjecture 1.2 holds if F contains a color-critical vertex (a vertex whose deletion decreases the chromatic number).

Theorem 1.4

Let \(\chi (F)>k\) and assume that F contains a color-critical vertex. Then for sufficiently large n we have \(\textrm{ex}_k(n,Berge- F)=\textrm{ex}(n,K_k,F)\).

We show that Conjecture 1.2 holds in the 3- and 4-uniform case. Furthermore, it holds in any uniformity if the chromatic number of F is sufficiently large.

Theorem 1.5

(i) Let \(\chi (F)>k\) and \(k\le 4\). Then \(\textrm{ex}_k(n,Berge- F)=\textrm{ex}(n,K_k,F)\) for sufficiently large n.

(ii) For any k there exists \(r_0=r_0(k)\) such that if \(\chi (F)=r+1\ge r_0\), then \(\textrm{ex}_k(n,Berge- F)=\textrm{ex}(n,K_k,F)\) for sufficiently large n.

Recall that if \(\chi (F)>k\), then the asymptotics of \(\textrm{ex}(n,K_k,F)\) is known, thus the asymptotics of \(\textrm{ex}_k(n,Berge- F)\) is known. Even if Conjecture 1.2 is true, it only improves the asymptotic result to an exact result in the few cases when \(\textrm{ex}(n,K_k,F)\) is known. Besides the case where F has a color-critical edge, we are aware only of the following results. Let \(2K_{r+1}\) denote two vertex-disjoint copies of \(K_{r+1}\) and \(B_{r,1}\) denote two copies of \(K_{r+1}\) sharing exactly one vertex. Gerbner and Patkós [10] determined \(\textrm{ex}(n,K_k,2K_{r+1})\) and \(\textrm{ex}(n,K_k,B_{r+1,1})\). The first of these results was extended by Gerbner [6] to \(\textrm{ex}(n,K_k,F)\) in the case each component of F either has chromatic number \(r+1\) and contains a color-critical edge, or has chromatic number at most r. Gerbner [6] also determined \(\textrm{ex}(n,K_k,Q_{r+1})\) for a class of graphs \(Q_r\) that we do not define here and most values of k.

For the Berge copies of the graphs mentioned above, we can show that Conjecture 1.2 holds. In fact, \(B_{r+1,1}\) and \(Q_r\) each has a color-critical vertex, thus we already dealt with them in Theorem 1.4. Let \(K_i+T(n-i,r)\) denote the graph we obtain by adding i vertices to \(T(n-i,r)\) and joining them to every vertex.

Theorem 1.6

Let us assume that F consists of s components with chromatic number \(r+1\), each with a color-critical edge, and any number of components with chromatic number at most r. Then \(\textrm{ex}_k(n, Berge- F)={{\mathcal {N}}}(K_k,K_{s-1}+T(n-s+1,r))\).

To prove the above theorems, we use the following results on the structure of the extremal graphs that are interesting on their own. Let us denote by \(\sigma (F)\) the smallest possible order of a color class in a \(\chi (F)\)-coloring of F.

Theorem 1.7

Let \(\chi (F)=r+1>k>2\) and G be an n-vertex F-free blue-red graph with \(g(G)=\textrm{ex}^{{\mathrm col}}(n,F)\). Then we have the following.

(i) For every vertex u of G we have that the number of blue k-cliques plus the number of red edges containing u is at least \((1+o(1))\left( {\begin{array}{c}r-1\\ k-1\end{array}}\right) (\frac{n}{r})^{k-1}\).

(ii) Let \(\varepsilon >0\) be sufficiently small. Then there exist an r-partition of V(G) to \(A_1,\dots , A_r\), a constant \(K=K(F,\varepsilon )\) and a set B of at most \(K(\sigma (F)-1)\) vertices such that we have the following. For each i we have\(|A_i|=(1-o(1))n/r\), each red edge is between two elements of B, every vertex of B is adjacent to at least \(\varepsilon n\) vertices in each part and to at least cn vertices in all but one parts for some constant \(c=c(F)\). Furthermore, every vertex of \(A_i\setminus B\) is adjacent to at most \(\varepsilon n\) vertices in \(A_i\) and all but at most \(\varepsilon (2r^k+1) n\) vertices in \(A_j\) with \(j\ne i\).

(iii) Let \({{\mathcal {H}}}\) be an n-vertex k-uniform Berge-F-free hypergraph with \(\textrm{ex}_k(n,Berge- F)\) hyperedges. Then every vertex of \({{\mathcal {H}}}\) is contained in at least \((1+o(1))\left( {\begin{array}{c}r-1\\ k-1\end{array}}\right) (\frac{n}{r})^{k-1}\) hyperedges.

2 Proofs

We will use the following stability result due to Ma and Qiu [12].

Theorem 2.1

(Ma, Qiu [12]) Let \(\chi (F)>k\) and let G be an n-vertex F-free graph that contains \(\textrm{ex}(n,K_k,F)-o(n^k)\) copies of \(K_k\). Then G can be turned into T(n, r) by adding and removing \(o(n^2)\) edges.

Let us start with the proof of Theorem 1.7.

We note that the analogous results for \(\textrm{ex}(n,K_k,F)\) can be found in [12]. Generalizations to some other graphs in place of \(K_k\) can be found in [5] for (i) and in [6] for (ii). Our proof follows the proofs in [5] and [6].

Proof of Theorem 1.7

Observe first that there are O(n) red edges incident to a vertex, thus their number is part of the lower order error term in (i) and (ii). In particular, G contains at least \(\textrm{ex}(n,K_k,F)-\textrm{ex}(n,F)\) blue copies of \(K_k\), thus \(G_{blue}\) can be transformed to a complete r-partite graph by adding and removing \(o(n^2)\) edges by Theorem 2.1. Note that there may be several different such complete r-partite graphs on the vertex set V(G) that can be obtained this way, we pick one with the smallest number of edges inside the parts and denote it by \(G'\). It is easy to see that each part has order \((1-o(1))n/r\), otherwise the number of blue cliques is at most \(\left( {\begin{array}{c}r\\ k\end{array}}\right) \left( \frac{n}{r}\right) ^k-\Theta (n^k)\). Let \(A_1,\dots ,A_r\) denote the parts and let f(v) denote the number of red edges and blue k-cliques incident to v that are not in \(G'\). Then we have \(\sum _{v\in V(G)}f(v)=o(n^k)\). Consider a set S of |V(F)| vertices in \(A_1\) such that \(\sum _{v\in S}f(v)\) is minimal. Then by averaging \(\sum _{v\in S}f(v)\le \frac{|S|}{|V_1|}\sum _{v\in V_1}f(v)=o(n^{k-1})\).

Let us consider blue k-cliques that contain exactly one vertex s of S, and the other vertices are in the common neighborhood of S in \(G_{blue}\). Let \(d_G(k,S)\) denote the number of such blue k-cliques. Observe that each vertex of S is in \(\frac{d_G(k,S)}{|S|}+o(n^{k-1}\) such blue k-cliques. Clearly \(\frac{d_{T(n,r)}(k,S)}{|S|}=(1+o(1)) \left( {\begin{array}{c}r-1\\ k-1\end{array}}\right) (\frac{n}{r})^{k-1}\).

Let x denote the number of blue k-cliques and red edges that contain u and a vertex from S, then \(x=O(n^{k-2})\). Now we apply a variant of Zykov’s symmetrization [15]. For an arbitrary vertex u, let \(d_G(k,u)\) denote the number of blue k-cliques that contain u. If \(d_G(k,u)<\frac{d_G(k,S)}{|S|}-x-n\), then we remove the edges incident to u from G. Then for every vertex v that is connected to each vertex of S with a blue edge, we connect u to v with a blue edge. For every vertex w that is connected to each vertex of S with a red edge, we connect u to w with a red edge. This way we do not create any copy of F, as the copy should contain u, but u could be replaced by any vertex of S that is not already in the copy, to create a copy of F in G. We removed at most \(d_G(k,u)+n-1\) blue k-cliqes and red edges, but added at least \(\frac{d_G(k,S)}{|S|}-x\) blue k-cliques, contradicting the choice of G as the F-free blue-red graph with \(g(G)=\textrm{ex}^{{\mathrm col}}(n,F)\).

Therefore, we have that the blue k-cliques plus the red edges containing u is at least

$$\begin{aligned}\frac{d_G(k,S)}{|S|}-x\ge \frac{d_{T(n,r)}(k,S)}{|S|}-\sum _{v\in S}f(v)-x=\frac{d_{T(n,r)}(k,S)}{|S|}-o(n^{k-1}).\end{aligned}$$

This completes the proof of (i).

The proof of (iii) is similar. We use the blue-red graph G obtained by Lemma 1.1. Note that g(G) may be smaller than \(\textrm{ex}^{{\mathrm col}}(n,F)\), otherwise this statement would follow from (i). We pick S the same way, but instead of blue k-cliques, we count the hyperedges containing u, let \(d_{{{\mathcal {H}}}}(k,u)\) denote their number, and analogously, let \(d_{{{\mathcal {H}}}}(k,S)\) denote the number of hyperedges containing exactly one vertex of S, such that the other vertices are in the common neighborhood of S in \(G_{blue}\). Let y denote the number of hyperedges that contain u and a vertex from S. If \(d_{{\mathcal {H}}}(k,u)<\frac{d_{{\mathcal {H}}}(k,S)}{|S|}-y\), then we remove the hyperedges containing u and for every hyperedge H that contains exactly one vertex \(v\in S\), we add \((H\setminus \{v\})\cup \{u\}\) as a hyperedge. Then the same reasoning as above completes the proof of (iii).

Let B denote the set of vertices that are adjacent to at least \(\varepsilon n\) vertices in their part \(A_i\). Note that by the choice of \(G'\), vertices of B are incident to at least \(\varepsilon n\) vertices in each other part. Let \(B_i=B\cap A_i\). \(\square \)

Claim 2.2

There is a K depending on \(\varepsilon \) and F such that \(|B|\le K(\sigma (F)-1)\).

The analogous claim for uncolored graphs \(G_0\) with \(\textrm{ex}(n,K_k,F)\) copies of \(K_k\) is Claim 4.2 in [12]. However, the proof of that claim does not use that \(G_0\) is extremal, only that \(G_0\) contains \(\textrm{ex}(n,K_k,F)-o(n^k)\) copies of \(K_k\). As this holds for G as well, the claim follows. We also present a sketch of the proof.

Proof

(Sketch of proof) We denote by G(v) the subgraph of G on the neighborhood of a vertex \(v\in B\). Recall that we have \(\Theta (n)\) vertices in each \(A_i(v)=A_i\cap V(G')\). There are \(o(n^2)\) edges are missing between parts in G, thus there are \(o(n^2)\) edges are missing between sets \(A_i(v)\) and \(A_j(v)\). We can apply the supersaturation theorem of Erdős and Simonovits [2] to show that there are at least \(cn^{|V(F')|}\) copies in G(v) of the complete r-partite graph \(F'\) with parts of order |V(F)| for some constant c.

Let us define an auxiliary bipartite graph with one part being B and the other part being the set of copies of \(F'\). We add an edge if the copy of \(F'\) is in the neighborhood of the vertex. Every copy of \(F'\) has at most \(\sigma (F)-1\) neighbors here because G is F-free. On the other hand, every vertex \(v\in B\) has at least \(cn^{|V(F')|}\) neighbors by the above argument. Clearly there are at most \(n^{|V(F')|}\) copies of \(F'\) in G, hence \(|B|cn^{|V(F')|}\le (\sigma (F)-1)n^{|V(F')|}\). \(\square \)

Consider now the set \(U_i\) of vertices v such that \(v\in A_i{\setminus } B\) is adjacent to less than \(|A_j|-\varepsilon (2r^k+1) n\) vertices of some \(A_j\). As there are \(o(n^2)\) edges missing between parts, we have that \(|U_i|=o(n)\).

Claim 2.3

For each i we have that \(U_i=\emptyset \).

Proof

(Proof of Claim) Let \(V_i=A_i\setminus (B\cap U_i)\), then we have that \(|V_i|\ge |A_i|-\varepsilon n\). Observe that each vertex of \(V_i\) is adjacent to all but at most \(\varepsilon (2r^k+1) n\) vertices of \(A_j\) for every \(j\ne i\). Therefore, for a set S of c vertices in \(V_i\), the common neighborhood of the vertices of S contains all but at most \(\varepsilon c(2r^k+1) n\) vertices of \(A_j\).

Let us delete the edges from each \(v\in U_i\) to \(A_i\) and connect v to each vertex of each \(V_j\), \(j\ne i\) with a blue edge. We claim that the resulting graph \(G''\) is F-free. Indeed, consider a copy \(F_0\) of F with the smallest number of vertices in \(U_i\). Clearly \(F_0\) contains a vertex \(v\in U_i\), as all the new edges are incident to such a vertex. Let Q be the set of vertices in \(F_0\) that are adjacent to v in \(G'\). They are each from \(\cup _{j\ne i}V_j\). Their common neighborhood in \(V_i\) is of order \(\frac{n}{r}-o(n)\). Therefore, at least one of the common neighbors is not in \(F_0\), thus we can replace v with that vertex to obtain another copy of F with less vertices from \(\cup _{i=1}^r U_i\), a contradiction.

We deleted at most \(\varepsilon n^{k-1}\) blue k-cliques and red edges for each vertex \(v\in U_i\), since they each contain one of the less than \(\epsilon n\) edges incident to v inside \(U_i\). We claim that we added more than \(\varepsilon n^{k-1}\) blue k-cliques. We consider only those blue k-cliques that contain v, a new neighbor of v in \(V_j\) with \(j\ne i\), and \(k-2\) other vertices from other sets \(V_\ell \). We have at least \(2r^k\varepsilon n\) choices for the neighbor and at least \(n/r-\varepsilon n\) choices for the other vertices. If \(\varepsilon \) is sufficiently small, then indeed, we obtain more than \(\varepsilon n^{k-1}\) new blue k-cliques, thus \(g(G'')>g(G')\), a contradiction unless \(U_i\) is empty.

Now we show that there is a constant \(c=c(F)\) such that each vertex is adjacent to at least cn vertices in all but one parts. Assume that v is adjacent to less than cn vertices in \(A_1\) and also in \(A_2\). Then the number of blue cliques containing v is at most \(\left( {\begin{array}{c}r-2\\ k-1\end{array}}\right) (\frac{n}{r})^{k-1}+2c\left( {\begin{array}{c}r-2\\ k-2\end{array}}\right) (\frac{n}{r})^{k-2}n+4c^2n^2\left( {\begin{array}{c}r-2\\ k-3\end{array}}\right) (\frac{n}{r})^{k-3}\), contradiction to (i) if c is small enough.

It is left to show that each red edge is between vertices in B. Assume that \(u\not \in B\) and uv is a red edge. Let us change its color to blue. We will find more than one new blue k-clique greedily. We can assume without loss of generality that \(u\in A_1\) and v is in either \(A_1\) or in \(A_2\). Let us observe that u and v have at least \(cn-\varepsilon (2r^k+2) n\) common neighbors in \(G_{blue}\) inside \(V_3\), since u is adjacent to all but at most \(\varepsilon (2r^k+2) n\) vertices of \(V_3\) and v is incident to at least cn vertices of \(V_3\). We pick one of these common neighbors w. These three vertices have at least \(cn-2\varepsilon (2r^k+2) n\) common neighbors in \(G_{blue}\) inside \(V_4\), since the neighborhood of u and w each avoid at most \(\varepsilon (2r^k+2) n\) of the at least cn neighbors of v in \(V_4\). We pick one of them, and so on. We can pick k vertices if \(cn-(k-2)\varepsilon (2r^k+2) n>0\), which holds if \(\varepsilon \) is small enough. Clearly we can pick more than one blue k-clique this way, completing the proof of (ii).

\(\square \)

Theorem 1.3 is easily implied by (ii) of Theorem 1.7, since in an F-free n-vertex blue-red graph, the number of blue k-cliques is at most \(\textrm{ex}(n,K_k,F)\), while the number of red edges inside B is O(1). Theorem 1.4 is also implied by (ii) of Theorem 1.7, since a color-critical vertex means that \(\sigma (F)=1\), thus \(|B|=0\), hence there are no red edges.

Let us continue with the proof of Theorem 1.5. Recall that it states that if \(\chi (F)>k\) and \(k\le 4\) or if \(\chi (F)\) is sufficiently large, then Conjecture 1.2 holds.

Proof of Theorem 1.5

Our aim is to show that there is no red edge in G as this implies the statement of the theorem. Let \(\chi (F)=r+1\). We will use Lemma 1.1. Let G be a blue-red F-free graph with \(g(G)=\textrm{ex}^{{\mathrm col}}(n,F)\). Assume that there is a red edge uv in G and apply now (ii) of Theorem 1.7. We obtain a partition of V(G) to \(A_1,\dots , A_r\) with \(|A_i|=(1+o(1))n/r\) such that there are o(n) edges inside parts, and there is a set B of vertices with \(|B|=o(n)\) such that each vertex outside B is adjacent to all but o(n) vertices in each other part.

Assume that u and v have \(\Omega (n)\) common neighbors in at least \(k-2\) of the sets \(A_1,\dots ,A_r\), say \(A_1,\dots ,A_{k-2}\). Then at least \(\Omega (n)\) of those vertices are not in B, we will use only those vertices. We pick a common neighbor in \(A_1{\setminus } B\), then it has \(\Omega (n)\) common neighbor with u and v in \(A_2\). Therefore, we can pick a common neighbor in \(A_2\setminus B\), and so on. The resulting cliques do not contain any vertex of B, thus by turning uv blue, we obtain multiple blue k-cliques, thus g(G) increases, a contradiction.

We obtained that u and v have \(\Omega (n)\) common neighbors in at most \(k-3\) of the sets \(A_i\), say \(A_1,\dots , A_{k-3}\). In the remaining \(r-k+3\) sets \(A_i\), they have o(n) common neighbors, thus at least one of them, say u has at most \((1+o(1))(r-k+3)n/2r\) neighbors in \(A_{k-2}\cup \dots \cup A_r\). Consider now the number of blue k-cliques containing u. There are \(o(n^{k-1})\) blue k-cliques that contain u and an edge inside an \(A_i\) that is not incident to u. Therefore, we can focus on those blue k-cliques that contain u, and the other \(k-1\) vertices are from different parts.

Let K be such a blue k-clique and assume that K contains i vertices from \(A_1,\dots ,A_{k-3}\). There are at most \((1+o(1))\left( {\begin{array}{c}k-3\\ i\end{array}}\right) \left( \frac{n}{r}\right) ^{i}\) ways to pick such an i-set. For the remaining \(k-1-i\) vertices of K, we have to pick one neighbor of u from \(k-1-i\) of the remaining \(r-k+3\) sets, and in total u has \((1+o(1))(r-k+3)n/2r\) neighbors in those sets. Then the number of \((k-1-i)\)-cliques is at most \(\textrm{ex}((1+o(1))(r-k+3)n/2r,K_{k-1-i},K_{r-k+4})\). A theorem of Zykov [15] states that \(\textrm{ex}(n,K_s,K_t)={{\mathcal {N}}}(K_s,T(n,t-1))=(1+o(1))\left( {\begin{array}{c}t-1\\ s\end{array}}\right) \left( \frac{n}{t-1}\right) ^{s}\), thus there are at most \((1+o(1))\left( {\begin{array}{c}r-k+3\\ k-i-1\end{array}}\right) \left( \frac{n}{2r}\right) ^{k-1-i}\) ways to pick the \((k-1-i)\)-clique.

We apply (i) of Theorem 1.7, thus we know that each vertex v is in at least \((1+o(1))\left( {\begin{array}{c}r-1\\ k-1\end{array}}\right) (\frac{n}{r})^{k-1}\) blue k-cliques. Therefore,

$$\begin{aligned} (1+o(1))\sum _{i=0}^{k-3}\left( {\begin{array}{c}k-3\\ i\end{array}}\right) \left( \frac{n}{r}\right) ^{i} \left( {\begin{array}{c}r-k+3\\ k-i-1\end{array}}\right) \left( \frac{n}{2r}\right) ^{k-1-i}\ge (1+o(1)) \left( {\begin{array}{c}r-1\\ k-1\end{array}}\right) \left( \frac{n}{r}\right) ^{k-1}. \end{aligned}$$

This holds only if

$$\begin{aligned} \sum _{i=0}^{k-3}\left( {\begin{array}{c}k-3\\ i\end{array}}\right) \left( {\begin{array}{c}r-k+3\\ k-i-1\end{array}}\right) \left( \frac{1}{2}\right) ^{k-1-i}\ge \left( {\begin{array}{c}r-1\\ k-1\end{array}}\right) . \end{aligned}$$
(1)

If \(k=3\), then \(i=0\) and \(\left( {\begin{array}{c}r\\ k-1\end{array}}\right) /4\ge \left( {\begin{array}{c}r-1\\ k-1\end{array}}\right) \), a contradiction.

If \(k=4\), then (1) gives \(\left( {\begin{array}{c}r-1\\ 3\end{array}}\right) \left( \frac{1}{2}\right) ^{3}+\left( {\begin{array}{c}r-1\\ 2\end{array}}\right) \left( \frac{1}{2}\right) ^{2}\ge \left( {\begin{array}{c}r-1\\ 3\end{array}}\right) \). This is equivalent to \((r-\frac{27}{7})(r-2)(r-1)\le 0\), a contradiction to \(r\ge k=4\). This completes the proof of (i).

There are several other pairs (k, r) when we could obtain a contradiction a similar way. However, if \(k=r\), the left hand side has a term \(\left( {\begin{array}{c}k-3\\ k-4\end{array}}\right) /8\). If \(k\ge 11\), then this term alone is larger than the right hand side, thus we do not have a contradiction in general. In fact, one can easily see that for \(k=r=5\) we do not obtain any contradiction. On the other hand, if k is fixed and r grows, there is only one term on the left hand side of (1) of order \(r^{k-1}\), and it is \(r^{k-1}/2^{k-1}(k-1)!\). Since the leading term on the right hand side is \(r^{k-1}/(k-1)!\), we obtain a contradiction for r large enough, proving (ii). \(\square \)

Let us continue with the proof of Theorem 1.6 that we restate here for convenience.

Theorem

Let us assume that F consists of s components with chromatic number \(r+1\), each with a color-critical edge, and any number of components with chromatic number at most r. Then \(\textrm{ex}_k(n, Berge- F)={{\mathcal {N}}}(K_k,K_{s-1}+T(n-s+1,r))\).

The corresponding generalized Turán results are proved in [6] and we will extend the proofs from there. We omit some details. We remark that in [6], the proof of the statement \(\textrm{ex}(n,K_k,F)={{\mathcal {N}}}(K_k,K_{s-1}+T(n-s+1,r))\) shows a bit more: if an n-vertex F-free graph G is not a subgraph of \(K_{s-1}+T(n-s+1,r)\), then it contains \({{\mathcal {N}}}(K_k,K_{s-1}+T(n-s+1,r))-\Omega (n^{k-1})\) copies of \(K_k\). This immediately implies for us that \(G_{blue}\) is a subgraph of \(K_{s-1}+T(n-s+1,r)\). Changing any blue edge in \(K_{s-1}+T(n-s+1,r)\) to red destroys \(\Theta (n^{k-2})\) copies of \(K_k\), thus it decreases g(G). This gives an alternative proof of (i) of Theorem 1.6.

Proof

Let G be a blue-red F-free graph with \(g(G)=\textrm{ex}^{{\mathrm col}}(n,F)\). We apply (ii) of Theorem 1.7. Assume first that there are s independent edges \(u_1v_1,\dots , u_sv_s\) inside the parts such that for each i, at least one of \(u_i\) and \(v_i\) are not in B. Observe that \(u_i\) and \(v_i\) have \(\Omega (n)\) common neighbors in each part besides the one containing them. Using this, we can easily extend each edge to an \((r+1)\)-chromatic component of F, where \(u_iv_i\) plays the role of a color-critical edge. We can also find the other components to obtain a copy of F in G, a contradiction.

If \(|B|\ge s\), then we can find s distinct vertices among their neighbors not in B, resulting in the contradiction. By similar reasoning, there are no \(s-|B|\) independent edges inside parts but outside B. Therefore, the edges inside parts that are not incident to any vertex of B form at most \(s-1-|B|\) stars plus O(1) further edges. Since the vertices outside B are incident to o(n) edges inside parts, there are \(o(n^{k-1})\) k-cliques containing such a vertex. This implies that deleting all the edges inside parts that are not incident to B, we lose \(o(n^{|k-1})\) copies of \(K_k\). If \(|B|<s-1\), then we can add a vertex to B creating \(\Theta (n^{k-1})\) copies of \(K_k\), a contradiction. We obtained that \(|B|=s-1\) and then there is no edge inside parts but outside B. This implies that G is a subgraph of \(K_{s-1}+T(n-s+1,r)\), completing the proof. \(\square \)