Graph Limits

Graph Theory and Additive Combinatorics 5 Graph limits 5.1 Introduction and statements of main results Graph limits seeks a generalization of analytic limits to graphs. Consider the following two examples that shows the potential parallel between the set of rational numbers and graphs: Example 5.1. For x ∈ [0, 1], the minimum of x3 − x occurs at x = √ 1/ 3. But if we restrict ourselves in Q (pretending that we don’t know about real numbers), a way to express this minimum is to find √ a sequence x1 , x2 , . . . of rational numbers that converges to 1/ 3. Example 5.2. Given p ∈ (0, 1), we want to minimize the density of C4 ’s among all graphs with edge density p. From Theorem 4.1 we see that the minimum is p4 , which is obtained via a sequence of quasirandom graphs. (There is no single finite graph that obtains this minimum.) We can consider the set of all graphs as a set of discrete objects (analogous to Q), and seek its "completion" (analogously R). Definition 5.3. A graphon ("graph function") is a symmetric measurable function W : [0, 1]2 → [0, 1]. Remark 5.4. Definition 5.3 can be generalized to Ω × Ω → [0, 1] where Ω is any measurable probability space, but for simplicity we will usually work with Ω = [0, 1]. (In fact, most "nice" measurable probability space can be represented by [0, 1].) The codomain of the function can also be generalized to R, in which case we will refer to the function as a kernel. Note that this naming convention is not always consistent in literature. Graphons can be seen as a generalized type of graphs. In fact, we can convert any graph into a graphon, which allow us to start imagining what the limits of some sequences of graph should look like. Example 5.5. Consider a half graph Gn , which is a bipartite graph where one part is labeled 1, 2, . . . , n and the other part is labeled n + 1, . . . , 2n, and vertices i and n + j is connected if and only if i ≤ j. If we treat the adjacency matrix Adj( Gn ) as a 0/1 bit image, we can define graphon WGn : [0, 1]2 → [0, 1] (which consists of (2n)2 "pixels" of size 1/(2n) × 1/(2n) each). When n goes to infinity, the graphon converges (pointwise) to a function that looks like Figure 5.2. This process of converting graphs to graphons can be easily generalized. Definition 5.6. Given a graph G with n vertices (labeled 1, . . . , n), we define its associated graphon as WG : [0, 1]2 → [0, 1] obtained by partitioning [0, 1] = I1 ∪ I2 ∪ · · · In with λ( Ii ) = 1/n such that if ( x, y) ∈ Ii × Ij , then W ( x, y) = 1 if i and j are connected in G and 0 otherwise. (Here λ( I ) is the Lebesgue measure of I.) However, as we experiment with more examples, we see that using pointwise limit as in Example 5.5 does not suffice for our purpose in general. 4 8 3 7 2 6 1 5 Figure 5.1: The half graph Gn for n = 4 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 Example 5.7. Consider any sequence of random (or quasirandom) graphs with edge density 1/2 (with number of vertices approaching infinity), then the limit (should) approach the constant function W = 1/2, though it certainly does not do so pointwise. Example 5.8. Consider a complete bipartite graph Kn,n with the two parts being odd-indexed and even-indexed vertices. Since the adjacency matrix looks like a checkerboard, we may expect limit to look like the 1/2 constant function as well, but this is not the case: if we instead label the two parts 1, . . . , n and n + 1, . . . 2n, then we see that the graphons should in fact converge to a 2 × 2 checkerboard instead. Figure 5.2: The graph of WGn (for n = 4) and the limit as n goes to infinity (black is 1, white is 0) The examples above show that we need to (at the very least) take care of relabeling of the vertices in our definition of graph limits. Definition 5.9. A graph homomorphism from H to G is a map φ : V ( H ) → V ( G ) such that if uv ∈ E( H ) then φ(u)φ(v) ∈ E( G ). (Maps edges to edges.) Let Hom( H, G ) be the set of all such homomorphisms. and let hom( H, G ) = | Hom( H, G )|. Define homomorphism density as hom( H, G ) t( H, G ) = . |V ( G )||V ( H )| This is also the probability that a uniformly random map is a homomorphism. Example 5.10. • hom(K1 , G ) = |V ( G )|, Figure 5.3: A graph of WKn,n and two possible limits of WKn,n as n goes to infinity • hom(K2 , G ) = 2| E( G )|, • hom(K3 , G ) is 6 times the number of triangles in G, • hom( G, K3 ) is the number of proper 3-colorings of G (where the colors are labeled, say red/green/blue). Remark 5.11. Note that the homomorphisms from H to G do not quite correspond to copies of subgraphs H inside G, because the homomorphisms can be non-injective. Since the number of noninjective homomorphisms contribute at most O H (n|V ( H )−1| ) (where n = |V ( G )|), they form a lower order contribution as n → ∞ when H is fixed. Definition 5.12. Given a symmetric measurable function W : [0, 1]2 → R, define t( H, W ) = Z ∏ [0,1]|V ( H )| ij∈ E( H ) W ( xi , x j ) ∏ dxi . i ∈V ( H ) Note that t( H, G ) = t( H, WG ) for every G and H. Example 5.13. When H = K3 , we have t ( K3 , W ) = Z W ( x, y)W (y, z)W (z, x ) dxdydz. [0,1]3 This can be viewed as the "triangle density" of W. We may now define what it means for graphs to converge and what the limit is. Definition 5.14. We say that a sequence of graphs Gn (or graphons Wn ) is convergent if t( H, Gn ) (or t( H, Wn )) converges as n goes to infinity for every graph H. The sequence converges to W if t( H, Gn ) (or t( H, Wn )) converges to t( H, W ) for every graph H. Remark 5.15. Though not necessary for the definition, we can think of |V ( Gn )| going to infinity as n goes to infinity. A natural question is whether a convergent sequence of graphs has a "limit". (Spoiler: yes.) We should also consider whether the "limit" we defined this way is consistent with what we expect. To this end, we need a notion of "distance" between graphs. One simple way to define the distance between G and G 0 to be ∑k 2−k |t( Hk , G ) − t( Hk , G 0 )| for some sequence H1 , H2 , . . . of all the graphs. (Here 2−k is added to make sure the sum converges to a number between 0 and 1.) This is topologically equivalent to the concept of convergence in Definition 5.14, but it is not useful. Another possibility is to consider the edit distance between two graphs (number of edge changes needed), normalized by a factor of 1/|V ( G )|2 . This is also not very useful, since the distance between any two G (n, 1/2) is around 1/4, but we should expect them to be similar (and hence have o (1) distance). This does, however, inspires us to look back to our discussion of quasirandom graphs and consider when a graph is close to constant p (i.e. similar to G (n, p)). Recall the DISC criterion in Theorem 4.1, where we expect |e( X, Y ) − p| X ||Y || to be small if the graph is sufficiently random. We can generalize this idea to compare the distance between two graphs: intuitively, two graphs (on the same vertex set, say) are close if |eG ( X, Y ) − eG0 ( X, Y )|/n2 is small for all subsets X and Y. We do, however, need some more definitions to handle (for example) graph isomorphisms (which should not change the distances) and graphs of different sizes. Definition 5.16. The cut norm of W : [0, 1]2 → R is defined as kW k  = sup S,T ⊆[0,1] Z S× T W , where S and T are measurable sets. For future reference, we also define some related norms. Definition 5.17. For W : [0, 1]2 → R, define the L p norm as R 1/p kW k p = ( |W | p ) , and the L∞ norm as the infimum of all the ream numbers m such that the set of all the points ( x, y) for which W ( x, y) > m has measure zero. (This is also called the essential supremum of W.) Definition 5.18. We say that φ : [0, 1] → [0, 1] is measure-preserving if λ( A) = λ(φ−1 ( A)) for all measurable A ⊆ [0, 1]. Example 5.19. The function φ( x ) = x + 1/2 mod 1 is clearly measurepreserving. Perhaps less obviously, φ( x ) = 2x mod 1 is also measurepreserving, since while each interval is dilated by a factor of 2 under φ, every point has two pre-images, so the two effects cancel out. This only works because we compare A with φ−1 ( A) instead of φ( A). Definition 5.20. Write W φ ( x, y) = W (φ( x ), φ(y)) (intuitively, "relabelling the vertices"). We define the cut distance δ (U, W ) = inf kU − W φ k φ where φ is a measure-preserving bijection. For graphs G, G 0 , define the cut distance δ ( G, G 0 ) = δ (WG , WG0 ). We also define the cut distance between a graph and a graphon as δ ( G, U ) = δ (WG , U ). Note that φ is not quite the same as permuting vertices: it is allowed to also split vertices or overlay different vertices. This allows us to optimize the minimum discrepancy/cut norm better than simply considering graph isomorphisms. Remark 5.21. The inf in the definition is indeed necessary. Suppose U ( x, y) = xy and W = U φ , where φ( x ) = 2x mod 1, we cannot attain 0 kU − W φ k = 0 for any φ0 (although the cut distance is 0) since φ is not bijective. Now we present the main theorems in graph limit theory that we will prove later. First of all, one might suspect that there is an alternative definition of convergence using the cut distance metric, but it turns out that this definition is equivalent to Definition 5.14. Theorem 5.22 (Equivalence of convergence). A sequence of graphs or graphons is convergent if and only if it is a Cauchy sequence with respect to the cut (distance) metric. Borgs, Chayes, Lovász, Sós, and Vesztergombi (2008) (A Cauchy sequence with respect to metric d is a sequence { xi } that satisfies supm≥0 d( xn , xn+m ) → 0 as n → ∞.) Theorem 5.23 (Existence of limit). Every convergent sequence of graphs or graphons has a limit graphon. Lovász and Szegedy (2006) Denote W̃0 as the space of graphons, where graphons with cut distance 0 are identified. Theorem 5.24 (Compactness of the space of graphons). The set W̃0 is a compact metric space under the cut metric. Remark 5.25. Intuitively, this means that the spaces of "essentially different" graphs is not very large. This is similar to the regularity lemma, where every graph has a constant-size description that approximates the graph well. In fact, we can consider this compactness theorem as a qualitative analytic version of the regularity lemma. 5.2 W-random graphs Recall the Erdős-Rényi random graphs G (n, p) we’ve seen before. We now introduce its graphon generalization. Let’s start with a special case, the stochastic block model. It is a graph with vertices colored randomly (blue or red), and two red vertices are connected with probability prr , a red vertex and a blue vertex are connected with probability prb = pbr , and two blue vertices are connected with probability pbb . Definition 5.26. Uniformly pick x1 , . . . , xn from the interval [0, 1]. A W-random graph, denoted G(n, W ), has vertex set [n] and vertices i and j are connected with probability W ( xi , x j ). Lovász and Szegedy (2007) x1 r An important statistical question is that given a graph, whether there is a good model for where this graph comes from. This gives some motivation to study W-random graphs. We also learnt that the sequence of Erdős-Rényi random graphs converges to the constant graphon, where below is an analogous result. b x1 ∗ x2 ∗ The proof for the above theorem uses Azuma’s inequality in order to show that t( F, Gn ) ≈ t( F, W ) with high probability. Regularity and counting lemmas We now develop a series of tools to prove Theorem 5.24. Theorem 5.29 (Counting Lemma). For graphons W, U and graph F, we have |t( F, W ) − t( F, U )| ≤ | E( F )| δ (W, U ). Proof. It suffices to prove |t( F, W ) − t( F, U )| ≤ | E( F )|kW − U k . Indeed, by considering the above over U replaced by U φ , and taking the infimum over all measure-preserving bijections φ, we obtain the desired result. R Recall that the cut norm kW k = supS,T ⊆[0,1] | S×T W |. Now we prove its useful reformulation: for measurable functions u and v, Z S,T ⊆[0,1] S× T W = sup u,v:[0,1]→[0,1] Z [0,1]2 W ( x, y)u( x )v(y)dxdy . Here’s the reason for the equality to hold: we take u = 1S and v = 1T so the left hand side is no more than the right hand side, and then the bilinearity of the integrand in u, v yields the other direction (the extrema are attained for u, v taking values at 0 or 1). We now illustrate the case when F = K3 . Observe that t ( K3 , W ) − t ( K3 , U ) = = Z Z ((W ( x, y)W ( x, z)W (y, z) − U ( x, y)U ( x, z)U (y, z))dxdydz (W − U )( x, y)W ( x, z)W (y, z)dxdydz + + Z Z U ( x, y)(W − U )( x, z)W (y, z)dxdydz U ( x, y)U ( x, z)(W − U )(y, z)dxdydz. Take the first term as an example: for a fixed z, Z (W − U )( x, y)W ( x, z)W (y, z)dxdydz ≤ kW − U k b x2 ∗ ∗ ∗ Figure 5.4: 2-block model Remark 5.28. In particular, every graphon W is the limit of some sequence of graphs. This gives us some form of graph approximations. sup x3 ∗ x3 Theorem 5.27. Let W be a graphon. Suppose that for all n, Gn are chosen from W-random graphs independently, then Gn → W almost surely. 5.3 r by the above reformulation. Therefore, the whole sum is bounded by 3kW − U k as we desire. For a general graph F, by the triangle inequality we have |t( F, W ) − t( F, U )| = Z ( ∏ W ( ui , vi ) − ui vi ∈ E ≤ ∏ | E| Z i −1 | E| i =1 j =1 k = i +1 ∑ ∏ U (u j , v j )(W (ui , vi ) − U (ui , vi )) ∏ ∏ dv U (ui , vi )) ui vi ∈ E v ∈V ! W (uk , vk ) ∏ dv . v ∈V Here, each absolute value term in the sum is bounded by kW − U k the cut norm if we fix all other irrelavant variables (everything except ui and vi for the i-th term), altogether implying that |t( F, W ) − t( F, U )| ≤ | E( F )| δ (W, U ). We now introduce an “averaging function” for graphon W. Definition 5.30. For a partition P = {S1 , . . . , Sk } of [0, 1] into measurable subsets, and W : [0, 1]2 → R a symmetrical measurable function, define the stepping operator WP : [0, 1]2 → R constant on each Si × S j R such that WP ( x, y) = λ(S )1λ(S ) S ×S W if ( x, y) ∈ Si × S j . i j i j (We ignore the defined term when the denominator equals to 0, because the sets are measure-zero anyway). This is actually a projection in Hilbert space L2 ([0, 1]2 ), onto the subspace of functions constant on each step Si × S j . It can also be viewed as the conditional expectation with respect to the σ-algebra generated by Si × S j . Theorem 5.31 (Weak regularity lemma). For any e > 0 and any graphon W : [0, 1]2 → R, there exists a partition P of [0, 1] into no 2 more than 41/e measurable sets such that kW − WP k ≤ e. Definition 5.32. Given graph G, a partition P = {V1 , . . . , Vk } of V ( G ) is called weakly e-regular if for all A, B ⊂ V ( G ), k e( A, B) − ∑ d(Vi , Vj )| A ∩ Vi || B ∩ Vj | ≤ e|V ( G )|2 . i,j=1 These are similar but different notions we have seen when introducing Theorem 3.5. Theorem 5.33 (Weak Regularity Lemma for Graphs). For all e > 0 and graph G, there exists a weakly e-regular partition of V ( G ) into up to 2 41/e parts. Lemma 5.34 (L2 energy increment). Let W be a graphon and P a partition of [0, 1], satisfying kW − WP k > e. There exists a refinement P 0 of P dividing each part of P into no more than 4 parts, such that kWP 0 k22 > kWP k22 + e2 . Frieze-Kannan (1999) Proof. Because kW − WP k > e, there exist subsets S, T ⊂ [0, 1] R such that | S×T (W − WP )| > e. Let P 0 be the refinement of P by introducing S and T (divide P based on whether it’s in S \ T,T \ S, S ∩ T or S ∩ T), and that gives at most 4 sub-parts each. R Define hW, U i to be WU. We know that hWP , WP i = hWP 0 , WP i because WP is constant on each step of P , and P 0 is a refinement of P . Thus, hWP 0 − WP , WP i = 0. By Pythagorean Theorem, kWP 0 k22 = kWP 0 − WP k22 + kWP k22 > kWP k22 + e2 , where the latter inequality comes by the Cauchy–Schwarz inequality, k1S×T k2 kWP 0 − WP k2 ≥ |hWP 0 − WP , 1S×T i| = |hW − WP , 1S×T i| > e. Proposition 5.35. For any e > 0, graphon W, and P0 partition of [0, 1], 2 there exists partition P refining part of P0 into no more than 41/e parts, such that kW − WP k ≤ e. This proposition specifically tells us that starting with any given partition, the regularity argument still works. Proof. We repeatedly apply Lemma 5.34 to obtain P0 , P1 , . . . partitions of [0, 1]. For each step, we either have kW − WP k ≤ e and thus stop, or we know kWP 0 k22 > kWP k22 + e2 . Because kWPi k22 ≤ 1, we are guaranteed to stop after fewer than than e−2 steps. We also know that each part is subdivided into no −2 more than 4 parts at each step, obtaining 4e as we desire. We hereby introduce a related result in computer science, the MAXCUT problem: given a graph G, we want to find max e(S, S̄) among all vertex subsets S ⊂ V ( G ). Polynomial-time approximation algorithms developed by Goemans and Williamson that finds a cut within around 0.878 fraction of the optimum. conjecture known as the Unique Games Conjecture would imply that the it would not be possible to obtain a better approximation than the Goemans– Williamson algorithm.2306295 states the impossibility of beating this. It is shown that approximating beyond 16 17 ≈ 0.941 is NP-hard. On the other hand, the MAXCUT problem becomes easy to approximate for dense graphs, i.e., approximating the size of the maximum cut of an n-vertex graph with in to en2 additive error in time polynomial in n, where e > 0 is a fixed constant. One can apply an algorithmic version of the weak regularity lemma and brute-force search through all possible partition sizes of the parts. This application was one of the original motivations of the weak regularity lemma. Goemans and Williamson (1995) Khot, Kindler, Mossel, and O’Donnell (2007) Håstad (2001) 5.4 Compactness of the space of graphons Definition 5.36. A martingale is a random sequence X0 , X1 , X2 , . . . such that for all n, E[ Xn | Xn−1 , Xn−2 , . . . , X0 ] = Xn−1 . Example 5.37. Let Xn denotes the time n balance at a fair casino, where the expected value of each round’s gain is 0. Then { Xn }n≥0 is a martingale. Example 5.38. For a fixed random variable X, we define Xn = E( X | information up to time n), so that this sequence also forms a martingale. Theorem 5.39 (Martingale Convergence Theorem). Every bounded martingale converges almost surely. Remark 5.40. Actually, instead of bounded, it is enough for the martingales to be L1 -bounded or uniform integrable, both of which gives sup E( Xn+ ) < ∞. We sketch a idea inspired by a betting strategy. The proof below omits some small technical details that can be easily filled in for those who are familiar with the basic language of probability theory. Proof. An “upcrossing” of [ a, b] consists of an interval [n, n + t] such that Xn < a, and Xn+t is the first instance after Xn such that Xn+t > a. We refer to the figure on the right instead of giving a more precise definition. Suppose there is a sequence of bounded martingale { Xn } that doesn’t converge. Then there exists rational numbers 0 < a < b < 1 such that { Xn } upcrosses the interval [ a, b] infinitely many times. We will show that this event occurs with probability 0 (so that after we sum over a, b ∈ Q, { Xn } converges with probability 1). Denote u N to be the number of upcrossings (crossings from below to above the interval) up to time N. Consider the following betting strategy: at any time, we hold either 0 or 1 share. If Xn < a, then buy 1 share and hold it until the first time that the price (Xn ) reads more than b (i.e. we sell at time m such that Xm > b for the first time and m > n). How much profit do we make from this betting strategy? We pocket b − a for each upcrossing. Accounting for difference between our initial and final balance, our profit is at least (b − a)u N − 1. On the other hand, the optional stopping theorem tells us that every “fair” betting strategy on a margingale has zero expected profit. So because the profits of a martingale is zero, 0 = E profit ≥ (b − a)Eu N − 1, • b • • a • • • • • • • • • • • n Figure 5.5: examples of “upcrossings” which implies Eu N ≤ b−1 a . Let u∞ = lim N →∞ u N denotes the total number of upcrossings. By the monotone convergence theorem, we have Eu∞ ≤ b−1 a too, hence P(u∞ = ∞) = 0, implying our result. We now prove the main theorems of graph limits using the tools developed in previous sections, namely the weak regularity lemma (Theorem 5.31) and the martingale convergence theorem (Theorem 5.39). We will start by proving that the space of graphons is compact (Theorem 5.24). In the next section we will apply this result to prove Theorem 5.23 and Theorem 5.22, in that order. We will also see how compactness can be used to prove a graphon-reformulation of the strong regularity lemma. e 0 is the space of graphons modulo the equivalence Recall that W e 0 , δ ) is a metric relation W ∼ U if δ (W, U ) = 0. We can see that (W space. Theorem 5.41 (Compactness of the space of graphons). The metric e 0 , δ ) is compact. space (W e 0 is a metric space, it suffices to prove sequential comProof. As W pactness. Fix a sequence W1 , W2 , . . . of graphons. We want to show that there is a subsequence which converges (with respect to δ ) to some limit graphon. For each n, apply the weak regularity lemma (Theorem 5.31) repeatedly, to obtain a sequence of partitions Pn,1 , Pn,2 , Pn,3 , . . . such that (a) Pn,k+1 refines Pn,k for all n, k, (b) |Pn,k | = mk where mk is a function of only k, and (c) Wn − Wn,k  ≤ 1/k where Wn,k = (Wn )Pn,k . The weak regularity lemma only guarantees that |Pn,k | ≤ mk , but if we allow empty parts then we can achieve equality. Initially, each partition may be an arbitrary measurable set. However, for each n, we can apply a measure-preserving bijection φ to Wn,1 and Pn,1 so that Pn,1 is a partition of [0, 1] into intervals. For each k ≥ 2, assuming that Pn,k−1 is a partition of [0, 1] into intervals, we can apply a measure-preserving bijection to Wn,k and Pn,k so that Pn,k is a partition of [0, 1] into intervals, and refines Pn,k−1 . By induction, we therefore have that Pn,k consists of intervals for all n, k. Properties (a) and (b) above still hold. While property (c) may not hold, and it’s no longer true that Wn,k = (Wn )Pn,k , we still know that δ (Wn , Wn,k ) ≤ 1/k for all n, k. This will suffice for our purposes. Lovász and Szegedy (2007) Now, the crux of the proof is a diagonalization argument in countably many steps. Starting with the sequence W1 , W2 , . . . , we will repeatedly pass to a subsequence. In step k, we pick a subsequence Wn1 , Wn2 , . . . such that: 1. the endpoints of the parts of Pni ,k all individually converge as i → ∞, and 2. Wni ,k converges pointwise almost everywhere to some graphon Uk as i → ∞. There is a subsequence satisfying (1) since each partition Pn,k has exactly mk parts, and each part has length in [0, 1]. So consider a subsequence (Wai )i∞=1 satisfying (1). Each Wai ,k can be naturally identified with a function f ai ,k : [mk ]2 → [0, 1]. The space of such functions is bounded, so there is a subsequence ( f ni )i∞=1 of ( f ai )i∞=1 converging to some f : [mk ]2 → [0, 1]. Now f corresponds to a graphon Uk which is the limit of the subsequence (Wni )i∞=1 . Thus, (2) is satisfied as well. To conclude step k, the subsequence is relabeled as W1 , W2 , . . . and the discarded terms of the sequence are ignored. The corresponding partitions are also relabeled. Without loss of generality, in step k we pass to a subsequence which contains W1 , . . . , Wk . Thus, the end result of steps k = 1, 2, . . . is an infinite sequence with the property that (Wn,k )∞ n=1 converges pointwise almost everywhere (a.e.) to Uk for all k: W1 k = 1 W1,1 k = 2 W1,2 k = 3 W1,3 .. .. . . W2 W2,1 W2,2 W2,3 .. . W3 W3,1 W3,2 W3,3 .. . ... ... ... ... .. . → U1 → U2 → U3 .. . pointwise a.e. pointwise a.e. pointwise a.e. Similarly, (Pn,k )∞ n=1 converges to an interval partition Pk for all k. By property (a), each partition Pn,k+1 refines Pn,k , which implies that Wn,k = (Wn,k+1 )Pn,k . Taking n → ∞, it follows that Uk = (Uk+1 )Pk (see Figure 5.6 for an example). Now each Uk can be thought of as a random variable on probability space [0, 1]2 . From this view, the equalities Uk = (Uk+1 )Pk exactly imply that the sequence U1 , U2 , . . . is a martingale. The range of each Uk is contained in [0, 1], so the martingale is bounded. By the martingale convergence theorem (Theorem 5.39), there exists a graphon U such that Uk → U pointwise almost everywhere as k → ∞. Recall that our goal was to find a convergent subsequence of W1 , W2 , . . . under δ . We have passed to a subsequence by the above diagonalization argument, and we claim that it converges to U under U1 P1 0.5 0.4 0.6 P2 U2 0.6 0.4 0.3 0.4 0.7 0.4 0.4 0.5 0.4 0.9 U3 0.7 0.4 0.4 0.4 P3 0.4 0.9 0.4 0.4 Figure 5.6: An example of possible U1 , U2 , and U3 , each graphon averaging the next. δ . That is, we want to show that δ(Wn , U ) → 0 as n → ∞. This follows from a standard "3-epsilons argument": let e > 0. Then there exists some k > 3/e such that kU − Uk k1 < e/3, by pointwise convergence and the dominated convergence theorem. Since Wn,k → Uk pointwise almost everywhere (and by another application of the dominated convergence theorem), there exists some n0 ∈ N such that Uk − Wn,k 1 < e/3 for all n > n0 . Finally, since we chose k > 3/e, we already know that δ(Wn , Wn,k ) < e/3 for all n. We conclude that δ(U, Wn ) ≤ δ(U, Uk ) + δ(Uk , Wn,k ) + δ(Wn,k , Wn ) ≤ kU − Uk k1 + Uk − Wn,k 1 + δ(Wn,k , Wn ) ≤ e. The second inequality uses the general bound that δ(W1 , W2 ) ≤ kW1 − W2 k ≤ kW1 − W2 k1 for graphons W1 , W2 . 5.5 Applications of compactness e 0 , δ ) to prove several results, We will now use the compactness of (W notably the strong regularity lemma for graphons, the equivalence of the convergence criteria defined by graph homomorphism densities and by the cut norm, and the existence of a graphon limit for every sequence of graphons with convergent homomorphism densities. As a warm-up, we will prove that graphons can be uniformly approximated by graphs under the cut distance. The following lemma expresses what we could easily prove without compactness: Lemma 5.42. For every e > 0 and every graphon W, there exists some graph G such that δ ( G, W ) < e. Proof. By a well-known fact from measure theory, there is a step function U such that kW − U k1 < e/2. For any constant graphon p there is a graph G such that k G − pk < e/2; in fact, a random graph G (n, p) satisfies this bound with high probability, for sufficiently large n. Thus, we can find a graph G such that k G − U k < e/2 by piecing together random graphs of various densities. So δ ( G, W ) ≤ kW − U k1 + kU − G k < e as desired. However, in the above lemma, the size of the graph may depend on W. This can be remedied via compactness. Proposition 5.43. For every e > 0 there is some N ∈ N such that for any graphon W, there is a graph G with N vertices such that δ ( G, W ) < e. Proof. For a graph G, define the e-ball around G by Be ( G ) = {W ∈ e 0 : δ ( G, W ) < e}. W As G ranges over all graphs, the balls Be ( G ) form an open cover e 0 , by Lemma 5.42. By compactness, this open cover has a fiof W nite subcover. So there is a finite set of graphs G1 , . . . , Gk such that e 0 . Let N be the least common multiple of Be ( G1 ), . . . , Be ( Gk ) cover W the vertex sizes of G1 , . . . , Gk . Then for each Gi there is some N-vertex graph Gi0 with δ ( Gi , Gi0 ) = 0, obtained by replacing each vertex of Gi with N/|V ( Gi )| vertices. But now W is contained in an e-ball around some N-vertex graph. Remark 5.44. Unfortunately, the above proof gives no information about the dependence of N on e. This is a byproduct of applying compactness. One can use regularity to find an alternate proof which gives a bound. e0 W G e e 0 by open balls Figure 5.7: Cover of W Figure 5.8: A K3 and its 2-blowup. Note that the graphs define equal graphons. Intuitively, the compactness theorem has a similar flavor to the regularity lemma; both are statements that the space of graphs is in some sense very small. As a more explicit connection, we used the weak regularity lemma in our proof of compactness, and the strong regularity lemma follows from compactness straightforwardly. Theorem 5.45 (Strong regularity lemma for graphons). Let e = (e1 , e2 , . . . ) be a sequence of positive real numbers. Then there is some M = M (e) such that every graph W can be written W = Wstr + Wpsr + Wsml where • Wstr is a step function with k ≤ M parts, • Wpsr  ≤ ek , • kWsml k1 ≤ e1 . Proof. It is a well-known fact from measure theory that any measurable function can be approximated arbitrarily well by a step function. Thus, for every graphon W there is some step function U such that kW − U k1 ≤ e1 . Unfortunately, the number of steps may depend on W; this is where we will use compactness. For graphon W, let k(W ) be the minimum k such that some kstep graphon U satisfies kW − U k1 ≤ e1 . Then { Bek(W ) }W ∈W e 0 is e 0 , and by compactness there is a finite set clearly an open cover of W e e 0. of graphons S ⊂ W0 such that { Be (W )}W ∈S covers W k (W ) Lovász and Szegedy (2007) If ek = e/k2 , then this theorem approximately recovers Szemerédi’s Regularity Lemma. If ek = e, then it approximately recovers the Weak Regularity Lemma. Let M = maxW ∈S k(W ). Then for every graphon W, there is some W 0 ∈ S such that δ (W, W 0 ) ≤ ek(W 0 ) . Furthermore, there is a k-step graphon U with k = k (W 0 ) ≤ M such that kW 0 − U k1 ≤ e1 . Hence, W = U + (W − W 0 ) + (W 0 − U ) is the desired decomposition, with Wstr = U, Wpsr = W − W 0 , and Wsml = W 0 − U. Earlier we defined convergence of a sequence of graphons in terms of the sequences of F-densities. However, up until now we did not know that the limiting F-densities of a convergent sequence of graphons are achievable by a single graphon. Without completing the space of graphs to include graphons, this is in fact not true, as we saw in the setting of quasirandom graphs. Nonetheless in the space of graphons, the result is true, and follows swiftly from compactness. Theorem 5.46 (Existence of limit). Let W1 , W2 , . . . be a sequence of graphons such that the sequence of F-densities {t( F, Wn )}n converges for every graph F. Then the sequence of graphons converges to some W. That is, there exists a graphon W such that t( F, Wn ) → t( F, W ) for every F. Lovász and Szegedy (2006) Proof. By sequential compactness, there is a subsequence (ni )i∞=1 and a graphon W such that δ (Wni , W ) → 0 as i → ∞. Fix a graph F. By Theorem 5.29, it follows that t( F, Wni ) → t( F, W ). But by assumption, the sequence {t( F, Wn )}n converges, so all subsequences have the same limit. Therefore t( F, Wn ) → t( F, W ). The last main result of graph limits is the equivalence of the two notions of convergence which we had defined previously. Theorem 5.47 (Equivalence of convergence). Convergence of Fdensities is equivalent to convergence under the cut norm. That is, let W1 , W2 , . . . be a sequence of graphons. Then the following are equivalent: • The sequence of F-densities {t( F, Wn )}n converges for all graphs F • The sequence {Wn }n is Cauchy with respect to δ . Proof. One direction follows immediately from Theorem 5.29, the counting lemma: if the sequence {Wn }n is Cauchy with respect to δ , then the counting lemma implies that for every graph F, the sequence of F-densities is Cauchy, and therefore convergent. For the reverse direction, suppose that the sequence of F-densities converges for all graphs F. Let W and U be limit points of {Wn }n (i.e. limits of convergent subsequences). We want to show that W = U. Let (ni )i∞=1 be the subsequence such that Wni → W. By the counting lemma, t( F, Wni ) → t( F, W ) for all graphs F, and by convergence of F-densities, t( F, Wn ) → t( F, W ) for all graphs F. Similarly, t( F, Wn ) → t( F, U ) for all F. Hence, t( F, U ) = t( F, W ) for all F. Borgs, Chayes, Lovász, Sós, and Vesztergombi (2008) By the subsequent lemma, this implies that U = W. Lemma 5.48 (Moment lemma). Let U and W be graphons such that t( F, W ) = t( F, U ) for all F. Then δ (U, W ) = 0. Proof. We will sketch the proof. Let G(k, W ) denote the W-random graph on k vertices (see Definition 5.26). It can be shown that for any k-vertex graph F, Pr[G(k, W ) ∼ = F as labelled graph] = 0 (−1) E( F )−E( F) t( F 0 , W ). ∑ 0 F ⊇F In particular, this implies that the distribution of W-random graphs is entirely determined by F-densities. So G(k, W ) and G(k, U ) have the same distributions. Let H(k, W ) be an edge-weighted W-random graph on vertex set [k], with edge weights sampled as follows. Let x1 , . . . , xk ∼ Unif([0, 1]) be independent random variables. Set the edge-weight of (i, j) to be W ( xi , x j ). We claim two facts, whose proofs we omit • δ (H(k, W ), G(k, W )) → 0 as k → ∞ with probability 1, and • δ1 (H(k, W ), W ) → 0 as k → ∞ with probability 1. Since G(k, W ) and G(k, U ) have the same distribution, it follows from the above facts and the triangle inequality that δ (W, U ) = 0. A consequence of compactness and the moment lemma is that the "inverse" of the graphon counting lemma also holds: a bound on Fdensities implies a bound on the cut distance. The proof is left as an exercise. Corollary 5.49 (Inverse counting lemma). For every e > 0 there is some η > 0 and integer k > 0 such that if U and W are graphons with |t( F, U ) − t( F, W )| ≤ η for every graph F on at most k vertices, then δ (U, W ) ≤ e. Remark 5.50. The moment lemma implies that a graphon can be recovered by its F-densities. We might ask whether all F-densities are necessary, or whether a graphon can be recovered from, say, finitely many densities. For example, we have seen that if W is the pseudorandom graphon with density p, then t(K2 , W ) = p and t(C4 , W ) = p4 ; furthermore, it is uniquely determined by these densities. If the equalities hold then δ (W, p) = 0. The graphons which can be recovered from finitely many Fdensities in this way are called "finitely forcible graphons". Among This lemma is named in analogy with the moment lemma from probability, which states that if two random variable have the same moments (and are sufficiently well-behaved) then they are in fact identically distributed. the graphons known to be finitely forcible are any step function and the half graphon W ( x, y) = 1 x+y≥1 . More generally, W ( x, y) = 1 p( x,y)≥0 is finitely forcible for any symmetric polynomial p ∈ R[ x, y] which is monotone decreasing on [0, 1]. 5.6 Lovász and Sós (2008) Lovász and Szegedy (2011) Inequalities between subgraph densities One of the motivations for studying graph limits is that they provide an efficient language with which to think about graph inequalities. For instance, we could be able to answer questions such as the following: Question 5.51. If t(K2 , G ) = 1/2, what is the minimum possible value of t(C4 , G )? We know the answer to this question; as discussed previously, by Theorem 4.1 we can consider a sequence of quasirandom graphs; their limit is a graphon W such that t(K2 , W ) = 2−4 . In this section we work on these kind of problems; specifically, we are interested in homomorphism density inequalities. Two graph inequaities have been discussed previously in this book; Mantel’s theorem (Theorem 2.2) and Turán’s theorem (Theorem 2.6): Theorem 5.52 (Mantel’s Theorem). Let W : [0, 1]2 → [0, 1] be a graphon. If t(K3 , W ) = 0, then t(K2 , W ) ≤ 1/2. Our goal in this section is to determine the set of all feasible edge density, triangle density pairs for a graphon W, which can be formally written as D2,3 = {(t(K2 , W ), t(K3 , W )) : W graphon } ⊆ [0, 1]2 . We know that the limit point of a sequence of graphs is a graphon (Theorem 5.23), hence the region D2,3 is closed. Moreover, Mantel’s Theorem (Theorem 5.52) tells us that the horizontal section of this region when triangle density is zero extends at most until the point (1/2, 0) ∈ [0, 1]2 (see Figure 5.9). A way in which we can describe D2,3 is by its cross sections. A simple argument below shows that each vertical cross section of D2,3 is a line segment: Proposition 5.54. For every 0 ≤ r ≤ 1, the set D2,3 ∩ [0, 1] × {r } is a line segment with no gaps. t ( K3 , W ) Theorem 5.53 (Turán’s theorem). Let W : [0, 1]2 → [0, 1] be a graphon. If t(Kr+1 , W ) = 0, then t(K2 , W ) ≤ 1 − 1/r. t ( K2 , W ) Figure 5.9: Mantel’s Theorem implication in the plot of D2,3 (red line) Proof. Consider two graphons W0 , W1 with the same edge density; then, we can consider Wt = (1 − t)W0 + tW1 , which is a graphon; moreover, its triangle density is mapped continuously as t varies from 0 to 1. Its initial and final values are t(K3 , W0 ) and r (K3 , W1 ), respectively, so every triangle density between these values can be achieved. Then, in order to better understand the shape of D2,3 , we would like to determine the minimum and maximum subgraph densities that can be achieved given a fixed edge density. We begin by addressing this question: Question 5.55. What is the maximum number of triangles in an n-vertex m-edge graph? An intuitive answer would be that the edges should be arranged so as to form a clique. This turns out to be the correct answer: a result known as the Kruskal–Katona theorem implies that a graph with (2k ) has at most (3k ) triangles. Here we prove an slightly weaker version of this bound. The Kruskal–Katona theorem can be proved using a “compression argument”: we repeatedly “push” the edges towards the clique and show that number of triangles can never decrease in the process. a Theorem 5.56. For every graphon W : [0, 1]2 → [0, 1], a t(K3 , W ) ≤ t(K2 , W )3/2 . Remark 5.57. This upper bound is achieved by a graphon like the one shown in Figure 5.10, which is a limit graphon of a sequence of cliques in G; for each of these graphons, edge and triangle densities are, respectively, t ( K2 , W ) = a 2 , 1 0 Figure 5.10: Graphon which achieves upper boundary of D2,3 : t(K2 , W ) = a2 and t(K3 , W ) = a3 1 t ( K3 , W ) = a 3 . Proof of Theorem 5.56. It suffices to prove the following inequality for every graph G: t(K3 , G ) ≤ t(K2 , G )3/2 . Let us look at hom(K3 , G ) and hom(K2 , G ); these count the number of closed walks in the graph of length 3 and 2, respectively. These values correspond to the second and third moments of the spectrum of the graph G: k hom(K3 , G ) = ∑ λ3i i =1 k and hom(K2 , G ) = ∑ λ2i i =1 t ( K3 , W ) 0.75 Therefore, The upper boundary of the region D3,2 is given by the curve y = x3/2 , as shown by Figure 5.11. 0.5 0.75 0 0 0.25 0.5 0.75 1 t ( K2 , W ) Figure 5.11: Plot of upper boundary of D2,3 , given by the curve y = x3/2 in [0, 1]2 Where {λi }in=1 are the eigenvalues of the adjacency matrix AG . We then have that n hom(K3 , G ) = ∑ λ3i n ≤ ∑ !3/2 λ2i = hom(K2 , G )3/2 . (5.1) i =1 i =1 After dividing by |V ( G )|3 on both sides, the result follows. Note that in the last proof, we used the following useful inequality, with ai = λ2i and t = 3/2: Claim 5.58. Let t > 1, and a1 , · · · , an ≥ 0. Then, a1t + · · · + atn ≤ ( a1 + · · · + an )t Proof. This inequality is homogeneous with respect to the variables ai , so we can normalize and assume that ∑ ai = 1; therefore, each of the ai ∈ [0, 1], so that ait ≤ ai for each i. Therefore, LHS = a1t + · · · + atn ≤ a1 + · · · + an = 1 = 1t = RHS. The reader might wonder whether there is a way to prove this without using eigenvalues of the graph G. We have following result, whose proof does not require spectral graph theory: Theorem 5.59. For every W : [0, 1]2 → R which is symmetric, t(K3 , W ) ≤ t(K2 , W 2 )3/2 where W 2 corresponds to the graphon W, squared pointwise. Note that above, t(K2 , W )3/2 falls in between these two terms when W is a graphon because all the terms would be bounded between 0 and 1; therefore, the above result is stronger than that of Theorem 5.56. The proof of this result follows from applying the Cauchy–Schwarz inequality three times; one corresponding to each edge of a triangle K3 . Proof. We have t ( K3 , W ) = Z [0,1]3 W ( x, y)W ( x, z)W (y, z)dxdydz. From now on, we drop the notation for our intervals of integration. We can apply the Cauchy–Schwarz inequality on the following integral; first with respect to the variable dx, and subsequently with respect to the variables dy, dz, each time holding the other two vari- ables constant: t ( K3 , W ) = Z W ( x, y)W ( x, z)W (y, z)dxdydz 1/2 Z 1/2 Z Z ≤ W ( x, y)2 dx W ( x, z)2 dx W (y, z)dydz ≤ ≤ Z Z Z 2 W ( x, y) dxdy W ( x, y)2 dxdy 1/2 Z 1/2 Z 2 W ( x, z) dx W ( x, z)2 dxdz 1/2 Z 1/2 Z 2 1/2 W (y, z) dy W (y, z)2 dydz dz 1/2 = kW k32 = t(K2 , W )3/2 , completing the proof. Remark 5.60. If we did not have the condition that W is symmetric, we could still use Hölder’s inequality; however, we would obtain a weaker statement. In this situation, Hölder’s inequality would imply that Z f ( x, y) g( x, z)h(y, z)dxdydz ≤ k f k3 k gk3 khk3 , [0,1]3 and by setting f = g = h = W, we could derive a weaker bound than the one obtained in the proof of Theorem 5.59 because, in general, kW k 2 ≤ kW k 3 . The next theorem allows us to prove linear inequalities between clique densities. Theorem 5.61 (Bollobás). Let c1 , · · · , cn ∈ R. The inequality Bollobás (1986) n ∑ c r t ( Kr , G ) ≥ 0 r =1 holds for every graph G if and only if it holds for every G = Km with m ≥ 1. More explicitly, the inequality holds for all graphs G if and only if n ∑ cr · r =1 m ( m − 1) · · · ( m − r + 1) ≥0 mr a1 = 0.2 for every m ≥ 1. Proof. One direction follows immediately because the set of clique graphs is a subset of the set of all graphs. We now prove the other direction. The inequality holds for all graphs if and only if it holds for all graphons, again since the set f0 with respect to the cut distance metric. In of graphs is dense in W particular, let us consider the set S of node-weighted simple graphs, with a normalization ∑ ai = 1. a3 = 0.4 a4 = 0.3 a2 = 0.1 a4 0 1 1 1 1 0 0 0 a2 1 0 0 1 a1 1 0 1 0 a3 a1 a2 a3 a4 Figure 5.12: Example of a node weighted graph on four vertices, whose weights sum to 1, and its corresponding As Figure 5.12 shows, each node weighted graph can be repref0 , because this set consented by a graphon. The set S is dense in W tains the set of unweighted simple graphs. Then, it suffices to prove this inequality for graphs in S . Suppose for the sake of contradiction that there exists a node weighted simple graph H such that n f ( H ) := ∑ c r t ( Kr , H ) < 0 r =1 Among all such H, we choose one with smallest possible number m of nodes. We choose node weights a1 , · · · , am with sum equal to 1 such that f ( H ) is minimized. We can find such H because we have a finite number of parameters, and f is a continuous function over a compact set. We have that ai > 0 without loss of generality; otherwise we would have a contradiction because we could delete that node and decrease the quantity |V ( H )|, while f ( H ) < 0 would still hold. Moreover, H is a complete graph; otherwise there exist i, j such that ij 6∈ E( H ). Note that the clique density is a polynomial in terms of the node weights; this polynomial would not have an a2i term because the set of graphons S corresponds to simple graphs, and the vertex i would not be adjacent to itself. This polynomial does not have an ai a j term either, because i and j are not adjacent. Therefore, f ( H ) is multilinear in the variables ai and a j . Fixing all of the other node weights and considering ai , a j as our variables of the multilinear function f ( H ), this function would be minimized by setting ai = 0 or a j = 0. If one of these weights were set to zero, this would imply a decrease in the number of nodes, while ai + a j would be preserved, hence not increasing f ( H ). This is a contradiction to the minimality of number of nodes in H such that f ( H ) < 0. In other words, H must be a complete graph; further, the polynomial f ( H ) on the variables ai has to be symmetric: n f (H) = ∑ cr r!sr , r =1 where each sr is an elementary symmetric polynomial of degree r sr = ∑ a i1 · · · a ir . i1 <··· 0 then f would be minimized when a1 = 0 or a2 = 0; this cannot occur because of the minimality of the number of nodes in H. If C = 0 then any value of a1 , a2 would yield the same minimum value of f ( H ); in particular we could set a1 = 0, again contradicting minimality on the number of nodes. Therefore, the constant C must be negative,implying that f ( H ) would be minimized when a1 = a2 . Then, all of the ai have to be equal, and H can also be regarded as an unweighted graph. In other words, if the inequality of interest fails for some graph H, then it must fail for some unweighted clique H; this completes the proof. Remark 5.62. In the proof above, we only considered clique densities; an inequality over other kinds of graphs would not necessarily hold. Thanks to the theorem above, it is relatively simple to test linear inequalities between densities, since we just have to verify them for cliques. We have the following corollary: Corollary 5.63. For each n, the extremal points of the convex hull of {( (t(K2 , W ), t(K3 , W ), · · · , t(Kn , W )) : W graphon} ⊂ [0, 1]n−1 are given by W = Km for all m ≥ 1. All of the points of these form in fact fall into the curve given by y = x (2x − 1), which is the dotted red curve in Section 5.6. Because the region D2,3 is contained in the convex hull of the red points { pm }m≥0 , it also lies above the curve y = x (2x − 1). We can moreover draw line segments between the convex hull points, so as to obtain a polygonal region that bounds D2,3 . The region D2,3 was determined by Razborov, who developed the theory of flag algebras, which have provided a useful framework in . .. t ( K3 , W ) Note that the above claim implies Turán’s theorem, because by Theorem 5.61, the extrema of the set above are given in terms of clique densities, which can be understood by taking W to be a clique. Thus, if t(Kr+1 , W ) = 0, then this cross section on the higher dimensional cube [0, 1]r will be bounded by the value t(K2 , W ) = 1 − 1r . In the particular case that we want to find the extremal points in the convex hull of D2,3 ⊂ [0, 1]2 , they correspond to   m − 1 (m − 1)(m − 2) pm = , m m2 5/9 12/25 3/8 2/9 0 1 2 2 3 45 3 4 56 ··· t ( K2 , W ) Figure 5.13: Set of lower boundary points of D2,3 , all found in the curve given by y = x (2x − 1) Razborov (2007) which to set up sum of squares inequalities, e.g., large systematic applications of the Cauchy–Schwarz inequalities, that could be used in order to prove graph density inequalities. Theorem 5.64 (Razborov). For a fixed edge density t(K2 , W ), which falls into the following interval, for some k ∈ N   1 1 t ( K2 , W ) ∈ 1 − , ,1− k−1 k Razborov (2008) .. . t ( K3 , W ) the minimum feasible t(K3 , W ) is attained by a unique step function graphon corresponding to a k-clique with node weights a1 , a2 , · · · , ak with sum equal to 1, and such that a1 = · · · = ak−1 ≥ ak . 5/9 12/25 3/8 2/9 The region D2,3 is illustrated on the right in Section 5.6. We have exaggerated the drawwings of the concave “scallops” in the lower boundary of the region for better visual effects. Note that in Turán’s theorem, the construction for the graphs which correspond to extrema value (Chapter 2, definition 2.5) are unique; however, in all of the intermediate values t(t2 , W ) 6= 1 − 1/k, this theorem provides us with non-unique constructions. To illustrate why these constructions are not unique, the graphon in Figure 5.15, which is a minimizer for triangle density when t(t2 , W ) = 2/3 can be modified by replacing the highlighted region by any graphon with the same edge density. Non-uniqueness of graphons that minimize t(K3 , W ) implies that this optimization problem is actually difficult. The problem of minimizing the Kr -density in a graph of given edge density was solved for r = 4 by Nikiforov and all r by Reiher., respectively. More generally, given some inequality between various subgraph densities, can we decide if the inequality holds for all graphons? For polynomial inequalities between homomorphism densities, it suffices to only consider linear densities, since t( H, W )t( H 0 , W ) = t ( H t H 0 , W ). Let us further motivate with a related, more classical question regarding nonnegativity of polynomials: Question 5.65. Given a multivariable polynomial p ∈ R[ x1 , x2 , · · · , xn ], is p( x ) ≥ 0 for every x = ( x1 , · · · , xn )? This problem is decidable, due to a classic result of Tarski that every the first-order theory of the reals is decidable. In fact, we have the following characterization of nonnegative real polynomials. Theorem 5.66 (Artin). A polynomial p ∈ R[ x1 , x2 , · · · , xn ] is nonnegative if and only if it can be written as a sum of squares of rational functions. 0 2 3 45 3 4 56 1 2 ··· t ( K2 , W ) Figure 5.14: Complete description of the region D2,3 ⊂ [0, 1]2 α3 0 1 1 α2 1 0 1 α1 1 1 0 α1 α2 α3 Figure 5.15: A non unique optimal graphon in the case k = 3. Nikiforov (2011) Reiher (2016) However, when we turn our interest into the set of lattice points, the landscape changes: Question 5.67. Given a multivariable polynomial p ∈ R[ x1 , x2 , · · · , xn ], can it be determined whether p( x1 , · · · , xn ) ≥ 0 for all x ∈ Zn ? The answer to the above question is no. This is related to the fact that one cannot solve diophantine equations, or even tell whether there is a solution: Theorem 5.68 (Matiyasevich; Hilbert’s 10th problem). Given a general diophantine equation is an undecidable problem to find its solutions, or even to determine whether integer solutions exist. Matiyasevich (2011) Turning back to our original question of interest, we want to know whether the following question is decidable Question 5.69. For a given set of graphs { Hi }i∈[k] and a1 , · · · , ak ∈ R, is ∑ik=1 ai t( Hi , G ) ≥ 0 true for every graph G? The following theorem provides an answer to this question: Theorem 5.70 (Hatami - Norine). Given a set of graphs { Hi }i∈[k] and a1 , · · · , ak ∈ R, whether the inequality Hatami and Norine (2011) k ∑ ai t( Hi , G) ≥ 0 i =1 is true for every graph G is undecidable. A rough intuition for why the above theorem is true is that we actually have a discrete set of points along the lower boundary of D2,3 ; one could reduce the above problem into proving the same inequalities along the points in the intersection of the red curve and the region. The set of points in this intersection forms a discrete set, and the idea is to encode integer inequalities (which are undecidable) into graph inequalities by using the special points on the lower boundary of D2,3 . Another kind of interesting question is to ask whether specific inequalities are true; there are several open problems of that type. Here is an important conjecture in extremal graph theory: Conjecture 5.71 (Sidorenko’s Conjecture). If H is a bipartite graph then t( H, W ) ≥ t(K2 , W )e( H ) . We worked recently with an instance of the above inequality, when H = C4 , when we were discussing quasirandomness. However, the above problem is open. Let us consider the Möebius strip graph Sidorenko (1993) - which consists in removing a 10-cycle from a complete bipartite graph K5,5 (Section 5.6). The name of this graph comes from its realization as a face-vertex incidence graph of the usual simplicial complex of the Möebius strip. The graph above is the first one for which this inequality remains an open problem. Even if nonnegativeness of a general linear graph inequalities is undecidable, if one wants to decide whether they are true up to an ε-error, the problem becomes more accessible: Theorem 5.72. There exists an algorithm that, for every ε > 0 decides correctly that n ∑ ci t( Hi , G) ≥ −ε i =1 for all graphs G, or outputs a graph G such that n ∑ ci t( Hi , G) < 0. i =1 Proof sketch. As a result of weak regularity lemma, we can take a weakly ε-regular partition. All the information regarding edge densities can be represented by this partition; in other words, one would only have to test a bounded number of possibilities on weighted node graphs with ≤ M(ε) parts whose edge weights are multiples of ε. If the estimate for the corresponding weighted sum of graph densities is true for the auxiliary graph one gets from weak regularity lemma, then it is also true for the original graph up to an ε-error; otherwise, we can output a counterexample. Figure 5.16: The Möebius strip graph.