A classical result of Erdős and, independently, of Bondy and Simonovits [3] says that the maximum number of edges in an
In this paper we extend Simonovits' result to a supersaturation result of
One of the central problems in extremal graph theory is the Turán problem, where, for a fixed graph H and fixed n, we wish to determine the maximum number of edges an n-vertex graph can have without creating a copy of H as a subgraph. This number is called the Turán number of H and is denoted by ex(n, H). The celebrated Erdős-Stone-Simonovits [6]theoremsaysthat
where χ(H) is the chromatic number of the graph H. This solves the Turán problem asymptotically for all non-bipartite graphs H. However, asymptotic results or exact results are known for only a handful of bipartite graphs. While the Turán problem asks for the threshold on the number of edges on n vertices that guarantees at least one copy of H, it is natural to ask what is the minimum number of copies of H guaranteed in a host graph once its number of edges exceeds ex(n, H). Such problems are referred to as supersaturation problems.WhenH is non-bipartite, we know the correct order of magnitude of the answer. Let H be a graph with χ(H) = p 3andv(H) vertices. A simple averaging argument (see e.g. Lemma 2.1 in [17]) can be used to show that for any ε>0 there exist δ, n 0 > 0 such that if G is a graph on n n 0 vertices with e(G) 1 -
then G contains at least δ n v(H) copies of H. This count is tight up to a multiplicative constant, as shown by the random graph of the same edge density as G. The threshold on the number of edges on G for which the count is valid is also asymptotically best possible, as shown by the Turán graph T n,p-1 , which is defined as the balanced blowup of the complete graph on (p -1) vertices. For the supersaturation problem for bipartite graphs, Erdős and Simonovits [9] and also separately Simonovits [26] made the following conjecture in the 1980s.
Conjecture 1 ([9, 26]). Let H be a bipartite graph with v vertices and e edges. Suppose that ex(n, H) = O(n 2-α ) for some real 0 <α<1. Then there exist α α a n dc o n s t a n t sC, c > 0 such thatifGisann-vertexgraphwith e(G) Cn 2-α (1.1)
edges, then G contains at least c(e(G)) e /n 2e-v copies of H.
The Erdős-Rényi random graph G(n, p)withp = e(G)/ n 2 shows that if Conjecture 1 is true then it is best possible up to a multiplicative constant. Simonovits [26] made a weaker conjecture that for every bipartite graph H with v vertices and e edges, there exist reals α, C, c > 0 such that every n-vertex graph G with e(G) > Cn 2-α contains at least c(e(G)) e /n 2e-v copies of H. A slight reformulation of this conjecture (with c replaced by 1 and the number of copies of H replaced by the number of homomorphic copies of H) was made by Sidorenko [24,25]. Note that this weakened version and Sidorenko's conjecture focus on the counting statement eventually being true when the host graph becomes very dense. When we study these conjectures, we are therefore concerned with host graphs with (n 2-c ) edges where c is as small as we want. On the contrary, works on Conjecture 1 typically aim at finding the best possible threshold beyond which the counting statement holds and hence the host graphs we work with are (much) sparser. In fact, Erdős and Simonovits [9] made two conjectures even stronger than Conjecture 1 by replacing condition (1.1) with e(G) C • ex(n, H)a n de ( G) (1 + ε)ex(n, H), respectively. At this stage, resolving these stronger versions seems hopeless since the exact value or even just the order of magnitude of ex(n, H) is only known for very few bipartite graphs H. Now we turn our attention to the main focus of this paper, that is, the supersaturation of linear cycles of even length in linear r-uniform hypergraphs, or in short, r-graphs. First let us give the background for r = 2. A classical result of Erdős (unpublished) and of Bondy and Simonovits [3] establishes that ex(n, C 2k ) = O(n 1+1/k ). The explicit upper bound that Bondy and Simonovits gave was ex(n, C 2k ) 100kn 1+1/k . This upper bound was later improved by Verstraëte to 8(k -1)n 1+1/k for sufficiently large n, by Pikhurko [21]to(k -1)n 1+1/k + O(n), and by Bukh and Jiang [4]t o8 0 √ k log kn 1+1/k + O(n). Erdős and Simonovits conjectured that ex(n, C 2k ) = (n 1+1/k ) also holds. This is known to be true for k = 2, 3, 5.
For supersaturation of even cycles, it was mentioned in [9] that Simonovits proved Conjecture 1 with α = α = 1 -1/k. The proof was not published at the time but is expected to appear in an upcoming paper of Faudree and Simonovits [13]. Very recently, Morris and Saxton [20] developed a balanced version of the supersaturation result for even cycles, which they use to obtain a sharp result on the number of C 2k -free graphs via the container method. Since Morris and Saxton require a balanced version of supersaturation where the collection of C 2k 's they obtain are, informally speaking, uniformly distributed, their proof is quite involved. In this paper we extend the result by Simonovits to a supersaturation result of even linear cycles in linear r-graphs, for all r 2. Our proof is self-contained and includes the r = 2case.
Before stating our main result, we need a few definitions. An r-graph G is called linear if any two edges share at most one vertex. For instance, all 2-graphs are linear. The linear Turán number of an r-graph H, denoted by ex ℓ (n, H), is defined to be the maximum number of edges an n-vertex linear r-graph can have without having a copy of H. The study of linear Turán numbers of linear r-graphs is motivated in part by their similarity to the Turán numbers of 2-graphs. Also, such studies were implicit in some classical extremal hypergraph problems, such as the famous (6, 3)problem (see [2]a n d [ 23]), which is asymptotically equivalent to determining the linear Turán number of a linear 3-cycle. The (6, 3)-problem asks for the maximum size of an n-vertex 3-graph in which no six vertices span three or more edges. Note that the usual Turán number ex(n, H)of a linear r-graph H and the linear Turán number ex ℓ (n, H)ofH are typically very different. The former is already at least n-1 r-1 as long as H contains two disjoint edges, while the latter is O(n 2 ). An r-uniform linear cycle C (r) m of length m is obtained from a 2-uniform m-cycle v 1 v 2 ...v m v 1 by extending each v i v i+1 (indices taken modulo m)withan(r -2)-tuple I i such that the tuples I i are pairwise disjoint for distinct indices. Collier-Cartaino, Graber and Jiang [5]e x t e n d e dt h e aforementioned result of Bondy and Simonovits on even cycles in 2-graphs to linear cycles in linear r-graphs. They showed that for all r 3andm 4,
). For even linear cycles, their result also works for uniformity r = 2. In the case r = 3, it is known that the upper bound above is sharp when m = 5, 7, 9, 13 (see [11]). It is interesting to note that when r 3, the linear Turán number of an odd linear cycle resembles that of an even linear cycle, which is very different from the situation for r = 2.
Our main result is the supersaturation version of the linear Turán result for linear cycles, but only for even linear cycles. Theorem 1.1. Given k, r 2, there exist constants C = C(k, r) and c = c(k, r) such that if G is an n-vertex linear r-graph with e(G) Cn 1+1/k , then G contains at least c(e(G)/n) 2k copies of C (r) 2k .
It is not hard to see that this lower bound on the number of copies of linear cycles is tight, up to a multiplicative constant. Indeed, for r = 2, in the Erdős-Rényi graph G(n, p), in expectation there are (p 2k n 2k )2k-cycles. For r 3, one may consider random subgraphs of almost complete partial Steiner systems. An (n, λ, r, q)-Steiner system is defined to be an r-graph on n vertices such that every q-tuple is in exactly λ r-edges. A partial (n, λ, r, q)-Steiner system is defined to be an r-graph on n vertices such that every q-tuple is in at most λ r-edges. Rödl [22]provedthatforall n there are partial (n,1,r, q)-Steiner systems with
edges. (Note that this is also implied by a recent solution of the existence conjecture by Keevash [18], while the q = 2 case was proved much earlier by Wilson [28,29,30].) By taking random subgraphs of such partial Steiner systems with λ = 1andq = 2, one can show that for every n and 0 e n 2 there is a linear r-graph G on n vertices and e(G) = e in which the number of copies of the linear cycles of length 2k is O((e/n) 2k ) (see Proposition 2.1).
Our Theorem 1.1 includes r = 2 as a special case and has a much simpler proof than that of Morris and Saxton of their stronger version of supersaturation. We use an approach developed by Faudree and Simonovits [12] in the study of the Turán numbers of theta graphs, which in its original form is not well suited for effective counting of C 2k 's. So we adapt their approach to facilitate counting. The proofs are greatly simplified via a reduction tool which allows us to reduce the supersaturation problem in a general host r-graph to one which has some regularity property. This regularization tool is an analogue of a regularization theorem of Erdős and Simonovits for the Turán problem and can be used for supersaturation problems in general. We refer the reader to Section 3 for the precise statement (see Theorem 3.3).
We organize the rest of the paper roughly as follows. In Section 2 we present notation and definitions. In Section 3 we develop our reduction results. In Section 4 we give an overview of the proof for r = 2. In Sections 5 and 6 we give proofs of the r = 2andr 3 cases of Theorem 1.1, respectively. Even though we could have proved Theorem 1.1 for general r directly, we feel that proving the r = 2 case first helps to illustrate the main ideas. However, we will give two slightly different proofs for r = 2andr 3, modulo the reduction mentioned earlier. Both of these proofs could be written for all r 2. The proof we present for r = 2 is more constructive and gives a better bound on constants. The proof we present for r 3 follows the approach of Faudree and Simonovits more closely and is perhaps more intuitive and easier to follow for some readers. In Section 7 we give some concluding remarks.
For an r-graph G,weletv(G)ande(G) denote its number of vertices and edges, respectively. Let (G), δ(G) denote the maximum and minimum degree of G, respectively. If S is a subset of V(G), then we use G -S to denote the graph obtained from G by deleting the vertices in S as well as edges of G that contain at least one vertex in S. Given a vertex v ∈ V(G), the link of v in G, denoted by L G (v), is defined to be
recalling that [V(G)] (r-1) refers to the family of all (r -1)-subsets of V(G).
Given a real q 1, we say that an r-graph G is q-almost-regular if (G) qδ(G)holds.Given positive constants C, γ , we say that an r-graph G is (C, γ )-dense if e(G) C(v(G)) γ .
We let t H (G) denote the number of copies of an r-graph H in an r-graph G. Given a 2-graph F,ther-expansion of F is the r-graph obtained by replacing each edge e of F with e ∪ I e ,whereI e is an (r -2)-tuple of new vertices, such that the I e 's are pairwise disjoint for distinct edges e.Note that F (2) = F.IfG is an r-expansion of a 2-graph F, then we call F a skeleton of G. So, for example, the linear r-cycle, C (r) m is the r-expansion of the 2-uniform m-cycle.Nowwedefinethenotionof supersaturation of expansions in linear r-graphs. Definition 2. Given a 2-graph F with v vertices and e edges, r 2andc a positive real, we say that a linear r-graph G c-supersaturates F (r) if
Note that for r = 2 this definition is the usual supersaturation for 2-graphs (as in Conjecture 1), that is, a graph Gc-supersaturates another graph F with e edges and v vertices if
As we have discussed earlier, for 2-graphs the bound on the number of copies of F (r) = F in Definition 2 is achieved up to a multiplicative constant by the random graph of the same edge density. For general r 3, the bound is tight as well, obtained by random subgraphs of appropriate edge density in almost complete partial Steiner systems. The proof of this is quite standard but we include it here for brevity. Proposition 2.1. Let F be a 2-uniform graph with v vertices, e edges and no isolated vertices. Let r 2. For all n sufficiently large and all 0 < E n 2 /4r 2 there exists an n-vertex linear r-graph G with e(G) EandO(E e /n 2e-v ) copies of F (r) .
Proof. Since F has no isolated vertex we must have v 2e. By our earlier discussion we know there exist almost complete r-uniform Steiner systems, that is, we can find an n-vertex linear r-graph G with e(G) n 2 /2r 2 .Ifv = 2e then the bound we are trying to prove on the number of F (r) is O(E e ), which holds trivially. So we may assume v < 2e. Note that the number of copies of F (r) in G is at most n v . This is because there are at most n v injections σ from V(F)toV(G), and since G is linear for each uv ∈ E(F) there is at most one edge of G containing {σ (u), σ (v)}. Now, let p = 2E/e(G). Let H be a random subgraph of G obtained by picking each edge of G independently with probability p.LetX denote the number of edges in H and let Y denote the number of copies of
By deleting one edge from each copy of F (r) in H, we get a subgraph G of H with at least E edges and no copy of F (r) . Hence we may assume that E e /n 2e-v > E, from which we get
(here we use v < 2e). Using the Chernoff bound (Lemma 3.4), one can show that P[X < E] < 1/2 for sufficiently large n. Also, by Markov's inequality, P[Y > 2E[Y]] < 1/2. So with positive probability, H has at least E edges and contains at most O(E e /n 2e-v )copiesofF (r) .
Let us remark that the bound given in Definition 2 is specific to the setting where the host graph is linear and embedded graphs is an expansion. In a different setting, the supersaturation problem typically becomes very different and the expected optimal count is expected to be different. In fact, as mentioned in the Introduction, the thresholds for forcing even just one copy of F (r) can be very different depending on whether or not we require the host graph to be linear.
An r-graph G is r-partite if there exists a partition of V(G)intor subsets A 1 , ..., A r such that each edge of G contains exactly one vertex from each A i .Wecall(A 1 , ..., A r )anr-partition of G. Given an r-partite r-graph G with an r-partition (A 1 , ..., A r )and1 i < j r,wedefinethe (i, j)-projection of G, denoted by P i,j (G), to be a 2-graph with edge set
The following proposition follows immediately from the definition of P i,j (G) and the linearity of G. Proposition 2.2. Let G be a linear r-partite r-graph with an r-partition (A 1 , ..., A r ).L e t1 i < j r. Then the mapping f :
Next we give the following slightly technical definition of what we call projection-restricted supersaturation in linear r-partite r-graphs. In the next section we show that we can obtain the supersaturation of an expansion F (r) in linear r-graphs from projection-restricted supersaturation in linear r-graphs which have an almost-regular 2-projection. Definition 3. Given a 2-graph F with v vertices and e edges, r 2andc a positive real. For a linear, r-partite r-graph G and any 2-projection of it, say P, we say that (G, P) c-supersaturates F (r) if
Note that for 2-graphs, Definition 3 coincides with Definition 2.
Erdős and Simonovits [7] proved the following 'regularization' theorem for 2-graphs.
). Let 0 <α<1 be a real and q = 20 • 2 (1/α) 2 . There exists n 0 = n 0 (α) such that if G is a (1, 1 + α)-dense graph on n n 0 vertices then there exists a q-almost-regular subgraph of G, say G ,whichis(2/5, 1 + α)-dense such that v(G ) > n α(1-α)/(1+α) . Theorem 3.1 is a useful tool for the Turán problem for H. Indeed, given a dense enough G,we may first find an almost-regular subgraph G that has similar density to G and look for a copy of H in G . This theorem itself is not sufficient for establishing supersaturation results for 2-graphs since we aim to force many copies of H in G. By going into G , we might lose many copies of H. What we probably need is the existence of a collection of dense enough almost-regular subgraphs of G which together supply the number of copies of H that we need. Indeed, this is the rough idea behind the following lemma, which may be viewed as some kind of extension of Theorem 3.1.For any s, t integers, t s 1, and a graph H,wedefine
Lemma 3.2. Let α be a real and s, t integers, where 0 <α<1 and t s 1, then there exist positive reals C 0 = C 0 (α, s, t) and q = q 3.2 (α, s, t) such that the following holds. For every C C 0 ,ifGisa (C,1+ α)-dense graph then it contains a collection of edge-disjoint subgraphs G 1 , ..., G m satisfying
Proof. While we specify the choice of q explicitly, we do not do so for C 0 . We assume C 0 is sufficiently large as a function of α, s and t.Let p = 2 max{4/α,(2s+t)/(t-s+1)} and q = 8p. By the definition of p,wehave p α 16 and p t-s+1 2 2s+t . (
Suppose G has n vertices. Let us partition V(G)i n t op sets A 1 , ..., A p of almost equal sizes, i.e. each of size n/p or n/p , such that A 1 contains vertices of the highest degrees in G.F o r convenience, we will drop the ceilings and floors in our arguments as doing so does not affect the arguments except for the slight changes to constants.
We now prove our statement by induction on n.W h e nn < q the claim holds trivially, since either G itself is q-almost-regular or no (C,1+ α)-dense graph on n < q vertices exists. For the induction step, we consider two cases. Since (G ) (G ) pd and δ(G
. So the claim holds by letting our collection of subgraphs be {G }.
Case 2. The number of edges in G with at least one endpoint in A 1 is more than 1 2 e(G).
Let I ={2, ..., p}.Define
Recall that p α 16. By the definition of I 2 and the fact that n i = 2n/p for each i ∈ [p], we have
Hence
For each i ∈ I 1 since e i Cn 1+α i and n i < n, by the induction hypothesis, G i contains a collection of edge-disjoint subgraphs G 1 i , ..., G m i i each of which is q-almost-regular and ( 1 4 C,1+ α)-dense such that
Hence, by (3.2), (3.3), p t-s+1 2 2s+t , and the convexity of the function x s ,wehave
Hence the claims holds by letting {G j i : i ∈ I 1 ,1 j m i } be our collection of subgraphs of G.This completes Case 2 and the proof. Now we are ready to state our main result of the section. Informally, it says that we can obtain the supersaturation of an expansion F (r) in linear r-graphs from projection-restricted supersaturation in linear r-graphs which have an almost-regular 2-projection. Theorem 3.3. Let α ∈ (0, 1) be a real and r 2. Let F be a graph with v vertices and e edges, where e v. There exists a real q = q(α, F) 1 such that the following holds. Suppose C, c > 0 are constants such that, for every linear r-partite r-graph G that has a (C,1+ α)-dense and q-almostregular 2-projection P, (G, P) c-supersaturates F (r) . Then there exist C , c such that every linear r-partite r-graph that is (C ,1+ α)-dense c -supersaturates F (r) . Proof. Let s = e, t = 2e -v. By our assumption, t s 1. We show that the theorem holds for q to be chosen as q 3.2 (α, s, t), derived from Lemma 3.2 applied with constant α, s and t. Finally, let
Let G be an r-partite r-graph on n vertices such that e(G) 4Cn 1+α . Suppose G has an r-partition
there exists a collection of edge-disjoint subgraphs H 1 , ..., H m of H, each of which is (C,1+ α)-dense and q-almost-regular, such that
, since H i is (C,1+ α)-dense and q-almost-regular, by the hypothesis of the theorem, (G i , H i ) c-supersaturates F (r) .Thatis,
Since the H i 's are edge-disjoint, the G i 's are also edge-disjoint (i.e. there is no edge contained in two different G i 's). Thus we have
Theorem 3.3 says that to establish supersaturation of F (r) in an n-vertex linear r-partite r-graph G, we may assume G has a dense enough almost-regular 2-projection P. Our next lemma can be used to show that we may further assume P to have edge density exactly (v(P) 1+α ), where α is anyfixedrealforwhichex(n, F (r) ) = O(n 1+α ). The proof uses random sampling and the classical Chernoff bound, which we state here for completeness. Lemma 3.4 (Corollary 2.3 of [16]). Given a binomially distributed variable X ∈ BIN (n, p) we have
Lemma 3.5. Let r 2 be an integer. Let α ∈ (0, 1) be a real. Let F be a graph with v vertices and eedges,wheree v. There is a constant m 0 = m 0 (α) such that the following holds for all M m 0 . Suppose D, q, c > 0 arerealswhereq 1 such that, for every linear r-partite r-graph G that has a 2-projection P on m M vertices satisfying Dm α δ(P ) (P ) 3qDm α ,wehavethat(G , P ) c-supersaturates F (r) . Then, for every linear r-partite r-graph G that has a (qD,1+ α)-dense and q-almost-regular 2-projection P on at least M vertices, (G, P) c/2 e+1 -supersaturates F (r) .
Proof. The choice of m 0 will be given implicitly in the proof. Let G be a linear r-partite graph with an r-partition (A 1 , A 2 , ..., A r ), where without loss of generality P = P 1,2 (G)is(qD,1+ α)-dense, q-almost-regular, and has m = v(P) M vertices. The idea is to sample randomly a subgraph G of G with an appropriate edge probability, count F (r) in G , and then use it to bound the count of F (r) in G.Nowletδ(P), (P)andd denote the minimum, maximum and average degrees in P, respectively. Then
Since P is q-almost-regular, we have δ(P) d/q 2Dm α . Let p = 2Dm α /δ(P) and let G be a random subgraph of G, obtained by including each edge of G in G independently with probability p.Then
Since G is linear and
and similarly E[d G (v)] 2Dm α . Now random variables d G (v)a n de ( G ) have binomial distributions. Hence, using Markov's inequality and Chernoff 's inequality, one can show that
P[e(G ) < p 2 e(G)] < 1 4 and
In some of the inequalities above, we used Chernoff (and the union bound for the last one). The desired inequalities hold when m is large enough as a function of α, which is guaranteed by choosing m 0 to be large enough. So there exists a subgraph G of G satisfying e(G )
and that for each
Now let P = P 1,2 (G ). Since there is a bijection between E(G )andE(P ), for each v ∈ V(P), we have
Thus, by the hypothesis of our theorem, (G , P ) c-supersaturates F (r) .By(3.4), we have
Applying Theorem 3.3 and Lemma 3.5 we obtain the following reduction tool for supersaturation of expansions. In this paper we use it on C (r) 2k .
Corollary 3.6. Let r 2 be an integer and α ∈ (0, 1) a real. Let F be a graph with v vertices and ee d g e s ,w h e r ee v. Let q = q 3.3 (α, F) be given as in Theorem 3.3 and m 0 = m 0 (α) be given as in Lemma 3.5. Suppose there exist reals D, λ, M, c > 0,whereλ 3q, M m 0 , such that, for every linear r-partite r-graph G that has a 2-projection P on m M vertices satisfying Dm α δ(P) (P) λDm α ,w eh a v et h a t(G, P) c-supersaturates F (r) . Then there exist C , c such that every (C ,1+ α)-dense linear r-graph G c -supersaturates F (r) .
Proof. Suppose there exist reals D, λ>0, where λ 3q, such that, for every linear r-partite rgraph G that has a 2-projection P on m M vertices satisfying Dm α δ(P) (P) λDm α ,we have that (G, P) c-supersaturates F (r) . By Lemma 3.5, there exists a constant c 3.5 such that, for every linear r-partite r-graph G that has a (qD,1+ α)-dense q-almost-regular 2-projection P on at least M vertices, (G, P) c 3.5 -supersaturates F (r) .S e tC = max{qD, M}. Then, for every linear r-partite r-graph G that has a (C,1+ α)-dense q-almost-regular 2-projection P,w eh a v et h a t( G, P) c 3.5supersaturates F (r) (as P must have at least C M vertices). Applying Theorem 3.3 with the C above and c = c 3.5 , there exist constant C 3.3 and c 3.3 such that every linear r-partite r-graph that is (C 3.3 ,1+ α)-dense c 3.3 -supersaturates F (r) .
Let C = (r r /r!)C 3.3 .LetG be a linear (C ,1+ α)-dense r-graph. By a well-known fact, G contains an r-partite subgraph G with e(G ) (r!/r r )e(G). Clearly, G is (C 3.3 ,1+ α)-dense. By our discussion above, G c 3.3 -supersaturates F (r) .HenceGc 3.3 -supersaturates F (r) . Corollary 3.7. Let r, k 2 be integers. There exist constants m k , q k depending only on k such that the following holds. Suppose there are reals D, λ, M, c > 0,whereλ q k DandM m k ,suchthat, for every n-vertex linear r-partite r-graph G that has a 2-projection P on m M vertices satisfying Dm
In this short section, we give a brief outline of the proof strategy for r = 2. The strategy for r 3 is similar and relies on establishing some coloured version of the r = 2 case. See Section 6 for details. By Corollary 3.7, to prove Theorem 1.1 for r = 2, it suffices to prove that every almostregular n-vertex bipartite graph with average degree (n 1/k ) contains at least (n 2 ) linear cycles of length 2k. Suppose we are given an n-vertex almost-regular bipartite graph G with average degree (n 1/k ). The key ingredient is to show that for each vertex x, there exists a j = j(x)
such that the number of C 2k 's containing some vertex that lies in the jth distance classes from x is at least (n 1+j/k ). Suppose we have established that. Then, for some t ∈ [k -1], there are (n) different vertices x in G with j(x) = t.S i n c e (G) = O(n 1/k ) by almost-regularity, any vertex in G lies in the jth distance class of at most O(n t/k ) different vertices x.H e n c eG contains at least (n • n 1+t/k /n t/k ) = (n 2 ) distinct C 2k 's and we are done. To establish the above-mentioned key ingredient, we adapt the Faudree-Simonovits method as follows. From each vertex x we use breadth-first search (BFS) to obtain the distance classes L 0 ={x}, L 1 , L 2 , .... Using the minimum degree assumption, we can find the smallest i ∈ [k -1] such that the subgraph G[L i ∪ L i+1 ]ofG induced by L i ∪ L i+1 has average degree at least some given constant, depending on k and i. The choice of i together with the condition δ(G) = (n 1/k ) also ensures that |L i |= (n i/k )ande(G[L i ∪ L i+1 ]) = (n (i+1)/k ). Let T be a BFS tree rooted at x with vertex set L 0 ∪ L 1 ∪•••∪L i . We divide vertices in L i+1 into L + i+1 and L - i+1 , where the former consists of those in L i+1 that send edges in G to many components of Tx (i.e. many different subtrees of T under x) and the latter consists of the rest of L i+1 . If most of the edges of G[L i ∪ L i+1 ]gointoL + i+1 , we build many paths of length 2k -2i in G[L i ∪ L i+1 ] whose two ends lie in L i and under different children of x in T. These paths then extend to different C 2k 's going through x. If most edges of G[L i ∪ L i+1 ]g oi n t oL - i+1 , then we do some cleaning to find vertex-disjoint subgraphs of G[L i ∪ L i+1 ] which together capture at least a constant proportion of the edges of G[L i ∪ L i+1 ] such that each is attached to a different component of Tx. Since the height of these components of Tx, viewed as subtrees rooted at children of x, is one shorter than that of T, we can apply some form of induction to show that these subgraphs together with the different subtrees of T that they are attached to collectively supply the needed collection of C 2k 's.
Let us now describe a variant of this method, which avoids induction (on the height of a BFS tree) and appears more versatile. The key to the Faudree-Simonovits method is that any path of length p in G[L i ∪ L + i+1 ]thatstartsinsomevertexa in L i and ends in some vertex b in L + i+1 can be extended at b toendatavertexc in L i so that a and c lie under different children of x in T. This allows us to round out the path into a cycle through x of length p + 2i + 1, as the paths in T from a and c to x are internally disjoint. The useful feature of a vertex v in L + i+1 is that it is well-linked to x by some measure. A variant to the Faudree-Simonovits method is to locate for each vertex v in L i+1 some vertex r(v)i nT (which may not be x itself) that v is well-linked to, which we may call the 'local root' for v (see Lemma 5.1 for details). Then we partition L i+1 based on the level r(v) lies in over all v ∈ L i+1 . This new approach has the advantage that even if T is replaced with some non-tree structure, we will still be able to extend a path in G[L i ∪ L i+1 ]toa cycle through a local root in a well-controlled way. Indeed, in [5], this variant is key to establishing that ex ℓ (n, C (r) 2k+1 ) = O(n 1+1/k ). In our proof of Theorem 1.1 we will use the Faudree-Simonovits inductive approach for r 3 and the 'local root' approach for r = 2. As we mentioned before, one could prove Theorem 1.1 in its generality using one of the two approaches.
Lemma 5.1. Let T be a tree of height h with a root x. For each v ∈ V(T),letT v be the subtree of T rooted at v. Let b be a positive integer. Let S be a set of at least bh + 1 vertices in T. Then there exists a vertex y at distance i from x, for some 0 i h -1,suchthat|V(T y ) ∩ S| |S|-ib and that for any child z of y in T, |V(T z ) ∩ S| |V(T y ) ∩ S|-b.
Proof. We define a sequence of vertices as follows. Let x 0 = x. Among all the children of x 0 ,let x 1 be one such that T x 1 contains the maximum number of vertices in S. Among all the children of x 1 ,letx 2 be one that contains the maximum number of vertices in S, and so on. Suppose the sequence we define this way is x 0 , x 1 , ..., x p ,wherep h and |V(T x p ) ∩ S|=1. Since |V(T x 0 ) ∩ S| bh + 1and|V(T x p ) ∩ S|=1, there must exist a smallest index 0 i < p such that |V(T x i+1 ) ∩ S| |V(T x i ) ∩ S|-b.Lety = x i .Theny satisfies the claim.
Given a bipartite graph G with a bipartition (A, B), we will use d A (G)andd B (G)todenotethe average degree in G of vertices in A and in B, respectively. Also, we will use δ A (G)andδ B (G)to denote the minimum degree in G of vertices in A and in B, respectively. When the graph G is clear, we will drop G from the notation above and write d A , d B , δ A , δ B , respectively. Lemma 5.2. Given a bipartite graph G with a bipartition (A, B), there exists a subgraph G of G with a bipartition (A , B ) where A ⊆ A, B ⊆ Bsuchthate(G ) 1 2 e(G) and that δ A (G ) 1 4 d A (G) and δ B (G ) 1 4 d B (G).
Let us iteratively delete any vertex in A whose degree becomes less than 1 4 d A and any vertex in B whose degree becomes less than 1 4 d B . We continue until we no longer have such vertices or run out of vertices. Let G denote the remaining graph. Let A denote the set of remaining vertices in A and B the set of remaining vertices in B.T h e number of edges removed in the process is at most
Hence G is non-empty. By the procedure, each vertex in A has degree at least 1 4 d A and each vertex in B has degree at least 1 4 d B in G .
We also need the following crude bound on the number of paths of a given length in an asymmetric bipartite graph. Even though sharper estimates exist in the literature, the lemma suffices for our purposes and is self-contained.
Lemma 5.4. Let h, k be positive integers where h k. Let G be a graph. Let T be a tree of height h in G with a root x. For each i ∈ [h],letL i be the set of vertices at distance i from x in T. Let W be a set of vertices in V(G) \ V(T). Let F denote the bipartite subgraph of G containing all the edges of G between L h and W. Let d L , d W be the average degree in F of vertices in L h andinW,respectively. Suppose d L , d W 16k 2 . Then there exists j ∈ [h] such that the number of C 2k 's in G that contain some vertex in L j is at least
,where
Proof. For each vertex y in T,letT y denote the subtree of T rooted at y. We clean up F to get a subgraph F of F as follows. First we delete vertices w in W with d F (w) kh.LetW denote the set of remaining vertices in W.Letw ∈ W . Applying Lemma 5.1 to T and S = N F (w), we conclude that there exists some vertex r(w) ∈ L j for some j ∈ [h -1] such that there are at least |N F (w)|-kj members of N F (w) that lie in T r(w) . Furthermore, for any child z of r(w)inT, there are at least k members of N F (w) ∩ V(T r(w) ) that lie outside T z .ToformF , we include edges between w and N F (w) ∩ V(T r(w) )foreachw ∈ W . By our assumptions, in forming F from F we have deleted at most kh edges incident to each w ∈ W.Hence e(F ) e(F) -kh|W|.
For each j ∈ [h -1], let W j ={w ∈ W : r(w) ∈ L j } and let F j be the subgraph of F induced by
where the last inequality follows from the fact that e(F)
. By our definition of F and F j ,inF j each w ∈ W j has edges to precisely one S e .LetN e = N F j (S e ). Then N 1 , ..., N t partition W j and F j is the vertex-disjoint union of
Claim 1. Every (2m -1)-path P in F j extends to a C 2k in G that contains a vertex in L j .
w h e r ev 1 ∈ S e and v 2m ∈ N e .T h e nr(v 2 ) = r(v 2m ) = z e .L e ta denote the child of z e in T z e such that v 1 lies under a.S i n c er(v 2m ) = z e , by definition, v 2m has at least k neighbours in T z e that lies outside T a . Among them, at least one, say u, lies outside V(P). Let Q, Q denote the unique (v 1 , z e )-path and the unique (u, z e )-path in T z e , respectively. Since v 1 and u lie under different children of
By Claim 1 the number of C 2k 's in G that contain a vertex in L j is at least the number of (2m -1)-paths in F j . To complete our proof, it suffices to find a corresponding lower bound on the number of (2m -1)-paths in F j . For convenience, let A = L h and B = W j .Letd A , d B denote the average degrees in F j of vertices in A and B, respectively. By (5.1),
By Lemma 5.3 with p = m -1, the number of (2m -1)-paths in F j is at least
This completes our proof.
In the next theorem, we use Lemma 5.4 to quickly obtain the desired lower bound on the number of C 2k 's in almost-regular n-vertex graphs whose number of edges is (n 1+1/k ). Theorem 5.5. Let k 2 be an integer. Let D, λ>0 be constants where D 64k 2 and λ 1.L e t n 0 = (8λ) k .L e tGb ea nn -v e r t e xb i p a r t i t eg r a p h ,n n 0 such that, for each v ∈ V(G),D n 1/k d(v) λDn 1/k . Then there exists a positive constant β = β(D, λ, k) such that t C 2k (G) βn 2 .
Proof. For each x ∈ V(G), let L i (x) denote the set of vertices at distance i from x.Leth(x)bethe minimum i k -1 such that |L i+1 (x)|/|L i (x)| < n 1/k . Clearly h(x) exists or else we run out of vertices. Let h = h(x). Let T be a BFS tree rooted at x that includes L 0 (x), L 1 (x), ..., L h (x). By our assumption,
Let F be the bipartite subgraph of G consisting of all the edges of G between L h (x)andL h+1 (x). The total number of edges of G incident to L h (x)isatleastDn 1/k |L h (x)|/2. Among them, the number of edges that are incident to
Let d A , d B denote the average degrees in F of vertices in L h (x)andL h+1 (x), respectively. Then
and
By Lemma 5.4, there exists a j ∈ [h -1] such that the number of C 2k 's in G that contain a vertex in L j (x)isatleast
Let us denote this j value by j(x).
Let us fix such a t. By our discussion, for each x ∈ S t , the number of C 2k 's that contain a vertex in L t (T x )isatleastα k n 1+t/k .Ontheother hand, a vertex y lies in L t (T x )foratmost[λDn 1/k ] t different x. Hence the number of distinct C 2k 's in G is at least
The claim holds by setting
Proof of the r = 2 case of Theorem 1.1. Theorem 5.5 applies as long as D 64k 2 , λ 1, and n 0 (8λ) k . To apply Corollary 3.7,w es e tD = max{64k 2 , m k }, λ = q k D and M k = (8λ) k , where m k , q k are as given in Corollary 3.7. The claim follows readily from Corollary 3.7.
Proof. Let us independently assign each vertex x in V(G) a colour from [k] chosen uniformly at random. Let S i be the vertices of assigned colour i.Foravertexv ∈ A ∪ B,weletX i (v) denote the number of edges (which are (r -1)-sets) in L G (v) that are completely contained in S i .Foreac h I ∈ L G (v),
Since G is linear, edges in L G (v) are pairwise disjoint. Hence the events {I ⊆ S i } are independent for different
. By the Chernoff bound,
Therefore the probability that the event
when n 2 is large enough and n n 2 . Thus there exists some colouring which guarantees that every
Before we establish supersaturation of C (r) 2k 's in linear r-partite r-graphs that have an almostregular 2-projection with the right density, we need another lemma. Given an r-graph G,where r 2, and S ⊆ V(G), S is a vertex cover of G if S contains at least one vertex of each edge of G. Lemma 6.3. Let r 2.LetGbeanr-gr aphandSavertexcoverofG.ThereexistasubsetS ⊆ S and a subgraph G ⊆ Gsuchthate(G ) (r/2 r )e(G) and that, for all e ∈ E(G ), |e ∩ S |=1.
Proof. Let S be a random subset of S obtained by including each vertex of S randomly and independently with probability 1/2. Let e be any edge of G. Suppose |e ∩ S|=m.Then1 m r.The probability that exactly one of these m vertices of e ∩ S is chosen for S is m/2 m r/2 r .S ot h e expected number of edges of G that meet S in exactly one vertex is at least (r/2 r )e(G). So there exists S ⊆ S such that at least (r/2 r )e(G) of the edges meet S in exactly one vertex. Let G be the subgraph of G consisting of these edges.
We now introduce the following adaptation of the BFS tree to linear hypergraphs. Definition 4 (maximal rooted rainbow tree). Given r 3, let G be a linear r-partite r-graph with two of its partition classes being A and B,andlett 0 be an integer. Suppose there exists a partition of V(G)intoS 1 , S 2 , ..., S t such that, for every v ∈ A ∪ B and for every i
For every x ∈ A ∪ B, we define a tree T x , rooted at x and of height t, together with a colouring ϕ of its edges by (r -2)-sets as follows. We define the tree by defining its levels L i iteratively. The L i 's will alternate between being completely inside A and being completely inside B.W ithoutlossof generality, suppose x ∈ A.ThetreeT x is defined symmetrically if x ∈ B.
We say that a sector S j is dominant for a vertex w ∈ W if
We say that w ∈ W is strong if it has no dominant sector and weak otherwise. Note that, by our definition, if w ∈ W has a dominant sector then there is only one such dominant sector for w. Let W s be the set of strong vertices and let W w be the set of weak vertices, respectively. Let H s denote the subgraph of H induced by L i and W s ,andletH w denote the subgraph of H induced by L i and W w . The argument splits into two cases, depending on whether the majority of the edges of H lie in H s or in H w . In the first case we build the necessary number of rainbow 2k-cycles going through the vertex x (so in the outcome of the theorem we have j = 0asx ∈ L 0 ). In the second case we use induction to find rainbow 2k-cycles in T(x j )'s for many j. 1. e(H s ) e(H)/2. (6.2) Let d avg (L i )andd avg (W s ) denote the average degrees in H for vertices in L i and W s respectively. Then by (6.2), we have d avg (L i ) d/2, d avg (W s ) b/2. By Lemma 5.2, there is a subgraph H of H s with bipartition (A, B), A ⊆ L i , B ⊆ W s , such that e(H ) e(H s ) 2 e(H) 4 , δ A (H ) d avg (L i ) 4 d 8 , δ B (H ) d avg (W s ) 4 b 8 . (6.3) Since b, d 16 i (2m + 2)k, clearly b/8, d/8 (4m + 4)k (4m + 4)(ki -1). Since c is strongly proper on H, by Lemma 6.1 with p = ki -1, the number of rainbow paths of length 2(k
Proof of claim. By symmetry, we may assume that v 1 ∈ A, v 2(k-i) ∈ B. For convenience, let t = 2(ki). It suffices to show that there exists u ∈ N H (v t ) (note that u lies in L i but does not necessarily lie in A) such that P ∪ v t u is a rainbow path in H and that S(v 1 ) = S(u). Indeed, suppose such a u exists. Then, since S(v 1 ) = S(u),theuniquepathQ 1 in T x from v 1 to x and the unique path
Nowweshowthatsuchau exists. Since v t ∈ W s , by definition, |N H (v t ) \ S(v 1 )| 2km.Since ϕ is a strongly proper edge-colouring using m-sets, {w ∪ ϕ(w): w ∈ N H (v t ) \ S(v 1 )} is an (m + 1)uniform matching of size |N H (v t ) \ S(v 1 )| 2km. Since clearly |V(P) ∪ C (P)| < 2km, there exists u ∈ N H (v t ) \ S(v 1 ) such that (w ∪ ϕ(w)) ∩ (V(P) ∪ C (P)) =∅.I ti se a s yt os e et h a tP ∪ v t u is a rainbow path in H.Also,u / ∈ S(v 1 )bychoice.
Case 2. e(H w ) e(H)/2.
In this case we have e(H w ) d 2 |L i |, e(H w ) b 2 |W|. (6.4) Recall that x 1 , ..., x p are the children of the root x and for each j ∈ [p], S j = V(T(x j )) ∩ L i .F o r each j ∈ [p], let W j be the set of vertices in W w whose dominant sector is S j .N o ww er u nt h e following 'cleaning' procedure. For every vertex y ∈ W w we only keep those edges in H w joining y to vertices in its dominant sector. Let H denote the resulting subgraph of H w . By the definition of W w , every vertex y ∈ W w satisfies d H (y) |N H (y)|-2km. Hence e(H ) e(H w ) -2km|W w |. Since b 8km,by(6.4) e(H w ) 4km|W|. Therefore e(H ) 1 2 e(H w ) 1 4 e(H). (6.5)
For each j ∈ [p], let H j denote the subgraph of H induced by S j ∪ W j .NotethattheH j 's are pairwise vertex-disjoint. We want to apply induction to those T(x j ) ∪ H j where H j is relatively dense from both partite sets. For that purpose we partition the index set [p] as follows. Let
By the definition and disjointness of the H j 's, we have
j∈I 1 ∪I 2 e(H j ) d 16 |L i |+ b 16 |W| 1 8 e(H). Hence j∈I 3 e(H j ) 1 8 e(H). (6.6) For each j ∈ I 3 , by definition, we have e(H j ) d 16 |S j | and e(H j ) b 16 |W j |.
Since T(x j ) has height i -1andd/16, b/16 > (16) i-1 (2m + 2)k, by the induction hypothesis with d, b replaced with d/16 and b/16 respectively, there exists q = q(j) such that the number of rainbow 2k-cycles in T(x j ) ∪ H j that contain a vertex in level q(j)ofT(x j )isatleast
e(H j ).
For each t = 0, ..., i -2, let I 3,t ={j ∈ I 3 : q(j) = t}. By the pigeonhole principle, there exists t ∈{0, ..., i -2} such that
Let us fix such a t. By our earlier discussion and the fact that vertices in level t of each T(x j )for j ∈ I 3,t lie in level t + 1ofT x , the number of rainbow 2k-cycles in G that contain a vertex from L t+1 is at least
with the choice of
Hence in this case the lemma holds for q = t + 1.
We are finally ready to prove the supersaturation statement of C (r) 2k for linear r-partite r-graphs G that have a 2-projection on two parts A, B that is almost-regular and have a number of edges exactly (|A ∪ B| 1+1/k ). By Corollary 3.7 this would imply Theorem 1.1 for all r 3. For this we first define an adequate partition V(G)intoS 1 , ..., S k . From each vertex x we define the maximal rainbow tree T x rooted at x relative to the partition (S 1 , ..., S k ). Then we apply Lemma 6.5 to find many rainbow 2k-cycles containing a vertex from some fixed level of T x , which corresponds to linear 2k-cycles in G. Summing over all x and eliminating overcount, we get a lower bound on the number of 2k-cycles in G. Theorem 6.6. Let k, r 2 be integers. Let D be a constant such that D 2 r+1 rk r (16) k . There exist n 0 such that if G is a linear r-partite r-graph with an r-partition A 1 , ..., A r such that |A 1 ∪ A 2 |= n n 0 and for every
where λ 1 is a real, then there exists α = α(k, r, λ) such that t C (r) 2k (G) αn 2 .
Proof. The choice of α will be specified at the end of the proof. We will choose n 0 to be large enough that n 0 n 6.2 (D, k, r,1/k), where n 6.2 is specified in Lemma 6.2.L e tS 1 , S 2 , ..., S k be a partition obtained by applying Lemma 6.2 to G.Inparticular,foreachx ∈ A 1 ∪ A 2 and j ∈ [k], we have
For each x ∈ A 1 ∪ A 2 ,letT x be a maximal rainbow tree of height k rooted at x relative to the partition S 1 , ..., S k , as described in Definition 4. The proof is similar to that of Theorem 5.5.For each x,wefindani ∈ [k] such that (i) there exists some set W and a bipartite subgraph H x induced by L i and W which has high average degree from both partite sets; (ii) the colouring c on T x is extended to also include a strongly proper edge-colouring of H x such that C (H x ) ∩ C (T x ) =∅.
We then use Lemma 6.5 to find many rainbow 2k-cycles that contain some vertex in some fixed level of T x . Below are the details. Fix x and write T for T x .Forj = 0, ..., k,letL j be defined as in Definition 4 and let ϕ be the assigned edge-colouring of T given in Definition 4.Since|L
By the construction of T, |L i+1 | is equal to the size of a maximum matching in F.Since F is an (r -1)-graph, we have τ (F) (r -1)α (F), where τ (F)andα (F) denote the vertex cover number and matching number of F, respectively. Let W be a minimum vertex cover of F.Then
We define a bipartite graph H x between L i and W and extend the edge-colouring ϕ restricted on T to an edge-colouring of T ∪ H x as follows. We go through the edges of F one by one.
For each e ∈ E(F ), since G is linear, there is a unique v ∈ L i such that v ∪ e ∈ E(G). Also by our definition of F , e ∩ W has exactly one vertex w. We include vw in H x and let ϕ(vw) = e \{w}.By the linearity of G and our discussion so far, each edge of F yields a different edge of H x .Thereis a bijection between E(F )andE(H x ). Moreover, C (H x ) ∩ C (T ) =∅, since colours used on H x are (r -2)-sets in S i+1 while
Hence we have
Also, by our choice of i, 16) k .SoT and H x satisfy the conditions of Lemma 6.5 with constants b, d and m = r -2. By Lemma 6.5, there exists some q = q(x)with 0 q i and some a i = a i (i, k) > 0 such that there are at least a i (bd) k-i-1+q e(H x ) rainbow C 2k 's in T ∪ H x that contain some vertex in level L q of T .Now|L i | n i/k by definition, e(H x ) (n (i+1)/k )b y( 6.8). Also, d = (n 1/k ). Hence the number of rainbow C 2k 's in T ∪ H x that contain some vertex in L q is at least βn (k-i-1+q)/k • n (i+1)/k = βn (k+q)/k for some β = β(k, r) > 0.
So in G there are at least βn (k+q)/k different linear 2k-cycles each of whose skeletons contains some vertex in L q .
For each t ∈ [k -1], let S t ={x ∈ V(G) | q(x) = t}. By the pigeonhole principle, for some t ∈ [k -1], |S t | n/(k -1). Let us fix such a t.LetM denote the number of triples (C, x, y), where x ∈ S t , C is a linear 2k-cycle in G whose skeleton contains a vertex in L t (T x )andy is a vertex on the skeleton of C that lies in L t (T x ). Let µ denote the number of different linear 2k-cycles C in G that are involved in these triples. By our discussion above, for each x ∈ S t , there are at least βn (k+q)/k different C. For each such C there is at least one y.So M |S t |βn (k+t)/k > (β/k)n 2+t/k . (6.10)
On the other hand, for each of the µ linear 2k-cycles C involved, there are at most 2k different choices of y.F o rfi x e dy, there are at most (λDn 1/k ) t choices of x since such an x is at distance at most t from y in the (1, 2)-projection P 1,2 (G)ofG, which has maximum degree at most λDn 1/k .So M µ(2k)(λDn
1/k ) t . (6.11) Combining (6.10)and(6.11) and solving for µ,weget µ β 2k 2 (λD) t n 2 . Let α = β 2k 2 (λD) k . Then α is a function of k, r, λ and we have t C (r) 2k (G) µ αn 2 .
We are now ready to prove the r 3caseofTheorem1.1.
Proof of the r 3 case of Theorem 1.1. First note that Theorem 6.6 can be rephrased by saying that if G is linear r-partite r-graph that has a 2-projection P on at least m n 0 vertices such that Dm
First we would like to mention that the reduction to proving the supersaturation of C 2k for n-vertex host graphs G with density exactly at (n 1+1/k ) is crucial to establishing our general theorem. For graphs G with density much higher than n 1+1/k , the bound resulting directly from BFS is worse than the optimal c(e(G)/v(G)) 2k . One reason is that the subgraph of G induced by the early levels of a BFS tree is potentially much denser than a tree. In this case, if we use the BFS structure we may lose many C 2k 's in counting. For all integers k, p 2, the theta graph p,k is the graph consisting of p internally disjoint paths of length k sharing the same endpoints. Faudree and Simonovits [12] showed that ex(n, p,k ) = O(n 1+1/k ). The method of our paper can be used to establish the supersaturation of the r-expansion (r) p,k (where r 2) of p,k in linear r-graphs. When r = 2 this establishes the truth of Conjecture 1 for H = p,k with α = α = 1 -1/k. Again, the lower bound is tight up to a multiplicative constant, obtained by taking a random graph of an almost complete Steiner system. Since the arguments are essentially the same, we have not included the results involving theta graphs in this paper.
It would be very interesting to establish the supersaturation of odd linear cycles in linear r-graphs, for r 3. Toward this end, in [5] it is shown that when r 3wehaveex ℓ (n, C (r) 2k+1 ) = O(n 1+1/k ), which is very different from the 2-uniform case, where for all sufficiently large n it is known that ex(n, C 2k+1 ) = n/2 n/2 . The proof of this theorem is much more involved than its counterpart for even linear cycles. It is unclear if a supersaturation statement similar to Theorem 1.1 holds for C (r) 2k+1 . At least, our methods do not readily give this. We raise it as an open question.
Question 5. Let k, r be integers where k 2, r 3. Do there exist positive constants C and c depending only on k and r such that every n-vertex linear r-graph G with e(G) Cn 1+1/k contains at least c(e(G)/v(G)) 2k+1 copies of C (r) 2k+1 ?
Very recently, Balogh, Narayanan and Skokan [1] obtained a balanced supersaturation result for linear cycles of all lengths in general r-graphs. Note that this is a different setting from ours, as in our case host graphs are linear, and hence are sparse, while they are working with dense ones. As Morris and Saxton did for even cycles in graphs, Balogh, Narayanan and Skokan used their supersaturation result to obtain a bound on the number of of n-vertex C (r) m -free r-graphs. It would be interesting to obtain such a balanced version of supersaturation for even linear cycles in linear r-graphs.