Limits of dense graph sequences

DOI10.1016/J.JCTB.2006.05.002MaRDI QIDQ859618zbMATH OpenOpenAlexWikidataFDO

Authors Balázs Szegedy, László Lovász

Publication date 16 January 2007

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0408173

zbMATH Keywords

convergent graph sequence graph homomorphism limit quasirandom graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We show that if a sequence of dense graphs has the property that for every fixed graph F, the density of copies of F in these graphs tends to a limit, then there is a natural ``limit object, namely a symmetric measurable 2-variable function on [0,1]. This limit object determines all the limits of subgraph densities. We also show that the graph parameters obtained as limits of subgraph densities can be characterized by ``reflection positivity, semidefiniteness of an associated matrix. Conversely, every such function arises as a limit object. Along the lines we introduce a rather general model of random graphs, which seems to be interesting on its own right.

Review text

Let \((G_{n})\) be a sequence of simple graphs whose number of nodes tends to infinity with \(n\). Let, for a fixed simple graph \(F\), \(\text{ hom}(F,G)\) be the number of homomorphisms from \(F\) into \(G\), and let \[ t(F,G)=\frac{\text{ hom}(F,G)}{| V(G)|^{| V(F)|}} \] be the probability that a random mapping \(V(F)\rightarrow V(G)\) is a homomorphism. The aim of the paper under review is to study, under the assumption that, for every \(F\), \((t(F,G_{n}))\rightarrow t(F)\), the set \({\mathcal T}\) of \(t(F)\) which arise. Note that this question is only of interest when the graph is dense, that is the number of edges is \(\geq c| V(G_{n})|^{2}\) for a constant \(c>0\). The assumption that \((t(F,G_{n}))\rightarrow t(F)\) has been studied by the first author and various co-authors before, as have questions of when a graph property can be equal to the number of homomorphisms \textit{into} a fixed graph. See for example papers such as http://research.microsoft.com/\(\sim\)borgs/Papers/TestStoc.pdf, http://research.microsoft.com/\(\sim\)borgs/Papers/HomRev.pdf, http://arxiv.org/PS\(\underscore\)cache/math/pdf/0404/0404468v1.pdf. There are probably other interesting facts still to be discovered in this area of linking graph properties to homomorphism structure. Clearly one way to characterise \({\mathcal T}\) would be to define an appropriate limit object from which the \(t(F)\) can be read off. The main idea of the paper under review is to show that there is indeed a natural limit object, which is a symmetric measurable function \(W: [0,1]^{2}\rightarrow [0,1]\). The main result in the paper is a set of four conditions on a simple graph parameter \(f(F)\) (i.e. a function on simple graphs which is invariant under isomorphism), each of which is equivalent to \(f(F)\) being in \({\mathcal T}\) (that is, there being a sequence \((G_{n})\) of simple graphs such that \(f(F)=\lim_{n\rightarrow\infty}t(F,G_{n})\)). These conditions are as follows: (1) There is a symmetric measurable function \(W:[0,1]^{2}\rightarrow [0,1]\) for which \(f(F)=t(F,W)\). Here \(t(F,W)\) is, when \(V(F)=\{1,2,\ldots k\}\), given by \[ t(F,W)=\int_{[0,1]^{k}}\prod_{ij\in E(F)}W(x_{i},x_{j})dx_{1}\ldots dx_{k}. \] (2) The parameter \(f\) is normalised (i.e. \(f(K_{1})=1\)), multiplicative (i.e. \(f(G_{1}G_{2})=f(G_{1})f(G_{2})\) where \(G_{1}G_{2}\) denotes the disjoint union of \(G_{1}\) and \(G_{2}\): for example, the parameter \(f(F)=\text{ hom}(F,G)\) is multiplicative) and reflection positive. The last notion is defined as follows: a \(k\)-labelled graph is a finite graph in which \(k\) nodes are labelled by \(1,2\ldots k\). We then define for two \(k\)-labelled graphs \(F_{1}\) and \(F_{2}\) a graph \(F_{1}F_{2}\) by first taking the disjoint union, then identifying nodes with the same label, and finally removing any multiple edges arising from the identifications. (Thus for 0-labelled graphs it is just the disjoint union, as before.) We now define an infinite matrix \(M(k,f)\) indexed by isomorphism classes of \(k\)-labelled graphs, where the entry in the row corresponding to \(F_{1}\) and column corresponding to \(F_{2}\) is \(f(F_{1}F_{2})\) in this sense. We say \(f\) is reflection positive if and only if \(M(k,f)\) is positive-semidefinite for every \(k\geq 0\). (3) This equivalence is specific to parameters defined on simple graphs. Let \(M_{0}(k,f)\) be the submatrix of \(M(k,f)\) formed by the rows and columns indexed by \(k\)-labelled graphs on \(k\) nodes (so every node is labelled): combine these to form \(M_{0}(f)\) whose rows and columns are indexed by all finite graphs whose nodes form a finite subset of \({\mathbb N}\), the entry in the row of \(F_{1}\) and column of \(F_{2}\) being \(f(F_{1}\cup F_{2})\). The condition is now that \(f\) be normalised, multiplicative and \(M_{0}(f)\) is positive-semidefinite. (4) The parameter \(f\) is normalised, multiplicative and \(f^{\dag}(F):=\sum_{F'\supseteq F}(-1)^{| E(F')\backslash E(F)|}f(F')\) satisfies \(f^{\dag}(F)\geq 0\). In the definition of \(f^{\dag}\), the sum is taken over all graphs on the same set of nodes as \(F\) and containing all edges of \(F\). Every symmetric measurable function \(W:[0,1]^{2}\rightarrow [0,1]\), and an integer \(n>0\), gives a random graph \(G(n,W)\) on nodes \(\{1,2,\ldots n\}\) by generating \(n\) independent uniform random variables on \([0,1]\), \(X_{1},\ldots X_{n}\) and saying that \(i\sim j\) with probability \(W(X_{i},X_{j})\) independently of all other edges. If \(W(x,y)=p\) for all \(x,y\) we get classical Erdős-Rényi random graphs \(G(n,p)\) for constant \(p\). (And the graph sequences which converge to this function are essentially the standard quasirandom graphs with density \(p\).) Standard concentration inequalities (e.g. of Azuma type) show that the graph sequence \((G(n,W))\) is convergent with probability 1 and its limit is the function \(W\). (Note this is in one sense a more satisfactory notion of a limit object for this sequence than the Rado (infinite random) graph, as that would not distinguish between the various possible choices of \(p\in (0,1)\).) The authors also show that a random graph model is of the form \(G(n,W)\) if and only if it has three natural properties, namely that the distribution is invariant under relabelling nodes, that if node \(n\) is deleted the distribution of the resulting graph is the same as the distribution on a \(G(n-1,W)\), and for every \(1<k<n\) the subgraphs induced by \(\{1,2,\ldots k\}\) and \(\{k+1,\ldots n\}\) are independent of each other. Proof techniques include proving various relations between various notions of distances, using a weak form of Szemerédi's lemma and martingale concentration inequalities. Much of the material extends to cases where the graphs have weights on the edges and/or nodes. The authors provide some motivation for the approach by noting that for example Goodman's theorem relating the number of edges to the number of triangles can be expressed, and fairly easily derived, in this framework.

Recommendations

Cites work

Cited in

(only showing first 100 items - show all)

This page was built for publication: Limits of dense graph sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q859618)