Hypergraphs with few Berge paths of fixed length between vertices
Zhiyang He Michael Tait

Unified Perceptual Parsing for Scene Understanding
    Tete Xiao1*, Yingcheng Liu1*, Bolei Zhou2*, Yuning Jiang3, Jian Sun4
    December 30, 2023
========================================================================




In this paper we study the maximum number of hyperedges which may be in an r-uniform hypergraph under the restriction that no pair of vertices has more than t Berge paths of length k between them. When r=t=2, this is the even-cycle problem asking for ex(n, C_2k). We extend results of Füredi and Simonovits and of Conlon, who studied the problem when r=2. In particular, we show that for fixed k and r, there is a constant t such that the maximum number of edges can be determined in order of magnitude. 




§ INTRODUCTION


The Turán number for a fixed graph F is the maximum number of edges that an n vertex graph may have without containing F as a subgraph. This function is denoted by ex(n, F) and its study for various graphs F is a classical problem in extremal combinatorics. The celebrated Erdős-Stone theorem <cit.> gives that 

    ex(n, F) = (1 - 1/χ(F)-1 + o(1)) n2,

and asymptotically solves the problem whenever χ(F) ≥ 3. However, for bipartite F it only gives ex(n, F) = o(n^2), and determining the order of magnitude for the Turán number of a bipartite graph in general is a notoriously difficult problem (see <cit.> for a survey). 

When F = C_2k, the study of ex(n, C_2k) is known as the even-cycle problem. This problem was first studied in 1938 by Erdős <cit.> and has since become a central problem in extremal graph theory. A general upper bound of ex(n, C_2k) = O_k(n^1+1/k) was first published by Bondy and Simonovits <cit.>. Since then, improvements have been made to the multiplicative constant <cit.>, and constructions have been found showing that the order of magnitude is correct for k∈{2,3,5} <cit.>. However, besides C_4, C_6, and C_10, the order of magnitude is unknown. 

We are interested in a generalization of this problem to hypergraphs. Note that a C_2k is a pair of internally disjoint paths of length k between a fixed pair of vertices. We will study hypergraphs where we forbid a certain number of paths of length k between vertices. In a hypergraph H, a Berge path of length k is a set of distinct vertices v_0,v_1,⋯, v_k and a set of distinct hyperedges h_1,h_2,⋯, h_k such that {v_i-1, v_i}∈ h_i for 1≤ i≤ k. Note that the hyperedges {h_i} could intersect in many different ways and in general two Berge paths of length k need not be isomorphic. We call the vertices v_0,⋯, v_k the core vertices of the Berge path.

The definition of Berge paths and cycles was extended to arbitrary graphs by Gerbner and Palmer <cit.>. We say a hypergraph H is a Berge-F if there is a bijection ϕ:E(F) → E(H) such that e ⊂ϕ(e) for all e∈ E(F). Again note that two hypergraphs H_1 and H_2 may each be a Berge-F and could be non-isomorphic. We denote by F^B, r the set of all r-uniform hypergraphs which are a Berge-F and we will write F^B when the uniformity is fixed. Given a family of r-uniform hypergraphs ℱ we denote the maximum number of hyperedges in an n vertex r-uniform hypergraph which does not contain any F∈ℱ as a subhypergraph by ex_r(n, ℱ). 

In this paper we are interested in studying ex_r(n, ℱ) when ℱ is a family of Berge theta graphs. A theta graph, denoted by Θ_k,t is the (2-uniform) graph given by a set of t internally disjoint paths of length k between a fixed pair of vertices. Note that Θ_k,2 = C_2k and so the study of the Turán number of Θ_k,t generalizes the even-cycle problem. We will study r-uniform hypergraphs which do not contain a Berge-Θ_k,t, i.e. we will study the Turán number for the family Θ_k,t^B. An alternative definition of a hypergraph in Θ_k,t^B is a set of distinct vertices x,y, v_1^1,⋯, v_k-1^1, ⋯, v_1^t,⋯, v_k-1^t and a set of distinct r-edges h_1^1,⋯, h_k^1,⋯ , h_1^t, ⋯, h_k^t such that {x, v_1^i}⊂ h_1^i, {v_j-1^i, v_j^i}⊂ h_j^i, and {v_k^i, y}⊂ h_k^i for 1≤ i≤ t and 2≤ j≤ k-1. That is, we are forbidding that a pair of vertices have t Berge paths of length k between them with disjoint internal core vertices. For (2-uniform) graphs, the study of ex(n, Θ_k,t) has been investigated in <cit.>. In particular, Faudree and Simonovits gave a more general version of the upper bound in the even-cycle problem. 


Given two integers k and t, there exists a constant c_k,t > 0, such that 

    (n, Θ_k,t) ≤ c_k,tn^1+1/k.



Our first main result is an extension of this bound to r-uniform hypergraphs. 


For fixed r, given two integers k and t, there exists a constant c_r,k,t, such that 

    _r(n, Θ_k,t^B) ≤ c_r,k,tn^1+1/k.



Recently, Conlon <cit.> complemented the upper bound of Faudree and Simonovits and showed that the order of magnitude is correct when t is large enough relative to k.


For any natural number k≥ 2, there exists a natural number t such that 

    (n, Θ_k,t) = Ω_k(n^1+1/k).



Our second theorem shows that this is also the case in higher uniformities.


For fixed r and any natural number k≥ 2, there exists a natural number t such that 

    _r(n, Θ_k,t^B) = Ω_k,r(n^1+1/k).



In Section <ref> we prove Theorem <ref> and in Section <ref> we prove Theorem <ref>



§ PROOF OF THEOREM <REF>


The proof of this theorem is inspired by a reduction lemma of Győri and Lemons <cit.>. To prove Theorem <ref> from Theorem <ref>, we prove the following lemma, which says that given any r-uniform Θ_k,t^B-free hypergraph, we can reduce it to a Θ_k,t-free (2-uniform) graph which has a constant proportion of the edges of the original r-uniform graph. 


Let 2≤ m< r, and H be a r-uniform hypergraph without Θ_k,t^B. Define the m-uniform hypergraph G in the following way: Order the edges of H arbitrarily and, going through the edges one by one, pick an m-set from each hyperedge to be in G where the m set chosen is the one which has been chosen the fewest number of times previously (break ties arbitrarily). Let M_k,i,r,m = ∑_j=1^k+1mk(i-1)+jm-m r-m+k+1. Then the hypergraph G will have no Θ_k,t^B,m and each of its edges will have multiplicity no more than M_k,t,r,m.



Let's first fix the notation we'll use in the rest of the proof. We will call the edges of H as hyperedges and the edges of G just as edges. We'll use h_i to denote the hyperedges, and e_i to denote edges. The edge set of H and G will be E(H) and E(G), respectively, and their (common) vertex set will be denoted as V. For every h∈ E(H), the m-set chosen from h will be denoted as e(h). 

First note that G is Θ_k,t^B,m free. Indeed, for any Berge path in G, say v_0e_1v_1e_2...e_kv_k, there is a corresponding Berge path in H v_0h_1...h_kv_k where h_i is the hyperedge such that e_i = e(h_i). Therefore, a Θ_k,t^B,m in G would imply that there is a Θ_k,t^B,r in H.

Now assume the lemma is not true and that there is an edge in G which was chosen more than M_k,t,r,m times. It suffices for us to construct a Θ_k,t^B,m in G, which will give us a Θ_k,t^B,r in H and results in a contradiction. Let e be an edge in G with some multiplicity at least M+1, and x, y∈ e. Consider the last hyperedge which contributed to the multiplicity of e, call it h. Since every time we select an m-set from a hyperedge in H, we select the one with the least multiplicity, we know that every other m-set in h must have multiplicity at least M. Since r > 2, we know there exists v_1∈ h∖{x, y}. Therefore there exists a hyperedge h_1∈ E(H) such that {x, v_1}⊆ e(h_1). On the other hand, note that v_1, y∈ h∖{x}, thus there exists h'_1∈ E(H) ∖{h_1} such that {v_1, y}⊆ e(h'_1). This gives us a length 2 path from x to y, namely x, v_1, y connected by h_1 and h'_1. Note that e(h_1) and e(h'_1) also have multiplicity at least M, and h is not part of the path. 

To extend this result, we prove the following claim, from which the construction follows easily.


Let S⊂ V be a “forbidden set", and M = ∑_j=1^k-1|S|+jm-m r-m+k+1. For i ≤ k-2, Suppose we have vertices x, v_1, v_2⋯ v_i, y and edges e_1, ⋯, e_i+1 that forms a path in G in the order given, and the last edge e_i+1∈ G with v_i, y∈ e_i+1 has multiplicity at least M - ∑_j=1^i|S|+jm-m r-m-(i-1)+1. Let S' = S ∪ e_1 ∪⋯∪ e_i+1. Then we can find v_i+1∉ S' such that x, v_1, v_2⋯ v_i, v_i+1, y forms a path, and the last edge in this new path containing v_i+1, y has multiplicity at least M - ∑_j=1^i+1|S|+jm-m r-m-i+1.
 


To find the vertex v_i+1, first we will find a new hyperedge h'∈ E(H) such that e_i+1⊂ h' and h'⊈S'. Note that the set S' has cardinality less than |S|+(i+1)m as we included all i+1 edges in the already existing path. We would like to make sure the next edge we choose for the new path is different from all previous edges. Since e_i+1 must be in h', the number of hyperedges h such that e(h) = e_i+1 and h⊂ S' is at most |S|+(i+1)m-m r-m. Now we let E' = {h∈ E(H)| e(h) = e_i+1, h⊈S'}, then we have

    |E'| ≥ |{h∈ E(H)| e(h) = e_i}| - |S|+(i+1)m-m r-m≥ M - ∑_j=1^i+1|S|+jm-m r-m-(i-1)+1.

Now we pick h' to be the last edge (in the original ordering) of E', which then implies that every m-set in h' besides e_i+1 has multiplicity at least M - ∑_j=1^i+1|S|+jm-m r-m-i+1. Since h'⊈S', we can find v_i+1∈ h' such that v_i+1∉ S'. Now we choose two m-sets from h', namely e'_i+1 and e_i+2 where v_i, v_i+1∈ e'_i+1 and v_i+1, y∈ e_i+2. This gives us a length i+2 path from x to y, namely the path x, v_1, ⋯ v_i, v_i+1, y where the last two edges are e'_i+1 and e_i+2, and the previous edges are the same as in the old length i+1 path. The last edge, e_i+2, has multiplicity at least M - ∑_j=1^i+1|S|+jm-m r-m-i+1, as desired. Note that the hyperedge h' is not part of the path, and as we discard the edge e_i+1 in the original path, we add in two new edges, namely e'_i+1 and e_i+2.


With this claim, we can now build the first path from x to y by induction on k. The base case when k=2 is already constructed before the statement of the claim. In the induction step, when we already has a length k-1 path, apply the claim with S = ∅ and we obtain a length k path, as desired. Note that if all we need is just one path, then we just need the multiplicity of the edge e to be at least M_k,1,r,m. 

To build t paths, we will construct each path separately. Assume that we have built i-1 paths. To build the ith path, the forbidden set S would be the union of all edges in previous paths. This ensures that the paths we are building are vertex-independent and edge-distinct. It then follows that to build t vertex-independent paths from x to y, it suffices for us to have that the multiplicity of the edge e to be at least M_k,t,r,m. This gives us a Θ_k,t^B,m in the graph G. If we then choose hyperedges in H that gives the edges in this Θ_k,t^B,m, we obtain a Θ_k,t^B,r in H. Such hyperedges can be chosen because all edges in this Θ_k,t^B,m in G have multiplicity at least 1, and these hyperedges are guaranteed to be distinct since for any two hyperedges chosen, say h_1 and h_2, e(h_1) e(h_2), and therefore h_1 h_2. This leads to a contradiction. Therefore all edges in G must have multiplicity at most M_k,t,r,m.


By Theorem <ref>, there exists a constant c_k,t such that (n, Θ_k,t) ≤ c_k,tn^1+1/k. Now assume that a r-uniform hypergraph has more than M_k,t,r,2c_k,tn^1+1/k edges. Then if we reduce this hypergraph into a (2-uniform) graph with the scheme described above, we will either have a graph with more than c_k,tn^1+1/k edges, or it will have at least one edge with more than M_k,t,r,2 multiplicity. Both cases imply that there is a Θ_k,t in the reduced graph, which leads to a Θ_k,t^B in the original hypergraph. This completes the proof of Theorem <ref>.




§ PRELIMINARIES FOR THEOREM <REF>


To prove Theorem <ref>, given any natural number k≤ 2, we need to construct a Θ_k,t^B-free r-uniform hypergraph with Ω(n^1+1/k) edges where t is a large enough constant depending only on k and r. Blagojević, Bukh and Karasev <cit.> found an elegant random algebraic construction for Turán type problems, and we will use this method to construct our hypergraphs. This method has recently been used with success in both the graph <cit.> and hypergraph setting <cit.>.

Let k and r be fixed, and for q a prime power let 𝔽_q be the finite field of order q. We will work with polynomials in kr variables over 𝔽_q. Let P_d be the set of such polynomials of degree at most d. That is, P_d consists of linear combinations of monomials ∏_i=1^kr x_i^α_i where ∑ a_i ≤ d. For the remainder of the paper we will use the term random polynomial to denote a polynomial chosen uniformly at random from P_d. Note that the distribution of random polynomials is equivalent to choosing the coefficient of each monomial ∏_i=1^kr x_i^α_i independently and uniformly from 𝔽_q. 



We will need to know the probability that a random polynomial vanishes on a fixed set of points. In particular, if we fix one point, since the constant term of a random polynomial is chosen uniformly from 𝔽_q, we have the following lemma.


If f is a random polynomial from P_d, then, for any fixed x∈ F_q^t,

    ℙ[f(x) = 0] = 1/q.



The next lemma, proved as Lemma 2.3 in <cit.> and Lemma 2 in <cit.>  extends the conclusion of Lemma <ref>.


Assume x_1, ⋯, x_z are z distinct points in 𝔽_q^t. Suppose q > z 2 and d≥ z - 1. Then if f is a random polynomial from P_d,

    ℙ[f(x_i) = 0 for all  i = 1, ⋯, z] = 1/q^z.
 


We now define the graphs that we will be interested in. Let N = q^k. We will construct an r-partite r-uniform hypergraph on rN vertices as follows. Let V_1,…, V_r be the partite sets, each a distinct copy of 𝔽_q^k. Choose f_1, f_2, ⋯ f_k(r-1)-1:𝔽_q^kr→𝔽_q to be independent random polynomials of degree d := k(2k+1). For v_1,…, v_r with v_i∈ V_i, we declare {v_1,⋯, v_r} to be an edge if and only if

    f_1(v_1, v_2, ⋯ ,v_r) = f_2(v_1, v_2, ⋯ ,v_r) = ⋯ = f_k(r-1)-1(v_1,v_2,⋯ ,v_r) = 0


We use the term random polynomial graph to describe the distribution of hypergraphs obtained this way. Since these polynomials are chosen independently, we know from Lemma <ref> that the probability of a given hyperedge is in a random polynomial graph is q^1-k(r-1). The total number of possible hyperedges is N^r = q^kr. Therefore the expected number of hyperedges is q^krq^1-k(r-1) = q^k+1 = N^1+1/k. 

We will be interested in subgraphs that appear in a random polynomial graph. Since hyperedges appear when a system of polynomials vanishes, we will describe subgraphs as varieties. Let 𝔽_q be the algebraic closure of 𝔽_q. A variety over 𝔽_q is a set of the form:

    W = {x∈𝔽_q^t: f_1(x) = f_2(x) = ⋯ = f_s(x) = 0}

For a collection of polynomials f_1, ⋯, f_s:𝔽_q^t→𝔽_q. In other words, a variety is the set of common roots of a set of polynomials. We say W is defined over 𝔽_q if the coefficients of these polynomials are from 𝔽_q and write W(𝔽_q) = W∩𝔽_q^t. We say W has complexity at most M if s, t and the maximum degree of the polynomials are all bounded by M. We will be very interested in how many points can be on a variety, and we will use the following theorem, proved by Bukh and Conlon (<cit.> Lemma 2.7) using tools from algebraic geometry.


Suppose W and D are varieties over 𝔽_q of complexity at most M which are defined over 𝔽_q. Then one of the following holds:

    
  * |W(𝔽_q) ∖ D(𝔽_q)| ≤ c_M, where c_M depends only on M, or
    
  * |W(𝔽_q) ∖ D(𝔽_q)| ≥ q/2.
    



Using these tools, we will show in the following section that we may modify a random polynomial graph to obtain a Θ_k,t^B free hypergraph with Ω(n^1+1/k) edges with high probability.








































§ PROOF OF THEOREM 4

In this section we show that there exists an n vertex Θ_k,t^B free hypergraph with Ω(n^1+1/k) hyperedges. Our proof is an adaption of <cit.> to the hypergraph setting. Let q be a sufficiently large prime power and let G be a random polynomial graph on n = rN = rq^k vertices defined in the previous section. As noted before the expected number of hyperedges in G is 


    N^1+1/k = Ω(n^1+1/k).


We are interested in Θ_k,t^B as a subgraph of G, and so we will be interested in Berge paths between vertices. Suppose now that x and y are two fixed vertices in G and let S be the set of Berge-paths with length k between them. We will be interested in the moments of the random variable |S|. Let m be fixed and note that |S|^m is the number of collections of m Berge paths of length k between x and y. These paths can be overlapping or identical, and the total number of hyperedges in any collection of m paths is at most km. Since q is sufficiently large, Lemma <ref> implies that for z≤ d the probability of any particular collection with z hyperedges is in G is q^z(1-k(r-1)), since the probability that any hyperedge is in G is q^1-k(r-1). Now if we denote P_m,z as the number of collections of m paths between x and y such that their intersection has z hyperedges in total, we have:

    𝔼[|S|^m] = ∑_z = 1^kmP_m,zq^z-zk(r-1),

as long as km ≤ d. Now we shall estimate P_m,z by estimating the maximum number of vertices there can be in any particular collection with z hyperedges. Namely, if a collection has hyperedges h_1, ⋯ h_z, then we want to estimate max|∪_i∈ [z]h_i|. 


If the union of m Berge-paths from x to y, each of length k, has z edges in their intersection {h_i}_i=1^z, then 

    | ⋃_i=1^z h_i ∖{x,y}| ≤zk(r-1)-z/k.




Given such a collection, assume |∪ h_i ∖{x,y}| = n_0. Let P_1,…, P_m be the set of paths, and let n_i and z_i be the number of vertices and edges respectively in P_i ∖(P_1 ∪⋯∪ P_i-1). Let z_i' = z_i if n_i >0 and z_i' = 0 if n_i=0.

If n_i > 0, then because consecutive edges in a Berge path must overlap, we have that z_i ≥⌊n_i/r-1+1⌋. Since n_i is an integer, this implies that z_i ≥n_i/r-1 - r-2/r-1 + 1 = n_i+1/r-1. Let r' be the number of n_i which are greater than 0. Let 

    z' = ∑_i=1^m z_i' ≤ r'k,

and so r' ≥z'/k. On the other hand,

    z' ≥∑_i: n_i>0n_i + 1/r-1 = n_0 + r'/r-1≥n_0/r-1 + z'/k(r-1).


This implies 

    n_0 ≤z'k(r-1)-z'/k.

Since z'≤ z the result follows.




We can now bound P_m,z.

P_m,z =  O_k,r(q^zk(r-1)-z)


We want to count the number of all possible collections of m Berge-paths between x and y with z edges in their intersection. Let V = zk(r-1)-z/k be the upper bound on the number of vertices, then we first choose the vertices that will be in the collection. There are less than (rN)^V number of ways to do this. Then we choose z hyperedges, each having r vertices. The number such choices is bounded by V r^z. Last we choose 2 vertices from each hyperedge to make up the core vertices. This is bounded by r 2^z, which eventually gives us 

    r^VV r^zr 2^zN^V =  O_k,r(N^V) = O_k,r(q^zk(r-1)-z)

Note that every collection of m paths is counted by this method in at least one way, giving the upper bound on P_m,z.


Thus, when m≤ 2k+1 we have z≤ km ≤ d (since d = k(2k+1)) and we may apply Lemma <ref> to find  

    𝔼[|S|^m] = ∑_z = 1^kmP_m,zq^z-zk(r-1)≤ kmC_k,r := C.

Where C_k,r is a constant dependent on k and r, and C is used to simplify our notation. 






Now if we want to apply tools from algebraic geometry, we need to write S as a variety. However, this cannot be done directly since there is no fixed set of polynomials whose set of common roots is exactly S. Therefore, we use the following analysis to bound |S|. Any path in S is a sequence of core vertices and edges (x, h_1, v_1, h_2, ⋯, v_k-1, h_k, y). We may partition the set of paths into which partite set each v_i is in. That is, S can be partitioned into disjoint sets depending on which partite sets each core vertex belongs to. Namely, we can let S_t_1, ⋯ t_k-1 denote the set of paths from x to y such that the ith core vertex v_i belongs to V_t_i. 

Now if we let σ denote any length k-1 tuple from [r]^k-1, then we have

    S = ⋃_σ∈ [r]^k-1S_σ,

and this is a disjoint union.

Fix any arbitrary S_σ. For notation, we denote the core vertices in an arbitrary path as v_1, ⋯, v_k-1 and the non core vertices in hyperedge h_i as w_1^i, ⋯, w_r-2^i. We also need to make sure that the non core vertices are ordered based on their partite sets. In other words, if w_j^i∈ V_t_1 and w_k^i∈ V_t_2 where j < k, then t_1 < t_2.

Now we may define the variety T_σ as


    {f_i,1(p) = ⋯ = f_i,k(p) = 0},
    


where p∈𝔽_q^k(r-2)+k-1 runs over sequences (v_1,⋯, v_k-1, w_1^1,⋯, w_r-2^1, ⋯, w_1^k,⋯, w_r-2^k (that is, each p is a vector ordered with the core vertices first and the non core vertices after).

Here the polynomials f_i,1,⋯, f_i,k are extensions to the polynomial f_i. Namely, 

    f_i,1(p) = f_i(x, v_1, w_1^1, ⋯, w_r-2^1)


    f_i,2(p) = f_i(v_1, v_2, w_1^2, ⋯, w_r-2^2)


    ⋯


    f_i,k(p) = f_i(v_k-1, y, w_1^k, ⋯, w_r-2^k)

Note that depending on σ (the ordering of partite sets on core vertices), the arguments given to f_i need to be reordered. However, since σ is fixed and so is the ordering of all non core vertices, we can fix the order of arguments given to f_i according to σ. For instance, if x∈ V_2, v_1∈ V_3, then 


    f_i, 1(p) = f_i(w_1^1, x, v_1, w_2^1, ⋯, w_r-2^1)


With this restriction on ordering, we see that S_σ⊆ T_σ(𝔽_q). Note that T_σ contains all of the paths in S_σ, but may also contain walks that are not paths.

If T_σ(𝔽_q) contains a degenerate walk x, v_1, v_2, ⋯, v_k-1, y, then one of the following three conditions must be true: x = v_b for some b∈ [k-1], v_a = y for some a∈ [k-1], or v_a = v_b for some a b∈ [k-1]. Therefore we can consider the collections of sets:


    W_0,b   = T_σ∩{v_1, ⋯, w_r-2^k: x = v_b}
    
    W_a,b   = T_σ∩{v_1, ⋯, w_r-2^k: v_a = v_b}
    
    W_a,0   = T_σ∩{v_1, ⋯, w_r-2^k: v_a = y}



Each of these sets is also a variety with complexity bounded in terms of k and r. Let W be the union of all of the W_0,b, W_a,b, and W_a,0. If X and Y are varieties with complexity bounded in terms of k and r, then we claim that X∪ Y is also a variety with complexity bounded in terms of k and r. To see this, if X is the set of points where the set of polynomials {f_i} vanish and Y is the set of points where the polynomials {g_j} vanish, then X∪ Y is exactly the set of points where the polynomials {f_ig_j} vanish. Since W is the union of O(k^2) varieties, we have that W is also a variety with complexity bounded in terms of k and r. Since S_σ = T_σ∖ W, we may apply Theorem <ref> to S_σ.









Now if we put everything together, we see that there exists a constant c_σ, dependent on k and r, such that either |S_σ|≤ c_σ or |S_σ|≥q/2. This conclusion holds true for any arbitrary σ∈ [r]^k-1. Looking at S, we see that either |S| = ∑_σ∈ [r]^k=1|S_σ|≤ C_k,r for some constant C_k,r dependent on k and r, or |S| > C_k,r, which implies that there exists σ such that |S_σ| > c_σ and therefore |S|≥ |S_σ| > q/2. Now by (<ref>) and Markov's inequality, for m≤ 2k+1 we have

    ℙ[|S| > C_k,r] = ℙ[|S| > q/2] =ℙ[|S|^m > (q/2)^m] ≤C/(q/2)^m.

Call a pair of vertices (x,y) bad if it has more than C_k,r length k paths between them. If B is the random variable denoting the number of bad pairs, then we have

    𝔼(B) ≤ N^2×C/(q/2)^m = O_k,r(q^2k-m) = O_k,r(1/q),

when we take m=2k+1. Therefore by Markov's Inequality, ℙ[B ≥ 1] → 0 as n→∞. Now let X be the number of edges, then by (<ref>) the expected number of edges in is N^1+1/k. The variance is 

    𝔼[X^2] - 𝔼[X]^2 = ∑_i,j𝔼[H_iH_j]-𝔼[H_i]𝔼[H_j] = N^r(q^1-k(r-1) - q^2-2k(r-1))≤𝔼[X]

Where H_i are indicator random variables for hyperedges and for i j, 𝔼[H_iH_j] = 𝔼[H_i]𝔼[H_j] because H_i and H_j are independent due to Lemma <ref>. By Chebyshev's Inequality, 

    ℙ[|X - N^1+1/k|≥1/2N^1+1/k] ≤1/4N^1+1/k

which goes to zero. Therefore with high probability this hypergraph on rN vertices has Ω_k,r(N^1+1/k) edges, and it contains no Θ_k,C_k,r+1^B. This completes the proof of Theorem <ref>.



§ CONCLUSION

In this paper we showed that for fixed k,r,t there is a constant c_k,r,t such that 

    _r(n, Θ_k,t^B) ≤ c_r,k,tn^1+1/k,

and that this order of magnitude is correct when t is large enough relative to r and k. That is, for fixed k and r there is a constant c_k,r such that

    _r(n, Θ_k,c_k,r^B) = Ω_k,r(n^1+1/k).


We end with some open questions. First, it would be interesting to determine the dependence on r. Even when t=2 and k∈{2,3,5} this dependence is unknown. For example, it is known that ex_r(n, C_4^B) = Θ(n^3/2) when 2≤ r≤ 6, but the order of magnitude is unknown for r≥ 7 (c.f. <cit.>). It would also be interesting to determine the dependence on t when t is large. Finally, in this paper we worked with the least restrictive definition of paths between vertices in hypergraphs. One could forbid only certain types of paths and demand that no pair of vertices have more than t of these paths between them. 
plain


