Notes on my book:
Large networks and graph limits

American Mathematical Society, Providence, Rhode Island, 2012





Section 1.3.1: Property testing. Talking about "property testing" I should have used the phrase "graph property testing". In a different context, testing whether a polynomial is linear or multilinear has been considered earlier (M. Blum, M. Luby and R. Rubinfeld: Self-Testing/Correcting with Applications to Numerical Problems, Proc. 22nd ACM STOC (1990), 73-83; L. Babai, L. Fortnow and C. Lund: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols, 31st IEEE FOCS (1990), 16-25.)

Section 6.4.1: On the dimension of graph algebras for homomorphism functions. Martin Dyer has kindly pointed out that the proof of Theorems 6.36--6.40 only works if we allow loops. Luckily, the theorem remains true without the loops; the proof can be corrected using the results of the preceding section (6.3. Contractors and connectors). Dyer also suggests a connection with the computational complexity theory of homomorphism numbers. [Details]

Section 9.5: Weak uniqueness of weak regularity partitions. We have seen that weak regularity partitions do not give unique template graphs in general. But if we consider weak regularity partitions of a graphon, then the template graphs become more and more similar to each other as the error decreases. [Details]

Furthermore, there is an error in the proof of Theorem 9.32: the two relations above "(see Figure 9.1...)" do not follow from contractivity. But it is easy to fix (and becomes simpler). [Details]

Section 11.8.2: Removal Lemma for null sets. The Removal Lemma has a version, where the set of triangles has measure 0, and we want to remove a set of edges with measure 0 and destroy all triangles. In fact, an appropriate generalization holds for any induced subgraph. The proof is quite different. [Details]

Section 13.5: The automorphism group of a pure graphon is compact. [Details]

Section 17.2: On the convergence of multigraphs with unbounded edge-multiplicities. One can extend the notions of regularity partitions and the cut distance to multigraphs with unbounded edge-multiplicities, and prove extensions of the Regularity and Counting lemmas. Based on these results, one can construct a limit object reflecting the limits of subgraph densities of simple graphs. A complete result (extending also the results in Chapter 17) is not yet available. [Details]

Section 23.4: Regularity Lemmas for categories. There is a quite natural generalization of the Regularity Lemma (in various forms, weak and stronger) to categories. The main shortcoming is that there is no Counting Lemma to go with it. [Details]

Section 20.1.1: Existence of a stationary distribution for the Markov chain on weighting pairs of a graph. Proof of Lemma 20.2. [Details]

Appendix A.3.4: Characterizing convergence of coupling measures. Proof of Proposition A.6. [Details]

Appendix A.3.4: Coupling measures concentrated on a specified set. Proof and generalization of Proposition A.7. [Details]

Last modified April 7, 2013.