bounds of Spencer [6,7]. On the other hand, the current best upper bounds are proved by Li, Rousseau, and Zang [8] by extending ideas of Shearer [9], which improve earlier bounds of Ajtai, Komlós and Szemerédi [1]. These bounds are as follows: for 𝑠 ≥ 3, there exists a constant 𝑐 1 (𝑠) > 0 such that

≤ 𝑟(𝐾 𝑠 , 𝑛) ≤ (1 + 𝑜( 1)) 𝑛 𝑠-1 (log 𝑛) 𝑠-2 Recently, the first and fourth authors [10] determined the asymptotics of 𝑟(𝐾 4 , 𝑛) up to a logarithmic factor by proving the following lower bounds.

Theorem 1. (Theorem 1 [10]) As 𝑛 → ∞, 𝑟(𝐾 4 , 𝑛) = Ω ( 𝑛 3 (log 𝑛) 4 )

In this paper, we prove some hypergraph versions of these results. A Berge triangle is a hypergraph consisting of three distinct edges 𝑒 1 , 𝑒 2 , and 𝑒 3 such that there exist three distinct vertices 𝑥, 𝑦, and 𝑧 with the property that {𝑥, 𝑦} ⊂ 𝑒 1 , {𝑦, 𝑧} ⊂ 𝑒 2 , and {𝑥, 𝑧} ⊂ 𝑒 3 . It is easy to check that there are only four different 3-uniform Berge triangles: 𝐿𝐶 3 (loose cycle of length 3), 𝑇 𝑃 3 (tight path on three edges and five vertices), 𝐹 5 , and 𝐾 3- 4 (3-uniform clique on four vertices minus an edge), as shown from left to right in Figure 1. It is natural to consider the problem of determining the off-diagonal Ramsey numbers for 3-uniform Berge triangles since they are in some sense the smallest non-trivial hypergraphs that provide a natural extension of 𝑟(𝐾 3 , 𝑛).

The off-diagonal Ramsey numbers for 𝑇 𝑃 3 and 𝐿𝐶 3 have been determined up to a logarithmic factor: for 𝑇 𝑃 3 , a result of Phelps and Rödl [11] shows that 𝑐 1 𝑛foot_0 ∕ log 𝑛 ≤ 𝑟(𝑇 𝑃 3 , 𝑛) ≤ 𝑐 2 𝑛 2 ; for 𝐿𝐶 3 , Kostochka, the second author, and the fourth author [12] showed that 𝑐 1 𝑛 3∕2 ∕(log 𝑛) 3∕4 ≤ 𝑟(𝐿𝐶 3 , 𝑛) ≤ 𝑐 2 𝑛 3∕2 . It seems plausible to conjecture that for some constant 𝑐, 𝑟(𝑇 𝑃 3 , 𝑛) ≤ 𝑐𝑛 2 log 𝑛 and 𝑟(𝐿𝐶 3 , 𝑛) ≤ 𝑐𝑛

(log 𝑛)

It is conjectured explicitly in [12] that 𝑟(𝐿𝐶 3 , 𝑛) = 𝑜(𝑛 3∕2 ) and the question of determining the order of magnitude of 𝑟(𝑇 𝑃 3 , 𝑛) was posed in [13]. It was also shown in [13] that 𝑟(𝑇 𝑃 4 , 𝑛) has an order of magnitude 𝑛 2 , leaving 𝑇 𝑃 3 as the only tight path for which the order of magnitude of 𝑟(𝑇 𝑃 𝑠 , 𝑛) remains open. We remark that if one can prove that every 𝑛-vertex 𝑇 𝑃 3 -free 3-graph with average degree 𝑑 > 1 has an independent set of size at least Ω(𝑛 √ log 𝑑∕𝑑), then this implies that 𝑟(𝑇 𝑃 3 , 𝑛) = Θ(𝑛 2 ∕ log 𝑛).

The problem for 𝐾 3- 4 is interesting in the sense that it is the smallest hypergraph whose off-diagonal Ramsey number is at least exponential: Erdős and Hajnal [14] proved 𝑟(𝐾 3- 4 , 𝑛) = 𝑛 𝑂(𝑛) and Rödl (unpublished) proved 𝑟(𝐾 3- 4 , 𝑛) ≥ 2 Ω(𝑛) . More recently, Fox and He [15] showed that 𝑟(𝐾 3- 4 , 𝑛) = 𝑛 Θ(𝑛) .

The problem for 𝐹 5 , however, is not very well studied: a result of Kostochka, the second author, and the fourth author [16] implies that 𝑟(𝐹 5 , 𝑛) ≤ 𝑐 1 𝑛 3 ∕ log 𝑛, and the standard probabilistic deletion method shows that 𝑟(𝐹 5 , 𝑛) ≥ 𝑐 2 𝑛 2 ∕ log 𝑛. In this paper, we fill this gap by showing that 𝑟(𝐹 5 , 𝑛) = 𝑛 3 ∕polylog(𝑛). This is a consequence of a more general theorem that we will prove.

We use this terminology to describe the fact that at most one new vertex is added when we add a new edge in the ordering. Further, 𝐹 is 𝑘-partite, or degenerate, if its vertices can be partitioned into 𝑘 sets 𝑉 1 , . . . , 𝑉 𝑘 such that each edge intersects each 𝑉 𝑖 , 1 ≤ 𝑖 ≤ 𝑘, in exactly one vertex. Otherwise, 𝐻 is non-degenerate. The three hypergraphs 𝑇 𝑃 3 , 𝐹 5 , and 𝐾 3- 4 in Figure 1 are slowly growing, whereas the first is not. The last two are non-degenerate.

In this paper, we obtain the following result for non-degenerate, slowly growing hypergraphs.

For every 𝑘 ≥ 3, there exists a constant 𝑐 > 0 such that for every slowly growing non-degenerate 𝑘-graph 𝐹 and all integers 𝑛 ≥ 2

The constant 𝑐 here is independent of 𝐹 because our construction simultaneously avoids all non-degenerate slowly growing 𝐹 . The order of magnitude of 𝑟(𝑇 𝑘 , 𝑛) for 𝑘 ≥ 3 is determined by the upper bound result of Kostochka, the second author, and the fourth author [16] together with the lower bound result of Bohman, the second author, and Picollelli [17]. For 𝑘 = 2, this theorem restates the known result [1][2][3][4] that 𝑟(𝐾 3 , 𝑛) has an order of magnitude of 𝑛 2 ∕ log 𝑛.

Theorem 3. (Theorem 2 [16]; Theorem 1 [17]) Let 𝑘 ≥ 2. Then there exist constants 𝑐 1 , 𝑐 2 > 0 such that for all integers 𝑛 ≥ 2, 𝑐 1 𝑛 𝑘 log 𝑛 ≤ 𝑟(𝑇 𝑘 , 𝑛) ≤ 𝑐 2 𝑛 𝑘 log 𝑛 Thus we have 𝑟(𝐹 2𝑘-1 , 𝑛) ≤ 𝑟(𝑇 𝑘 , 𝑛) ≤ 𝑂(𝑛 𝑘 ∕ log 𝑛). On the other hand, it is easy to check that 𝐹 2𝑘-1 is a slowly growing non-degenerate 𝑘-graph. Hence Theorem 2 together with Theorem 3 implies the following theorem. Theorem 4. Let 𝑘 ≥ 3. There exist constants 𝑐 1 , 𝑐 2 > 0 such that for all integers 𝑛 ≥ 2, 𝑐 1 𝑛 𝑘 (log 𝑛) 2𝑘-2 ≤ 𝑟(𝐹 2𝑘-1 , 𝑛) ≤ 𝑐 2 𝑛 𝑘 log 𝑛 Theorem 4 determines 𝑟(𝐹 2𝑘-1 , 𝑛) up to a logarithmic factor. In particular, this determines 𝑟(𝐹 5 , 𝑛) up to a polylogarithmic factor, and 𝐹 5 is the only 3-uniform Berge triangle for which the polynomial power of the off-diagonal Ramsey number was not previously known.

It would be interesting to determine its order of magnitude. We believe the current upper bounds are closer to the truth:

Conjecture 1. There exists a constant 𝑐 > 0 such that for

The proof of Theorem 2 uses the so-called random block construction, which first requires a pseudorandom bipartite graph. We build our construction using the following bipartite graph.

Definition 1. For every prime power 𝑞 and integer 𝑚 ≥ 2, let Γ 𝑞,𝑚 be the bipartite graph with two parts 𝑋 = 𝔽 2 𝑞 and 𝑌 = 𝔽 𝑚 𝑞 , where two vertices 𝑥 = (𝑥 0 , 𝑥 1 ) ∈ 𝑋 and 𝑦 = (𝑦 0 , . . . , 𝑦 𝑚-1 ) ∈ 𝑌 form an edge if and only if

𝑞 and 𝑌 as one-variable polynomials defined on 𝔽 𝑞 of degree at most 𝑚 -1. Now Γ 𝑞,𝑚 is simply the incidence bipartite graph of the points and the polynomials where a point 𝑃 ∈ 𝑋 and a polynomial 𝐹 ∈ 𝑌 form an edge if and only if 𝑃 = (𝑤, 𝐹 (𝑤)) for some 𝑤 ∈ 𝔽 𝑞 .

For any vertex 𝑥 of a graph 𝐺, we use 𝑑(𝑥) to denote the degree of 𝑥, that is, the number of neighbors of 𝑥 in 𝐺. Further, for any set 𝑈 of vertices, we use 𝑑(𝑈 ) to denote the number of common neighbors of vertices in 𝑈 . When 𝑈 = {𝑥, 𝑦}, we use 𝑑(𝑥, 𝑦) = 𝑑({𝑥, 𝑦}) for short. The following proposition collects some useful properties of Γ 𝑞,𝑚 .

Proposition 1. For every prime power 𝑞 and integer 𝑚 ≥ 2, Γ 𝑞,𝑚 has the following properties:

i. For every 𝑥 = (𝑥 0 , 𝑥 1 ) ∈ 𝑋, to find a neighbor 𝑦 = (𝑦 0 , . . . , 𝑦 𝑚-1 ) of 𝑥, one can choose 𝑦 𝑖 for 1 ≤ 𝑖 ≤ 𝑚 -1 freely and then let

ii. For every 𝑦 = (𝑦 0 , . . . , 𝑦 𝑚-1 ), to find a neighbor 𝑥 = (𝑥 0 , 𝑥 1 ) of 𝑦, one can choose 𝑥 0 freely and then let

where 𝑥 is the only variable. By the Fundamental Theorem of Algebra for finite fields, such an equation has at most 𝑚 -1 solutions. Since 𝑥 1 is determined by 𝑥 0 , we conclude that 𝑑(𝑦, 𝑦 ′ ) ≤ 𝑚 -1. iv. For every 𝑥 = (𝑥 0 , 𝑥 1 ), 𝑥 ′ = (𝑥 ′ 0 , 𝑥 ′ 1 ) ∈ 𝑋, if 𝑥 0 ≠ 𝑥 ′ 0 , then every common neighbor 𝑦 = (𝑦 0 , . . . , 𝑦 𝑚-1 ) corresponds to a solution to a collection of two linear equations that are linearly independent. The solution space of such a collection of linear equations has rank 𝑚 -2, which implies that the number of solutions is 𝑞 𝑚-2 . Thus in this case 𝑑(𝑥, 𝑥 ′ ) = 𝑞 𝑚-2 . On the other hand, if

0 , which implies that the two equations cannot equal 0 at the same time. Thus 𝑑(𝑥, 𝑥 ′ ) = 0. v. Let |𝑈 | = 𝑘, and let 𝑥 (1) = (𝑥 (1) 0 , 𝑥 (1) 1 ), . . . , 𝑥 (𝑘) = (𝑥 (𝑘) 0 , 𝑥 (𝑘) 1 ) be the vertices in 𝑈 . Then each common neighbor 𝑦 = (𝑦 0 , . . . , 𝑦 𝑚-1 ) corresponds to a solution to the collection of 𝑘 linear equations

1 since 𝑥 (𝑡 1 ) and 𝑥 (𝑡 2 ) are different. Then by the same argument as in (iv), we know that 𝑑(𝑈 ) = 0. On the other hand, if all 𝑥 (𝑡) 0 are distinct, then the solution space of the collection of linear equations has rank 𝑚 -𝑘, which implies that the number of solutions is 𝑞 𝑚-𝑘 . Thus in this case 𝑑(𝑥, 𝑥 ′ ) = 𝑞 𝑚-𝑘 . ◽ For all 𝑘 ≥ 3, let 𝐻 𝑞,𝑘 be a 𝑘-uniform hypergraph on 𝑋 = 𝑋(Γ 𝑞,𝑘-1 ) whose edges are all 𝑘-sets {𝑥 1 , . . . , 𝑥 𝑘 } ⊆ 𝑋 such that there exists an element 𝑦 ∈ 𝑌 = 𝑌 (Γ 𝑞,𝑘-1 ) such that {𝑥 1 , . . . , 𝑥 𝑘 } ⊆ 𝑁(𝑦). By Proposition 1, 𝐻 𝑞,𝑘 is the union of 𝑞 𝑘-1 𝑘-uniform cliques on 𝑞 vertices such that each vertex is contained in 𝑞 𝑘-2 cliques and the vertex sets of every two cliques intersect in at most 𝑘 -2 vertices. Let 𝐻 * 𝑞,𝑘 be the 𝑘-uniform hypergraph obtained by replacing each maximal clique of 𝐻 𝑞,𝑘 with a random complete 𝑘-partite 𝑘-graph on the same vertex set. More formally, for each 𝑦 ∈ 𝑌 , we color the vertices in 𝑁(𝑦) with 𝑘 colors {1, . . . , 𝑘} uniformly at random, and for each 1 ≤ 𝑖 ≤ 𝑘, we let 𝑋 𝑦,𝑖 ⊆ 𝑁(𝑦) be the set of vertices with color 𝑖, and then we replace the clique on 𝑁(𝑦) with a complete 𝑘-partite 𝑘-graph on 𝑁(𝑦) with 𝑘-partition 𝑋 𝑦,1 ⊔ • • • ⊔ 𝑋 𝑦,𝑘 . It is easy to check the following proposition. Proposition 2. If 𝐹 is a non-degenerate slowly growing 𝑘-graph, then 𝐻 * 𝑞,𝑘 is 𝐹 -free.

We claim that every copy of 𝐹 in 𝐻 𝑞,𝑘 must be fully contained in one of the 𝑞 𝑘-1 𝑘-uniform cliques of size 𝑞. Indeed, suppose that we want to build a copy of 𝐹 in 𝐻 𝑞,𝑘 by consecutively picking the edges in the order given above. Then the fact that every two cliques of 𝐻 𝑞,𝑘 intersect in at most 𝑘 -2 vertices shows that we must pick every edge in the clique containing the previous edges. Since 𝐻 * 𝑞,𝑘 is obtained from 𝐻 𝑞,𝑘 by replacing every clique by a complete 𝑘-partite 𝑘-graph and 𝐹 itself is not 𝑘-partite, this proves the statement. ◽

We will fix an instance of 𝐻 * 𝑞,𝑘 with good Balanced Supersaturation, which means that each induced subgraph of 𝐻 * 𝑞,𝑘 on 𝑞 1+𝑜(1) vertices contains many edges that are evenly distributed. Using Balanced Supersaturation together with the Hypergraph Container Lemma [18,19], we can find upper bounds on the number of independent sets in 𝐻 * 𝑞,𝑘 of size 𝑡 = (log

We then take a random subset 𝑊 of 𝑉 (𝐻 * 𝑞,𝑘 ) where each vertex is sampled independently with probability 𝑝 = Θ( 𝑡 𝑞 ) as in [20]. Finally, our construction is obtained by arbitrarily deleting a vertex from each independent set of size 𝑡 in 𝐻 * 𝑞,𝑘 [𝑊 ].

We will give the details in the following sections.

In this section we show the pseudorandomness of Γ 𝑞,𝑘-1 , which will be useful later in showing the balanced supersaturation of 𝐻 * 𝑞,𝑘 .

Given an 𝑛-vertex graph 𝐺, let 𝐴 𝐺 be the adjacency matrix of 𝐺, which is the 𝑛 × 𝑛 symmetric matrix where

if {𝑖, 𝑗} ∈ 𝐸(𝐺), 0, otherwise Let 𝜆 1 (𝐺) ≥ . . . ≥ 𝜆 𝑛 (𝐺) denote the eigenvalues of 𝐴 𝐺 . If 𝐺 is a bipartite graph with bipartition 𝑉 1 ⊔ 𝑉 2 , we say 𝐺 is (𝑑 1 , 𝑑 2 )-regular if 𝑑(𝑣) = 𝑑 1 for all 𝑣 ∈ 𝑉 1 and 𝑑(𝑣) = 𝑑 2 for all 𝑣 ∈ 𝑉 2 . The seminal expander mixing lemma is an important tool that relates edge distribution to the second eigenvalue of a graph. Here we make use of the bipartite version. Lemma 1. (Theorem 5.1, [21]) Suppose that 𝐺 is a (𝑑 1 , 𝑑 2 )-regular bipartite graph with bipartition 𝑉 1 ⊔ 𝑉 2 . Then for every 𝑆 ⊂ 𝑉 1 and 𝑇 ⊂ 𝑉 2 , the number of edges between 𝑆 and 𝑇 , denoted by 𝑒(𝑆, 𝑇 ), satisfies | By Proposition 1, we know Γ 𝑞,𝑘-1 is (𝑞 𝑘-2 , 𝑞)-regular. For convenience, from now on we let 𝑛 = |𝑉 (Γ 𝑞,𝑘-1 )| = 𝑞 2 + 𝑞 𝑘-1 , 𝐴 = 𝐴 Γ 𝑞,𝑘-1 , 𝜆 𝑖 = 𝜆 𝑖 (Γ 𝑞,𝑘-1 ) for all 1 ≤ 𝑖 ≤ 𝑛, and let 𝑑 1 = 𝑞 𝑘-2 , 𝑑 2 = 𝑞. Lemma 2. 𝜆 2 = 𝑞 𝑘 2 -1 .

Proof. Define the matrix

where 𝐽 is the |𝑋| × |𝑌 | all-one matrix. We will show that

By definition, for any 𝑥 ∈ 𝑋 and 𝑦 ∈ 𝑌 , 𝐴 3 (𝑥, 𝑦) is the number of walks of length three of the form 𝑥𝑦 ′ 𝑥 ′ 𝑦 in Γ 𝑞,𝑘-1 . There are two cases.

Case 1: 𝑥𝑦 ∈ 𝐸(Γ 𝑞,𝑘-1 ). When 𝑥 ′ = 𝑥, the number of choices for 𝑦 ′ is 𝑞 𝑘-2 . When 𝑥 ′ ≠ 𝑥, the number of choices for 𝑥 ′ is 𝑞 -1, and for each such 𝑥 ′ , by Proposition 1iv, the number of choices for 𝑦 ′ is 𝑞 𝑘-3 . Thus in this case the number of walks 𝑥𝑦 ′ 𝑥 ′ 𝑦 is 𝑞 𝑘-2 + (𝑞 -1)𝑞 𝑘-3 .

Case 2: 𝑥𝑦 ∉ 𝐸(Γ 𝑞,𝑘-1 ). Suppose 𝑥 = (𝑥 0 , 𝑥 1 ) and 𝑥 ′ = (𝑥 ′ 0 , 𝑥 ′ 1 ). If 𝑥 0 = 𝑥 ′ 0 , then 𝑥 1 ≠ 𝑥 ′ 1 , and hence, by Proposition 1iv, 𝑥 and 𝑥 ′ have no common neighbor. When 𝑥 0 ≠ 𝑥 ′ 0 the number of choices for 𝑥 ′ is 𝑞 -1 and for each such 𝑥 ′ , the number of choices for 𝑦 ′ is 𝑞 𝑘-3 , again by Proposition 1iv. Thus in this case the number of walks 𝑥𝑦 ′ 𝑥 ′ 𝑦 is (𝑞 -1)𝑞 𝑘-3 .

Combining the two cases above, we obtain Equation (1). Next, let 𝑢 𝑋 be the characteristic vector of 𝑋, that is, 𝑢 𝑋 (𝑣) = 1 for each 𝑣 ∈ 𝑋 and 𝑢 𝑋 (𝑣) = 0 otherwise. Similarly, let 𝑢 𝑌 be the characteristic vector of 𝑌 . Let

It is easy to check that 𝜆 1 = -𝜆 𝑛 = √ 𝑑 1 𝑑 2 and that 𝑎 1 and 𝑎 𝑛 are eigenvectors corresponding to 𝜆 1 and 𝜆 𝑛 . Since 𝐴 is symmetric, the spectral theorem implies that 𝐴 has an orthonormal basis of eigenvectors. Hence, for each 1 < 𝑖 < 𝑛, there exists an eigenvector 𝑎 𝑖 corresponding to 𝜆 𝑖 such that 𝑎 𝑖 is orthogonal to both 𝑎 1 and 𝑎 𝑛 . Thus 𝑎 𝑖 is orthogonal to 𝑢 𝑋 and 𝑢 𝑌 , which implies that 𝑀 ⋅ 𝑎 𝑖 = 0. Multiplying both sides of Equation ( 1) by 𝑎 𝑖 , we obtain 𝜆 3 𝑖 = 𝑞 𝑘-2 𝜆 𝑖 . Because the rank of 𝐴 is larger than 2, there exists at least one 𝜆 𝑖 ≠ 0, and hence

Let 𝑆 be a subset of 𝑋 with size |𝑆| = 𝑟𝑞. If we pick 𝑦 ∈ 𝑌 uniformly at random, then the expectation of |𝑁(𝑦) ∩ 𝑆| is 𝑟. Thus intuitively, the vertex set of a "typical" clique in 𝐻 𝑞,𝑘 intersects 𝑆 in Θ(𝑟) vertices. The following lemma shows that a substantial portion of all cliques are "typical".

Let 𝑆 be a subset of 𝑋 with size |𝑆| = 𝑟𝑞. For 0 < 𝛿 < 1, let

Let

Apply Lemma 1 with 𝐺 = Γ 𝑞,𝑘-1 and 𝑇 = 𝑌 + . Together with Lemma 2, we have

In this section, we show that 𝐻 * 𝑞,𝑘 has balanced supersaturation with positive probability. We need to use the following concentration inequality. Proposition 3. (Corollary 2.27 [22]) Let 𝑍 1 , . . . , 𝑍 𝑡 be independent random variables, with 𝑍 𝑖 taking values in a set Λ 𝑖 .

Assume that a function 𝑓 ∶ Λ 1 × • • • × Λ 𝑡 → ℝ satisfies the following Lipschitz condition for some numbers 𝑐 𝑖 :

Then, the random variable 𝑋 = 𝑓 (𝑍 1 , . . . , 𝑍 𝑡 ) satisfies, for any 𝜆 ≥ 0,

Recall that 𝐻 * 𝑞,𝑘 is the 𝑘-uniform hypergraph obtained by replacing each maximal clique of 𝐻 𝑞,𝑘 with a random complete 𝑘-partite 𝑘-graph on the same vertex set. Concretely, for each 𝑦 ∈ 𝑌 , we color the vertices in 𝑁(𝑦) with 𝑘 colors {1, . . . , 𝑘} uniformly at random, and for each 1 ≤ 𝑖 ≤ 𝑘 we let 𝑋 𝑦,𝑖 ⊆ 𝑁(𝑦) be the set of vertices with color 𝑖, and then we replace the clique on 𝑁(𝑦) with a complete 𝑘-partite 𝑘-graph on 𝑁(𝑦) with 𝑘-partition 𝑋 𝑦,1 ⊔ • • • ⊔ 𝑋 𝑦,𝑘 . Note that the colorings for different cliques are independent.

Given a 𝑘-graph 𝐻, let Δ 𝑖 (𝐻) denote the maximum integer such that there exists 𝑆 ⊆ 𝑉 (𝐻) such that |𝑆| = 𝑖 and the number of edges containing 𝑆 is Δ 𝑖 (𝐻).

There exists a subgraph 𝐻 ⊂ 𝐻 * 𝑞,𝑘 [𝑆] such that, for all 1 ≤ 𝑖 ≤ 𝑘,

Proof. For a fixed 𝑆 ⊆ 𝑋 with |𝑆| ≥ 4𝑘𝑞, let 𝑟 = |𝑆|∕𝑞 ≥ 4𝑘 ≥ 12 and let

Let 𝐻 be a subgraph of 𝐻 * 𝑞,𝑘 [𝑆] with edge set

other words, 𝐻 contains only edges that are in the "typical" cliques. Define the random variable 𝑍 = |𝐸(𝐻)|. For all 𝑦 ∈ 𝑌 1∕2 and 𝑣 ∈ 𝑁 Γ 𝑞,𝑘-1 (𝑦), let 𝐴 𝑦,𝑣 be the random variable with values in {1, . . . , 𝑘} such that 𝐴 𝑦,𝑣 = 𝑖 if vertex 𝑣 receives color 𝑖 in the clique on 𝑁 Γ 𝑞,𝑘-1 (𝑦). Let 𝐵 1 , . . . , 𝐵 𝑡 be an arbitrary order of 𝐴 𝑦,𝑣 for 𝑦 ∈ 𝑌 1∕2 and 𝑣 ∈ 𝑁 Γ 𝑞,𝑘-1 (𝑣). Clearly, 𝑍 is determined by 𝐵 1 , . . . , 𝐵 𝑡 , i.e., there exists a function 𝑓 ∶ [𝑘] 𝑡 → ℕ such that 𝑍 = 𝑓 (𝐵 1 , . . . , 𝐵 𝑡 ). Observe that changing the color of a vertex 𝑣 in a typical clique will only affect the number of edges containing 𝑣 in that clique, which is at most ( 3𝑟∕2-1 𝑘-1 ) ≤ (2𝑟) 𝑘-1 , since a typical clique has size at most 3𝑟∕2. In other words, if two vectors 𝑏, 𝑏 ′ ∈ [𝑘] 𝑡 differ in only one coordinate, then

Note that for any 𝑘 vertices in a typical clique, the probability that they form an edge in 𝐻 is 𝑘 ! 𝑘 𝑘 . Hence, by linearity of expectation and the fact that a typical clique has size at least 𝑟∕2 and that 𝑟∕2 -𝑘 ≥ 𝑟∕4, we have

Thus by Proposition 3 with 𝜆 = 𝑟 𝑘 𝑞 𝑘-1 6(4𝑘) 𝑘 , 𝑐 𝑖 = (2𝑟) 𝑘-1 , and the fact that

) Using the union bound, the probability that there exists an 𝑆 ⊆ 𝑋

given that 𝑞 is sufficiently large in terms of 𝑘.

Hence, with positive probability, for every 𝑆 ⊆ 𝑋 with |𝑆| = 𝑟𝑞 ≥ 4𝑘𝑞, the corresponding 𝐻 satisfies |𝐸(𝐻)| ≥ 𝑟 𝑘 𝑞 𝑘-1 6(8𝑘) 2𝑘 . Let 𝐽 ⊆ 𝑆 be such that |𝐽 | = 𝑖 and 1 ≤ 𝑖 ≤ 𝑘 -1. Note that, by Proposition 1 (v), the number of 𝑦 such that 𝐽 ⊆ 𝑁 Γ 𝑞,𝑘-1 (𝑦) is at most 𝑞 𝑘-1-𝑖 , and for each such 𝑦 ∈ 𝑌 1∕2 , the number of edges in

and when 𝑖 = 𝑘,

Combining the inequalities above, we have for all 1 ≤ 𝑖 ≤ 𝑘,

concluding the proof. Note that a stronger bound actually holds for all 𝑖 ≤ 𝑘 -1, and the claimed bound only arises from the case 𝑖 = 𝑘. ◽

We make use of the hypergraph container method developed independently by Balogh, Morris, and Samotij [18] and Saxton and Thomason [19]. Here we make use of the following simplified version of Theorem 1.5 in [23]:

Theorem 5. (Theorem 1.5 [23]) For every integer 𝑘 ≥ 2, there exists a constant 𝜖 > 0 such that the following holds. Let 𝐵, 𝐿 ≥ 1 be positive integers and let 𝐻 be a 𝑘-graph satisfying

Then there exists a collection  of subsets of 𝑉 (𝐻) such that:

i. For every independent set 𝐼 of 𝐻, there exists 𝐶 ∈  such that 𝐼 ⊂ 𝐶;

ii. For every 𝐶 ∈ , |𝐶| ≤ |𝑉 (𝐻)| -𝜖𝐿;

iii. We have

Next, we use Theorem 5 together with Lemma 4 to count the number of independent sets of size 𝑞

1 𝑘-1 (log 𝑞) 2 in 𝐻 * 𝑞,𝑘 . Theorem 6. For every 𝑘 ≥ 3, there exists a constant 𝑐 ′ > 0 such that, when 𝑞 is sufficiently large, we can fix an instance of 𝐻 * 𝑞,𝑘 such that the number of independent sets of size 𝑡 = 𝑞 1 𝑘-1 (log 𝑞) 2 of 𝐻 * 𝑞,𝑘 is at most ( 𝑐 ′ 𝑞 𝑡 ) 𝑡 Proof. By Lemma 4, we can fix an instance of 𝐻 * 𝑞,𝑘 such that for every 𝑆 ⊂ 𝑉 (𝐻 * 𝑞,𝑘 ) with |𝑆| ≥ 4𝑘𝑞 there exists a subgraph 𝐻 of 𝐻 * 𝑞,𝑘 [𝑆] such that for all 1 ≤ 𝑖 ≤ 𝑘, Δ 𝑖 (𝐻) ≤ 6(16𝑘) 2𝑘 |𝐸(𝐻)| |𝑆| ( 𝑞 1 𝑘-1 |𝑆| ) 𝑖-1 (3) We will first prove the following claim. Claim 1. There exists a constant 𝜖 > 0 such that for every 𝑆 ⊂ 𝑉 (𝐻 * 𝑞,𝑘 ) with |𝑆| > 4𝑘𝑞, there exists a collection  𝑆 of at most exp ( log 𝑞 ⋅ 𝑞 1 𝑘-1 𝜖 ) subsets of 𝑆 such that: i. For every independent set 𝐼 of 𝐻 * 𝑞,𝑘 [𝑆], there exists 𝐶 ∈  𝑆 such that 𝐼 ⊂ 𝐶; ii. For every 𝐶 ∈  𝑆 , |𝐶| ≤ (1 -𝜖)|𝑆|. ◽ Proof. Fix an arbitrary 𝑆 ⊂ 𝑉 (𝐻 * 𝑞,𝑘 ) with |𝑆| ≥ 4𝑘𝑞. By Lemma 4 there exists a subgraph 𝐻 of 𝐻 * 𝑞,𝑘 [𝑆] satisfying Equation (3). By Equation (3), it is easy to check that Equation (2) holds for 𝐻, with 𝐿 = |𝑆| 6(16𝑘) 2𝑘 and 𝐵 = 𝑞 1 𝑘-1 . Hence by Theorem 5, there exist a constant 𝜖 ′ (not depending on 𝑆) and a collection  𝑆 of subsets of 𝑆 such that i. For every independent set 𝐼 of 𝐻, there exists 𝐶 ∈  𝑆 such that 𝐼 ⊂ 𝐶; ii. For every 𝐶 ∈  𝑆 , |𝐶| ≤ |𝑉 (𝐻)| -𝜖 ′ 𝐿 ≤ ( 1 -𝜖 ′ 6(16𝑘) 2𝑘

) |𝑆|;

iii. We have

every independent set of 𝐻 * 𝑞,𝑘 [𝑆] is also an independent set of 𝐻. Therefore, by taking 𝜖 sufficiently small with respect to 𝜖 ′ and 𝑘, we conclude that  𝑆 has the desired properties. ◽ Now we apply Claim 1 iteratively as follows. Fix the constant 𝜖 guaranteed by Claim 1. Let  0 = {𝑉 (𝐻 * 𝑞,𝑘 )}. Let 𝑡 0 = |𝑉 (𝐻 * 𝑞,𝑘 )| = 𝑞 2 and let 𝑡 𝑖 = (1 -𝜖)𝑡 𝑖-1 for all 𝑖 ≥ 1. Let 𝑚 be the smallest integer such that 𝑡 𝑚 ≤ 4𝑘𝑞. Clearly 𝑚 = 𝑂(log 𝑞). Given a set of containers  𝑖 such that every 𝐶 ∈  𝑖 satisfies |𝐶| 𝑡 𝑖 , we construct  𝑖+1 as follows: for every 𝐶 ∈  𝑖 , if |𝐶| ≤ 𝑡 𝑖+1 , then we put it into  𝑖+1 ; otherwise, if |𝐶| > 𝑡 𝑖+1 , by Claim 1, there exists a collection  ′ of containers for 𝐻 * 𝑞,𝑘 [𝐶] such that every 𝐶 ′ ∈  ′ satisfies |𝐶 ′ | < (1 -𝜖)|𝐶| ≤ 𝑡 𝑖+1 -now we put every element of  ′ into  𝑖+1 . Let  =  𝑚 . Note that | 𝑖 | | 𝑖-1 | ≤ exp ( log 𝑞 ⋅ 𝑞 Recall that 𝑡 = (log 𝑞) 2 𝑞 1 𝑘-1 and let 𝑁 𝑡 be the number of independent sets of 𝐻 of size 𝑡. Since every independent set of 𝐻 of size 𝑡 is contained in some 𝐶 ∈ , we have, for some constant 𝑐 ′ > 0,

𝑡 ) ≤ ( 𝑐 ′ 𝑞 𝑡 ) 𝑡 ◽ 6 | Proof of Theorem 2 Proof. Proof of Theorem 2 For every sufficiently large prime power 𝑞, we let 𝑡 = (log 𝑞) 2 𝑞 1 𝑘-1 . By Theorem 6 we can fix an instance of 𝐻 * 𝑞,𝑘 such that the number of independent sets of 𝐻 * 𝑞,𝑘 of size 𝑡 is at most ( 𝑐 ′ 𝑞 𝑡 ) 𝑡 for some constant 𝑐 ′ > 0. Let 𝑊 be a random subset of 𝑉 (𝐻 * 𝑞,𝑘 ) where each vertex is sampled independently with probability 𝑝 = 𝑡 𝑐 ′ 𝑞 . Note that 𝑝 < 1 as 𝑞 is sufficiently large. Then the expected number of independent sets of size 𝑡 in 𝐻 * 𝑞,𝑘 [𝑊 ] is at most ( 𝑐 ′ 𝑞 𝑡 ) 𝑡 𝑝 𝑡 ≤ 1 Let 𝑊 ′ ⊆ 𝑊 be obtained by arbitrarily deleting one vertex in each independent set of size 𝑡. Thus the expectation of |𝑊 ′ | is at least 𝑝𝑞 2 -1 = (log 𝑞) 2 𝑐 ′ 𝑞 𝑘 𝑘-1 -1 Hence there exists a choice 𝑊 ′ with at least this many vertices. Let 𝐻 ′ = 𝐻 * 𝑞,𝑘 [𝑊 ′ ]. By definition of 𝑊 ′ , we have 𝛼(𝐻 ′ ) < 𝑡. Moreover, by Proposition 2 we know that 𝐻 ′ is 𝐹 -free. Thus, we have 𝑟(𝐹 , 𝑡) ≥ (log 𝑞) 2 𝑐 ′ 𝑞 𝑘 𝑘-1

Recall that 𝑡 = (log 𝑞) 2 𝑞 1 𝑘-1 . It is well-known that for every integer 𝑛 there exists a prime 𝑞 such that 𝑛∕2 ≤ 𝑞 ≤ 𝑛. Thus for every 𝑛 sufficiently large, it is easy to find a prime 𝑞 such that

Therefore we conclude that there exists a constant 𝑐 > 0 such that for all 𝑛 sufficiently large, 𝑟(𝐹 , 𝑛) ≥ 𝑐𝑛 𝑘 (log 𝑛) 2𝑘-2 ◽