{'fraction_non_alphanumeric': 0.0606483174835406, 'fraction_numerical': 0.019979882955376737, 'mean_word_length': 3.2413224743067675, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 38, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Effect of Induced Subgraphs on Quasi-Randomness

One of the main questions that arise when studying random and quasi-random structures is which properties P are such that any object that satisfies P"behaves"like a truly random one. In the context of graphs, Chung, Graham, and Wilson call a graph p-quasi-random} if it satisfies a long list of the properties that hold in G(n,p) with high probability, like edge distribution, spectral gap, cut size, and more. Our main result here is that the following holds for any fixed graph H: if the distribution of induced copies of H in a graph G is close (in a well defined way) to the distribution we would expect to have in G(n,p), then G is either p-quasi-random or p'-quasi-random, where p' is the unique non-trivial solution of a certain polynomial equation. We thus infer that having the correct distribution of induced copies of any single graph H is enough to guarantee that a graph has the properties of a random one. The proof techniques we develop here, which combine probabilistic, algebraic and combinatorial tools, may be of independent interest to the study of quasi-random structures.


Background and basic definitions
Quasi-random structures are those that possess the properties we expect random objects to have with high probability. The study of quasi-random structures is one of the most interesting borderlines between discrete mathematics and theoretical computer science, as they relate the problem of how to deterministically construct a random-like object with the question of when we can consider a single event to be a random one. Although quasi-random structures have been implicitly studied for many decades, they were first explicitly studied in the context of graphs by Thomason [28,29] and then followed by Chung, Graham, and Wilson [8]. Following the results on quasi-random graphs, quasi-random properties were also studied in various other contexts such as set systems [4], tournaments [5], and hypergraphs [6]. There are also some very recent results on quasi-random groups the distribution of induced copies of a single graph H is not enough to guarantee that a graph is quasi-random. Therefore, the notion of closeness that we use here is essentially optimal if one wants to be able to deal with any H.
Before stating our main result we first discuss some previous ones, which will put ours in the right context. The cornerstone result on properties guaranteeing that a graph is quasi-random is that of Chung, Graham, and Wilson [8], stated below, but before stating it we need to introduce some notation. We will denote by e(G) the number of edges of a graph G. A labeled copy of a graph H in a graph G is an injective mapping φ, from the vertices of H to the vertices of G, that maps edges to edges, that is (i, j) ∈ E(H) ⇒ (φ(i), φ(j)) ∈ E(G). So the expected number of labeled copies of a graph H in G(n, p), is p e(H) n h + o(n h ) where h is the number of vertices of H 1 . A labeled induced copy of a graph H in a graph G is an injective mapping φ, from the vertices of H to the vertices of G, that maps edges to edges, and non-edges to non-edges, that is (i, j) ∈ E(H) ⇔ (φ(i), φ(j)) ∈ E(G). So the expected number of induced labeled copies of a graph H in G(n, p), is δ H (p)n h + o(n h ), where here and throughout the paper we will use δ H (p) to denote p e(H) (1 − p) ( h 2 )−e(H) . For a set of vertices U ⊆ V we denote by H[U ] the number of labeled copies of H in U , and by H * [U ] the number of induced labeled copies of H in U . We also use e(U ) to denote the number of edges inside a set of vertices U , and e(U, V ) to denote the number of edges connecting U to V . The following is (part of) the main result of [8]: Theorem 1 (Chung, Graham, and Wilson [8]) Fix any 0 < p < 1. For any n-vertex graph G the following properties are equivalent:   For the rest of the paper let us use the notation x = y ± ǫ as a shorthand for the two inequalities y − ǫ ≤ x ≤ y + ǫ. As we have mentioned before, we use the o(1) term to denote an arbitrary function tending to 0 with n. Hence, the meaning of the fact that, for example, P 2 implies P 1 is that for any f (n) = o(1) there is a g(n) = o (1) such that if G has the property that all U ⊆ V (G) of size n/2 satisfy e(U ) = 1 2 p|U | 2 ± g(n)n 2 , then e(U ) = 1 2 p|U | 2 ± f (n)n 2 for all U ⊆ V (G). Equivalently, this means for any δ > 0 there is an ǫ = ǫ(δ) and n 0 = n 0 (δ) such that if G is a graph on n ≥ n 0 vertices and it has the property that all U ⊆ V (G) of size n/2 satisfy e(U ) = 1 2 p|U | 2 ± ǫn 2 , then e(U ) = 1 2 p|U | 2 ± δn 2 for all U ⊆ V (G). This will also be the meaning of other implications between other graph properties later on in the paper.
Note, that each of the items in Theorem 1 is a property we would expect G(n, p) to satisfy with high probability. We will thus say that G is p-quasi-random if it satisfies property P 1 , that is if for some small δ all U ⊆ V (G) satisfy e(U ) = 1 2 p|U | 2 ± δn 2 . If one wishes to be more precise then one can in fact say that such a graph is (p, δ)-quasi-random. We will sometimes omit the p and just say that a graph is quasi-random. In the rest of the paper the meaning of a statement "If G satisfies P 2 then G is quasi-random" is that P 2 implies P 1 in the sense of Theorem 1 discussed in the previous paragraph. We will also say that a graph property P is quasi-random if any graph that satisfies P must be quasi-random. So the meaning of the statement "P 2 is quasi-random" is that P 2 implies P 1 . Therefore, all the properties in Theorem 1 are quasi-random.
Given Theorem 1 one may think that any property that holds with high probability in G(n, p) is quasi-random. That however, is far from true. For example, it is easy to see that having the "correct" vertex degrees is not a quasi-random property (consider K n/2,n/2 ). Note also that in P 5 we require α < 1 2 , because when α = 1 2 the property is not quasi-random (see [7] and [23]). A more relevant family of non quasi-random properties are those requiring the graph to have the "correct" number of copies of a fixed graph H. Note that P 4 (t) guarantees that for any even t, if a graph has the "correct" number of edges and the "correct" number of copies of C t then it is quasi-random. As observed in [8] this is not true for all graphs, in fact this is not true for any non-bipartite H.

Quasi-randomness and the distribution of copies of a single graph
As throughout the paper we work with labeled copies and labeled induced copies of H, we henceforth just call them copies and induced copies. To understand the context of our main result, which deals with induced copies of a fixed graph H, it is instructive to review what is known about the effect of the distribution of a fixed graph H on quasi-randomness. By Theorem 1 we know that for some graphs H the property of having the "correct" number of copies of H in G, along with the right number of edges, is enough to guarantee that G is quasi-random. Furthermore, this is not true for all graphs H. However, the intuition is that something along these lines should be true for any H, i.e. that for any H, if the copies of H in a graph G have the "properties" we would expect them to have in G(n, p), then G should be p-quasi-random. Simonovits and Sós [23] observed that the counter examples showing that, for some graphs H, having just the "correct" number of copies of H (and the "correct" number of edges) is not enough to guarantee quasi-randomness, all have the property that some of the induced subgraphs of these counter examples have significantly more/less copies of H than we would expect to find in G(n, p). For example, in order to show that having the "correct" number of edges and triangles as in G(n, 1/2) does not guarantee that G is 1 2 -quasi-random, one can take a complete graph on αn vertices and a complete bipartite graph on (1 − α)n vertices, for an appropriate α.
The main insight of Simonovits and Sós [23] was that quasi-randomness is a hereditary property, in the sense that we expect a sub-structure of a random-like object to be random-like as well. Thus, perhaps it will suffice to require that the subgraphs of G should also have the "correct" number of copies of H. To state the main result of [23] let us introduce the following variant of property P 1 of Theorem 1.
Note that the above restriction is that the value of H[U 1 , . . . , U h ] should be close to what it should be in G(n, p) for all h-tuples of equal-size. Observe also that the above condition does not impose any restriction on the number of edges of G, while in property P 1 there is. Note also, that the error in the above definition involves n rather than m = |U 1 | = · · · = |U h | so when m = o(n) the condition vacuously holds. As opposed to P 4 , which is not quasi-random for all graphs, Simonovits and Sós [23] showed that P H is quasi-random for any graph H.
Theorem 2 (Simonovits and Sós [23]) The following holds for any graph H: if a graph G satisfies P H then it is p-quasi-random.
Observe that P H requires, via Definition 1.1, all h-tuples of vertex sets to have the "correct" number of copies of H with one vertex in each set. A more "natural" requirement, that was actually used in [23], is that all subsets of vertices U ⊆ V (G) should contain the "correct" number of copies of H, that is, that H[U ] ≈ p e(H) |U | h for all U ⊆ V (G). However, it is not difficult to show that these two conditions are in fact equivalent (see [21]). We choose to work with Definition 1.1 as it will fit better with the discussion in the next subsection.

The main result
So we know from Theorem 1 that when we consider the number of subgraphs of H in G, then some H but not all, are such that having the "correct" number of copies of H in a graph G (and number of edges) is enough to guarantee that G is quasi-random. From Theorem 2 we know that for all H, having the "correct" number of copies of H in all the subgraphs of G is enough to guarantee that G is quasi-random. A natural question is what can we learn from the distribution of induced copies of a graph H? As we shall see, the situation is much more involved.
Recall that for a fixed graph H on h vertices and a fixed 0 < p < 1, we define δ H (p) = p e(H) (1 − p) ( h 2 )−e(H) . Let us denote by p H the second 2 solution (other than p) of the equation . We call p H the conjugate of p with respect to H. We will sometimes just write p instead of p H when H is fixed. Note that the expected number of induced copies of H in a set of vertices U is roughly δ H (p)|U | h . But, as it may 3 be the case that p = p H we see that for any H and any p, the distribution of induced copies of H in both G(n, p) and G(n, p H ) behaves precisely the same. Therefore, the best we can hope to deduce from the fact that the distribution of induced copies of H in G is close to that of G(n, p) is that G is either p-quasi-random or p H -quasi-random.
So given the above discussion and Theorem 2, it seems reasonable to conjecture that, if a graph G has the "correct" distribution of induced copies of H, then G is either p-quasi-random or p Hquasi-random. When we say "correct" distribution we mean that all pairwise disjoint h-tuples U 1 , . . . , U h ⊆ V (G) of the same size m satisfy H * [U 1 , . . . , U h ] = δ H (p)h!m h ± o(m h ). However, it was observed in [23,24] that this is not the case. For example, one can take vertex set V 1 , V 2 of sizes αn, (1 − α)n and put G(αn, p 1 ) on V 1 , G((1 − α 1 )n, p 1 ) on V 2 and connect V 1 and V 2 with probability p 2 = p 1 . Then for appropriate constants, we get a graph with the "correct" distribution of the 3-vertex path, yet this graph is not p-quasi-random for any p.
However, as before, the intuition is that having the "correct" distribution of induced copies of H should guarantee that G is quasi-random. Our main result in this paper is that indeed it does, one just needs to refine the notion of "correct distribution". As we have mentioned before, if U 1 , . . . , U h is an h-tuple of vertices in G(n, p) of the same size m, then we would expect to have However, this is because we would actually expect a slightly stronger condition to hold. Before stating this condition, let us introduce the following "permuted" version of the quantity H * [U 1 , . . . , U h ].
Getting back to our discussion, observe that the reason we expect to have It is now natural to define the following property: Our main result is that property P * H guarantees that a graph is quasi-random.

Theorem 3 (Main result)
The following holds for any graph H: if a graph satisfies P * H then it is either p-quasi-random or p H -quasi-random.
Our main result can be formulated as saying that for any H, if a graph G has the "correct" distribution of induced copies of H, then G is quasi-random. We remind the reader that one cannot hope to strengthen Theorem 3 by showing that G must be p-quasi-random, as G(n, p) satisfies P * H with probability 1. Observe, that our notion of "correct distribution" (that is, the quantities H * σ ) is stronger than the notions that have been considered before (that is, the quantities H * ), where the latter is known to be too weak to guarantee quasi-randomness for arbitrary graphs H. Let us mention here that Simonovits and Sós conjectured in [23] that the weaker quantities H * should be sufficient for guaranteeing quasi-randomness for any H on at least 4 vertices. This conjecture, however, is still wide open.

Overview of the paper
As we have discussed in the first subsection, the theory of quasi-random graphs has many applications in theoretical computer science, both in the case of sparse and dense graphs. We think that the main interest of our result is in the proof techniques and tools that are used in the course of its proof. Besides several combinatorial arguments and tools (such as the Regularity Lemma [26], Ramsey's Theorem and Rödl's "nibble" Theorem [19]) the main underlying idea of the proof is an algebraic one. Roughly speaking, what we do is take all the information we know about the graph G, namely the information on the distribution of induced copies of H, and use it in order define a large system of polynomial equations. The unknowns in this system of equations represent (in some way) the distribution of edges of G. The crux of the proof is to show that the unique solution of this system of equations, is one that forces the edges of the graph to be nicely distributed (in the sense of property P 1 in Theorem 1). The main theorem we need in order to obtain this uniqueness is a result of Gottlieb [10], in algebraic combinatorics, concerning the rank of set inclusion matrices (see Theorem 4). This approach to showing that a graph is quasi-random may be applicable for showing quasi-random properties of other structures.
In Section 2 we prove Theorem 3 by applying several combinatorial tools as well as a key lemma (Lemma 2.1) that is proved in Section 3. The proof of Lemma 2.1, which is the most difficult step in the proof of Theorem 3, contains most of the new ideas we introduce in this paper.

Proof of Main Result
In this section we give the proof of Theorem 3, but before getting to the actual proof we will need some preparation. We first discuss Lemma 2.1, which is the main technical lemma we need for the proof of Theorem 3, and whose proof appears in the next section. We then discuss some simple notions related to the Regularity Lemma, and then turn to the proof of Theorem 3. Throughout this section, let us fix a real 0 < p < 1 and a graph H on h vertices. Recall that we set δ H (p) = p e(H) (1 − p) ( h 2 )−e(H) and that we denote by p, the conjugate of p, the second solution in (0, 1) of

The Key Lemma
In what follows we will work with weighted complete graphs W on r vertices. We will think of the vertices of W as the integers [r]. In that case each pair of vertices 1 ≤ i < j ≤ r will have a weight 0 ≤ w(i, j) ≤ (1 − w(φ(i), φ(j))) .
Another notation that will simplify the presentation is a variant of the H * σ [U 1 , . . . , U h ] notation that was defined in Section 1. Suppose we have r pairwise disjoint vertex sets U 1 , . . . , U r and an injective mapping φ : Suppose we construct an r-partite graph on vertex sets U 1 , . . . , U r , each of size m, by connecting every vertex in U i with any vertex in U j independently with probability w(i, j). Then, observe that for any φ : Observe however, that we would also expect the same to hold if we were to replace p by p.
The following lemma shows that the converse is also true in the following sense: if we know that for any injective mapping φ we have the "correct" fraction of induced copies of H as we would expect to find if we had w(i, j) = p for all (i, j), then either 4 almost all (i, j) satisfy w(i, j) = p or almost all satisfy w(i, j) = p. Note that for convenience the lemma is stated with respect to quantities in (0, 1), rather than with respect to the number of edges or number of copies 5 . In what follows, we will always assume wlog that if p = p then ǫ < |p − p|/2. This will guarantee that the intervals p ± ǫ and p ± ǫ are disjoint.
The proof of Lemma 2.1, which is the main lemma we need for the proof of Theorem 3, appears in Section 3. It is interesting to note that, as we show in Section 3, one cannot strengthen the above lemma by showing that either all densities are close to p or they are all close to p.

The Regularity Lemma
We now give a brief overview of the Regularity Lemma of Szemerédi, which turns out to be strongly related to quasi-random graphs. The following lemma of Simonovits and Sós [22] shows that the property of having a regular partition where most of the pairs are connected by regular pairs of density close to p implies that the 4 Remember that we cannot expect to be able to show that all densities are p as the number of induced copies of H behaves the same with respect to p and p. 5 So w(i, j) should be understood as the density between the pair (Ui, Uj ) and graph is p-quasi-random. For completeness we include a short self-contained proof of this lemma at the end of this section. We remind the reader that we use the notation x = y ± ǫ to denote the fact that y − ǫ ≤ x ≤ y + ǫ. [22]) For every ζ > 0 there is an ǫ = ǫ 2.3 (ζ) and t = t 2.3 (ζ) with the following property: suppose an n vertex graph G has an ǫ-regular partition of order k ≥ t where all but ǫ k 2 of the pairs are ǫ-regular with density p ± ǫ. Then every set of vertices U ⊆ G spans 1 2 p|U | 2 ± ζn 2 edges.

Lemma 2.3 (Simonovits and Sós
Another tool we will need for the proof of Theorem 3 is Lemma 2.4 below. This lemma is equivalent to saying that if we have r pairwise disjoint vertex sets V 1 , . . . , V r that are all regular enough, then for any injective mapping φ : is close to what it should be. Such a lemma is well known, and has been proven and used in many papers. See, e.g., Lemma 4.2 in [9] for one such proof. We thus omit the proof of Lemma 2.4.

Proof of Theorem 3
For the proof of Theorem 3 we will also need the following two lemmas, whose proofs are deferred to the end of this section.
Lemma 2.5 For every ǫ there is an r 2.5 = r 2.5 (ǫ) such that for every r ≥ r 2.5 there is N 2.5 = N 2.5 (r) and γ 2.5 = γ 2.5 (r) with the following property. Assume k ≥ N 2.5 and that K is a k vertex graph with at least (1 − γ 2.5 ) k 2 edges. Suppose the edges of K are colored red/blue so that at least ǫ k 2 are blue and at least ǫ k 2 are red. Then K has r vertices that span a complete graph K r with at least r blue edges and at least r red edges. Lemma 2.6 For any γ and r, there is an N 2.6 = N 2.6 (γ, r) such that the following holds for any k ≥ N 2.6 . If K is a graph on k vertices with at least (1 − γ) k 2 edges, then K has at least (1 − γr 2 ) k 2 edges that belong to a copy of K r .
Proof of Theorem 3: We will say that a γ-regular equipartition of order k is γ-super-regular 6 if all but γ k 2 of the pairs are γ-regular with density p ± γ or all but γ k 2 of the pairs are γ-regular with density p ± γ. We need to show that any graph G that satisfies P * H must be either p-quasirandom or p-quasi-random 7 . Fix any ζ > 0 and recall that by Lemma 2.3 we know that in order to show that a graph G has the property that every set U ⊆ V (G) satisfies e(U ) = 1 2 p|U 2 | ± ζn 2 or that every such set satisfies e(U ) = 1 2 p|U 2 |± ζn 2 , it is enough to show that G has an ǫ-super-regular partition of order at least t, where and Let us define the following constants 8 To complete the proof that P * H implies that a graph is either p-quasi-random or p-quasi-random, we show (via Lemma 2.3) that for any ζ > 0 there is an N (ζ) and δ(ζ) such that the following holds: if G is a graph on at least N (ζ) vertices and for every h-tuple of vertex sets U 1 , . . . , U h ⊆ V (G) of (arbitrary) size m each, and for every permutation σ : then G has an ǫ-super-regular partition of order k, where k ≥ t. We will show that one can take N (ζ) to be the integer N defined in (6) and that δ(ζ) can be taken as the value defined in (8).
So let G be a graph of size at least N , and apply Lemma 2.2 (the regularity lemma) on G with γ/r 2 and N that were defined in (5) and (6). Lemma 2.2 guarantees that G has a γ-regular partition V = {V 1 , . . . , V k } where t ≤ N ≤ k ≤ T and T is given in (7). We now need to show that all but ǫ k 2 of the pairs (V i , V j ) are ǫ-regular and satisfy d(V i , V j ) = p ± ǫ or ǫ-regular and satisfy is not ǫ-regular then (i, j) are not connected. So our goal is to show that either all but ǫ k 2 of the pairs of vertices of W are connected by an edge with weight p ± ǫ or that all but ǫ k 2 of the pairs of vertices of W are connected by an edge with weight p ± ǫ. 7 Recall that the meaning of that is that either every set U ⊆ V (G) satisfies e(U ) = 1 2 p|U 2 | ± ζn 2 or that every such set satisfies e(U ) = 1 2 p|U 2 | ± ζn 2 for some small ζ > 0 8 We note that we need N , which is defined in (6), in order to allow us to apply the various lemmas we stated above, that all work for large enough graphs. Claim 2.7 Any copy of K r in W satisfies the following: 1. Any edge has either weight p ± ǫ or weight p ± ǫ.
2. If p = p then either at most r − 1 of them have weight p ± ǫ or at most r − 1 of them have weight p ± ǫ.
Proof: Consider any copy of K r in W and suppose wlog that the vertices of this copy are 1, . . . , r.
Recall that k ≤ T and that G satisfies (9) with the δ that was chosen in (8). We thus infer that for any injective mapping φ : In addition, as we are referring to r vertices that form a copy of K r in W , we know that V 1 , . . . , V r are all pairwise γ-regular. Thus the choice of γ in (5) Combining (10) and (11) we infer that for any φ : Hence, the two assertions of the claim follow from Lemma 2.1.
We are now going to use Lemma 2.1 in order to color some of the edges of W . Consider any copy of K r in W . We know from the first assertion of Claim 2.7 that all the edge weights in the copy of K r are either p ± ǫ or p ± ǫ. If p = p then we color all the edges of this K r with the color red. So assume that p = p and recall that we assume wlog that in this case ǫ < |p − p|/2, which makes it possible to color the edges whose weight is p ± ǫ blue, and the edges whose weight is p ± ǫ red (in a well defined way). We now apply this coloring scheme to any copy of K r in W . We claim that we have thus colored at least (1 − γ) k 2 of the edges of W . Indeed, as we applied the regularity lemma with γ/r 2 we know that W has at least (1 − γ/r 2 ) k 2 edges. As k ≥ N 2.6 (γ, r) we infer from Lemma 2.6 that at least (1 − γ) k 2 of the edges of W belong to a copy of K r thus they are colored in the above process. Let us now remove from W all the uncolored edges and call the new graph W ′ . Thus W ′ has at least (1 − γ) k 2 edges and they are all colored either red or blue. We now claim that either W ′ has at most ǫ 2 k 2 red edges, or at most ǫ 2 k 2 blue edges. Indeed, if W ′ had at least ǫ k 2 red edges and at least ǫ k 2 blue edges, then our choice of r and γ in (4) and (5), the fact that W ′ has at least (1 − γ) k 2 edges, and that k ≥ N 2.5 (r), would allow us to apply Lemma 2.5 on W ′ and infer that it has a copy of K r with at least r blue edges and at least r red edges, contradicting Claim 2.7 (recall that W ′ is a subgraph of W ).
We thus conclude that W has at least (1 − γ) k 2 ≥ (1 − ǫ 2 ) k 2 edges, and that even if p = p either all but ǫ 2 k 2 of them are red or all but at most ǫ 2 k 2 of them are blue. By the definition of W , this means that in the equipartition V either all but ǫ k 2 of the pairs are ǫ-regular with density p ± ǫ, or all but at most ǫ k 2 of them are ǫ-regular with density p ± ǫ, which completes the proof.

Proofs of additional lemmas
We end this section with the proofs of Lemmas 2.3, 2.5 and 2.6.
Proof of Lemma 2.3: We claim that one can take ǫ = ǫ 2.3 (ζ) = 1 8 ζ and t = t 2.3 (ζ) = 8/ζ. Indeed, suppose G has an ǫ-super-regular partition {V 1 , . . . , V k } of order k ≥ t, that is, a partition in which all but ǫ k 2 of the pairs (V i , V j ) are ǫ-regular with density d(V i , V j ) = p ± ǫ. Let us count the number of edges of G that do not connect a pair (V i , V j ) which is ǫ-regular with density d(V i , V j ) = p ± ǫ. As k ≥ t ≥ 8/ζ we know that the number of pairs of vertices that both belong to the same set V i is at most k|n/k| 2 ≤ 1 8 ζn 2 . As all but ǫ k 2 of the pairs (V i , V j ) are ǫ-regular with density d(V i , V j ) = p ± ǫ, we also know that the number of pairs connecting pairs (V i , V j ), which do not satisfy these two conditions, is bounded by ǫ k 2 (n/k) 2 ≤ 1 8 ζn 2 . Consider now a set of vertices U , and define U i = U ∩ V i . The number of vertices of U that belong to a set U i whose size is smaller than ǫ|V i | is bounded by ǫn. Therefore the number of pairs of vertices of U such that one of them belongs to a set U i of size smaller than ǫ|V i | is bounded by ǫn 2 ≤ 1 8 ζn 2 . Combining the above three facts we conclude that all but 1 2 ζn 2 of the pairs of vertices of u i , u j ∈ U are such that: (1) is ǫ-regular with density p ± ǫ. Therefore, by the definition of a regular pair we get that the density of U in all but 1 2 ζn 2 of its pairs is p ± 2ǫ = p ± 1 2 ζ, and therefore e(U ) = 1 2 p|U | 2 ± ζn 2 .
Proof of Lemma 2.5: Suppose we randomly pick r vertices v 1 , . . . , v r from K with repetitions where r = Ω(1/ǫ 3 ). Clearly, if k ≥ 10r 2 then by a Birthday-Paradox argument we infer that with probability at least 3/4 all the vertices v 1 , . . . , v r are distinct. Suppose wlog that r is even and let us partition the set of unordered pairs (v i , v j ) into r − 1 perfect matchings M 1 , . . . , M r−1 on the vertices v 1 , . . . , v r . For every pair (v i , v j ) let p i,j be the indicator random variable for the event that v i and v j are connected in K by a red edge. As we sample with repetitions then for every matching M t , the r/2 events {p i,j : (v i , v j ) ∈ M t } are independent. Also, as K has at least ǫ k 2 red edges, we have that P r[p i,j = 1] ≥ ǫ/2 (we lose a little due to the probability of having non distinct vertices). We thus conclude that for any matching M t , the expected number of red edges spanned by its members is at least ǫr/4 and by a Chernoff bound, the probability of deviating from this expectation by more than ǫr/8 is bounded by 2 −Θ(ǫ 2 r) < 1/4r. Clearly the same analysis applies for the blue edges. We conclude by the union bound that with probability at least 3/4 the r vertices span at least ǫr 2 /16 red edges and at least ǫr 2 /16 blue edges. As r = Ω(1/ǫ 3 ) we have ǫr 2 /16 ≥ r therefore we have the required amount of red/blue edges. We conclude that one can take r 2.5 = Ω(1/ǫ 3 ) and N 2.5 (r) = 10r 2 .
Finally, to conclude that all the pairs (v i , v j ) are connected we take γ 2.5 = 1/4r 2 . This way, the probability that a pair of vertices are not connected is at most 1/4r 2 and by the union bound, with probability at least 3/4 they are all connected. So to recap, if we sample with repetition r vertices, then with probability at least 1/4 they are all distinct, all connected, and have at least r red edges and at least r blue edges. So there must be at least one such set of r vertices in K.
Proof of Lemma 2.6: Suppose k is large enough to guarantee by Rödl's theorem [19] that the complete graph on k vertices contains (1 − γ) k 2 / r 2 edge disjoint copies of K r . If we now consider the same copies of K r in K (more precisely, the vertex sets of these copies) then the fact that K has (1 − γ) k 2 edges implies that at most γ k 2 = γ r 2 · k 2 / r 2 of these copies of K r have a pair of vertices that are not connected. Thus, K contains at least (1 − γr 2 ) k 2 / r 2 edge disjoint copies of K r implying that at least (1 − γr 2 ) k 2 edges of K belong to a copy of K r .

Proof of the Key Lemma
As in Section 2, let us fix a real 0 < p < 1 and a fixed graph H on h vertices. Let also p be the conjugate of p with respect to H. We will again work with weighted complete graphs W on r vertices, and will identify the vertices of W with [r] and the vertices of H with [h]. Each pair of vertices 1 ≤ i < j ≤ r of W has a weight 0 ≤ w(i, j) ≤ 1 that is given by some weight function w : E(W ) → [0, 1]. We remind the reader of the notation W (φ) that was introduced at the beginning of Section 2.
Recall that Lemma 2.1 states that, if all the values W (φ) are close to what they should be, then all the weights w(i, j) are close to what they should be. The following lemma is an "exact" version of Lemma 2.1 where we assume that the values W (φ) are exactly what they should be. The proof of Lemma 2.1 will then follow from the lemma below using standard continuity arguments. Observe that the lemma below actually gives a bit more information than what we need for Lemma 2.  We split the proof of Lemma 3.1 into two parts. We initially prove Lemma 3.2 below showing that all w(i, j) are taken from {p, p}. We then use this lemma in order to show that in fact most of the w(i, j) are either p or p.
An important ingredient in the proof of Lemma 3.2 will be a theorem of Gottlieb [10], concerning the rank of set inclusion matrices. For integers r ≥ h > 2, the inclusion matrix A(r, h) is defined as follows: The rows of A(r, h) are indexed by h-element subsets of [r], and the columns by the 2-element subsets of [r]. Entry (i, j) of A(r, h) is 1 if the 2-element set, whose index is j, is contained in the h-element set, whose index is i. Otherwise, this entry is 0. Notice that A(r, h) is a square matrix if and only if r = h + 2, and that for r > h + 2, A(r, h) has more rows than columns. Trivially, rank(A(r, h)) ≤ r 2 . However, Gottlieb [10] proved 9 that in fact Theorem 4 (Gottlieb [10]) rank(A(r, h)) = r 2 for all r ≥ h + 2.
Lemma 3.2 Let H be a fixed graph with h > 2 vertices. If r ≥ h + 2 and W is a labeled weighted graph on r vertices satisfying W (φ) = δ H (p) for all φ ∈ Φ, then w(i, j) ∈ {p, p} for all 1 ≤ i < j ≤ r.
Proof: We associate a variable x i,j for each 1 ≤ i < j ≤ r, which represents the unknown w(i, j). Thus, for any φ ∈ Φ we have that W (φ) is given by the polynomial As our assumption is that W (φ) = δ H (p) for all φ ∈ Φ we have the following set of r!/(r − h)! polynomial equations E φ : Our goal now is to show that the only solution to this system is x i,j ∈ {p, p}. For a vertex set S ⊆ [r] of size h, let E[S] denote the h 2 edges of W induced by S. Let S be the set of all h-element subsets of V (W ) = [r] and notice that |S| = r h . For every S ∈ S let Φ S be the set of all h! elements of Φ that are bijections on S. For every set S let us take the product of the h! equations {E φ : φ ∈ Φ S } of (13). We thus get the following system of r h polynomial equations (one for every S ∈ S) with r 2 variables (one for each (i, j) ∈ E(W )): In order to show that the only solution of the equations E S is given by x i,j ∈ {p, p}, it would be convenient to first transform them to linear equalities, by taking logarithms on both sides. Define and note that if we take logarithm of the equations given in (14) and use the y i,j defined above, we thus obtain an equivalent system of linear equations on the r 2 variables y i,j , where equation E S becomes E ′ S : We can write the r h linear equations E ′ S as Ax = b where A in an r h × r 2 matrix, and b is the all h 2 · log(δ H (p)) vector. A key observation at this point is that A is precisely the inclusion matrix A(r, h). Since r ≥ h + 2 we obtain, by Theorem 4, that the system has a unique solution and the values of the variables y i,j are uniquely determined. Now, as each set S ∈ S is of size h it is clear that setting y i,j = log(δ H (p)) for all (i, j) gives a valid solution of the linear equations given in (16), and by the above observation, this is in fact the unique solution. Recalling the definition of y i,j in (15), this implies that for all (i, j) we have Now, as {p, p} are the only solutions to the above equation, we deduce that indeed x i,j ∈ {p, p}, proving the lemma.
For the proof of Lemma 3.1, we will need another simple lemma. A graph is called pairwise regular if there exists a number t so that d(x) + d(y) − d(x, y) = t for all pairs of distinct vertices x, y. Here d(v) denotes the degree of v and d(u, v) = 1 if (u, v) is an edge, otherwise d(u, v) = 0. A graph is called pairwise outer-regular if there exists a number t so that d(x) + d(y) − 2d(x, y) = t for all pairs of distinct vertices x, y. Trivially, a graph is pairwise regular if and only if its complement is. The same holds for pairwise outer-regular. It is also trivial that the complete graph (and the empty graph) is both pairwise regular and pairwise outer-regular. Notice, that K 1,2 is also pairwise regular, and that K 1,3 is also pairwise outer-regular. The following lemma, whose proof is deferred to the end of this section, establishes that these are the only non-trivial cases.

Lemma 3.3
The only non-complete and non-empty graphs which are pairwise regular are K 1,2 and its complement. The only non-complete and non-empty graphs which are pairwise outer-regular are K 1,3 and its complement.
Proof of Lemma 3.1: Notice that if p = p then there is actually nothing to prove, since Lemma 3.2 already yields the desired conclusion. Hence, assume p = p. Observe, that this implies that H in not the complete graph nor the empty graph as in these two cases p = p.
By Lemma 3.2, each edge weight is either p or p. We color the edges of W with two colors: blue for edges whose weight is p and red for edges whose weight is p. We may assume that our coloring is non-trivial, that is, that we have both red and blue edges, since otherwise there is nothing to prove. Each φ ∈ Φ defines a labeled copy of H in W . Let b(φ) be the number of edges of H mapped to blue edges and let a(φ) be the number of non-edges 10 of H mapped to blue edges. Then, the number of edges of H mapped to red edges is m − b(φ) and the number of non-edges of H mapped to red edges is h 2 − m − a(φ). Thus, we have for every φ ∈ Φ that Multiplying (17) where in the second equality we use the fact that p m (1 − p) ( h 2 )−m = δ H (p). This implies that On the other hand, since p and p are both solutions of the equation Thus, solving (19) for p p and plugging it into (20) gives that for any φ Consider first the case where gcd(m, h 2 ) = 1. This implies that gcd(m, h 2 − m) = 1. Since the red-blue coloring is not trivial there is a K h subgraph of W which contains both red and blue edges. Thus there exists φ ∈ Φ so that 0 < a(φ) + b(φ) < h 2 . There are two ways in which (21) can be satisfied: the first is if a(φ) = b(φ) = 0, but this violates the fact that 0 < a(φ) + b(φ). The second is if a(φ) is a multiple of h 2 − m and b(φ) is a multiple of m, but this violates a(φ) + b(φ) < h 2 . Thus, the coloring must be trivial, and we are done. Now consider the case gcd(m, h 2 ) > 1. By Ramsey's Theorem if N 3.1 (h) is sufficiently large, there is a monochromatic copy of K 3h−8 in W . Let T denote a maximal monochromatic copy in W . Thus, T has t vertices and r > t ≥ 3h − 8. Suppose, wlog, that T is completely red. Let x be a vertex outside T . By maximality of T , there exists y ∈ T so that (x, y) is blue. Suppose x has at least h − 2 red neighbors in T , say (x, v 1 ), . . . , (x, v h−2 ) are all red. Then, {x, y, v 1 , . . . , v h−2 } induce a copy of K h which has precisely one blue edge. If φ is any bijection onto this copy then a(φ) + b(φ) = 1, but this must violate (21) and hence the coloring must be trivial and we are done.
We may now assume that each vertex x outside T has at most h − 3 red neighbors in T . Now, if t = r − 1 then there are at most r − 1 blue edges in our coloring, all incident with x, and we are done. Otherwise, there are at least two vertices x 1 and x 2 outside T , that have at least t − 2(h − 3) ≥ 3h − 8 − 2h + 6 = h − 2 common neighbors {v 1 , . . . , v h−2 } in T so that all edges (x i , v j ) are blue for i = 1, 2 and j = 1, . . . , h − 2.
For the proof of Lemma 2.1, we will need the following simple fact Claim 3.4 For any integer p and δ there is a γ = γ 3.4 (δ, p) with the following property: Let A be any p × p non-singular 0/1 matrix, let b be any vector in R p and let x ∈ R p be the unique solution of the system of linear equations Proof: Fix any p×p non-singular matrix A with 0/1 entries. Then the solution of Ax = b is given by Now, as there are finitely many 0/1 p × p matrices, we can set γ = γ 3.4 (δ, p) = min A γ(δ, A), where the minimum is taken over all 0/1 p × p matrices.
Proof of Lemma 2.1: The lemma is an immediate consequence of Lemma 3.1 using standard arguments of continuity; the continuity of polynomials as functions, and the continuity of unique solutions to linear systems that is given in Lemma 3.4 above. First we can take N 2.1 (h) = N 3.1 (h). Now, given any r ≥ N 3.1 (h) and ǫ we need to show that if all W (φ) are very close to δ H (p) then we can get the conclusion of Lemma 2.1.
First, we see that in Lemma 3.2 if all W (φ) are close to δ H (p) then by Lemma 3.4 any solution to the linear equations E ′ S given in (16) satisfies that all y i,j are very close to log(δ H (p)). By continuity of 2 x this means that x m i,j (1 − x i,j ) ( h 2 )−m is close to δ H (p), which again by continuity of x k implies that either x i,j is close to p or to p. So the conclusion of Lemma 3.2 is that if all W (φ) are close to δ H (p), then all densities are indeed close to either p or p.
For the rest of the proof, in equations (17) and (18) we replace p and p with quantities close to them. This means that (19) and (20) are no longer equations but approximately equal to 1. This implies that in (21) we also have approximate equality. However, note that as both sides of (21) involve integers, once the two sides are close enough, they must in fact be equal. Now, as the rest of the proof only relies on the validity of (21) it follows verbatim as in the proof of Lemma 3.1.
It is interesting to note that we cannot hope to prove a stronger version of Lemma 3.1 in which all edge weights are the same, regardless of gcd( h 2 , m). Indeed, consider the case where H = C h is a cycle with h ≥ 4 vertices. For every r ≥ h + 1, there are weighted complete graphs W with r vertices having W (φ) = δ H (p) for each φ ∈ Φ, while still some edges of W have weight p and others have weight p. Indeed, assume that all weights of edges not incident with r ∈ W have weight p, and the r − 1 edges incident with r have weight p. Now, if the image of φ does not contain r then, clearly, On the other hand, if the image of φ contains r then But note that p 2 (1 − p) h−3 is just δ H (p) 2/h , and hence it also equals p 2 (1 − p) h−3 . Consequently, W (φ) = δ H (p) in this case as well.
Proof of Lemma 3.3: Let us say that (x 1 , y 1 )(x 2 , y 2 ) are violating, with respect to the property of being pairwise regular if d(x 1 ) + d(y 1 ) − d(x 1 , y 1 ) = d(x 2 ) + d(y 2 ) − d(x 2 , y 2 ) and violating with respect to the property of being pairwise outer-regular if d(x 1 )+ d(y 1 )− 2d(x 1 , y 1 ) = d(x 2 )+ d(y 2 )− 2d(x 2 , y 2 ). Suppose first that G is a pairwise regular graph which is neither complete nor empty. We claim that this implies that |d(x) − d(y)| ≤ 1 for any two vertices x, y ∈ V (G). Indeed, if there is a pair that violates this, then (x, z), (y, z) is violating for any z. Note that G cannot be regular, otherwise (x 1 , y 1 )(x 2 , y 2 ) is violating whenever (x 1 , y 1 ) is and edge and (x 2 , y 2 ) is not. So partition the vertices of G into two non empty sets, V 1 and V 2 , where all the vertices of V 1 have degree s and those of V 2 have degree s − 1.
If |V 1 | > 1 then V 1 must be a clique otherwise (x 1 , x 2 )(x 2 , y) is violating for any non-adjacent x 1 , x 2 ∈ V 1 and y ∈ V 2 . In particular, we have t = 2s − 1. We also have that |V 2 | = 1 as otherwise (x 1 , x 2 )(y 1 , y 2 ) is violating for any x 1 , x 2 ∈ V 1 and y 1 , y 2 ∈ V 2 . If the unique vertex v of V 2 is connected to x 1 ∈ V 1 but not to x 2 ∈ V 1 then (x 1 , v)(x 2 , v) is clearly violating, so v is either connected to all the vertices of V 1 or else is an isolated vertex. If v is an isolated vertex then s = 1, which implies that V 1 is a clique of size 2, and G is thus the complement of K 1,2 . If v is connected to all the vertices of V 1 then |V 1 | = s − 1 which is impossible, since in a graph with s vertices there cannot be vertices with degree s. If |V 1 | = 1 then we must have |V 2 | > 1. Note that in this case V 2 must span an independent set as otherwise (x, y 1 )(y 1 , y 2 ) is violating for any choice of adjacent y 1 , y 2 ∈ V 2 and x ∈ V 1 . As G is not edgeless we infer that s − 1 = 1 implying that G is K 1,2 .
Suppose now that G is pairwise outer-regular and is neither complete nor empty. Following the same reasoning as above, we must have for any two vertices x, y of G, that |d(x) − d(y)| ≤ 2. Again, note that G cannot be regular, so partition the vertices of G into two non-empty sets, V 1 and V 2 , where all of the vertices of V 1 have degree s and all the vertices of V 2 have degree s − 1 or s − 2. If |V 1 | > 1 then again V 1 must span a clique, as otherwise (x 1 , x 2 )(x 2 , y) is violating for any x 1 , x 2 ∈ V 1 and y ∈ V 2 , and therefore t = 2s − 2. Note that if y ∈ V 2 is connected to x ∈ V 1 then (x 1 , x)(x, y) is violating for any other x 1 ∈ V 1 . Also, if |V 2 | ≥ 2 then any pair of vertices of V 2 must be disconnected with degree s − 1 as otherwise (x 1 , x 2 )(y 1 , y 2 ) is violating for any x 1 , x 2 ∈ V 1 and y 1 , y 2 ∈ V 2 . We thus get that the degree of vertices in V 2 is zero, hence either s = 1 or s = 2. The former case implies that t = 0 and that |V 1 | = 2. This means that G has just one edge, which is not an outer-regular graph. If s = 2 then |V 1 | = 3 implying that G is a triangle plus some isolated vertices. If there is one such vertex then G is the complement of K 1,3 , and if there are two such vertices y 1 , y 2 , then (y 1 , y 2 )(y 1 , v) is violating for any v ∈ V 1 . So assume that |V 1 | = 1, which implies that |V 2 | ≥ 2. Let x be the unique vertex of V 1 , and observe that if x is connected to y 1 ∈ V 2 but not to y 2 ∈ V 2 then (x, y 1 )(x, y 2 ) is violating. So either v is connected to all the vertices of V 2 or to none of them, but note that the latter case is impossible as s > s − 1 ≥ 0. We now claim that V 2 must be edgeless. Indeed if y 1 , y 2 ∈ V 2 are connected and d(y 1 ) ≥ d(y 2 ) then (y 1 , y 2 )(x, y 1 ) is violating. We infer that the degree of the vertices of V 2 is 1, so G is either K 1,2 , which is not outer regular, or K 1,3 .