Graphon

A graphon is a symmetric measurable function $W:[0,1]^2\; \backslash to\; [0,1]$. Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme:

1. Each vertex $j$ of the graph is assigned an independent random value $u\_j\backslash sim\; U[0,1]$
2. Edge $(i,j)$ is independently included in the graph with probability $W(u\_i,u\_j)$.

A random graph model is an exchangeable random graph model if and only if it can be defined in terms of a (possibly random) graphon in this way.

The model based on a fixed graphon $W$ is sometimes denoted $\backslash mathbb\{G\}(n,\; W)$,

by analogy with the Erdős–Rényi model of random graphs.

A graph generated from a graphon $W$ in this way is called a $W$-random graph.

It follows from this definition and the law of large numbers that, if $W\backslash neq0$, exchangeable random graph models are dense almost surely.

The simplest example of a graphon is $W(x,y)\backslash equiv\; p$ for some constant $p\backslash in[0,1]$. In this case the associated exchangeable random graph model is the Erdős–Rényi model $G(n,p)$ that includes each edge independently with probability $p$.

If we instead start with a graphon that is piecewise constant by:

1. dividing the unit square into $k\backslash times\; k$ blocks, and
2. setting $W$ equal to $p\_\{lm\}$ on the $(\backslash ell,m)^\{\backslash text\{th\}\}$ block,

the resulting exchangeable random graph model is the $k$

community stochastic block model, a generalization of the Erdős–Rényi model.

We can interpret this as a random graph model consisting of $k$ distinct Erdős–Rényi graphs with parameters $p\_\{\backslash ell\backslash ell\}$ respectively, with bigraphs between them where each possible edge between blocks $(\backslash ell,\backslash ell)$ and $(m,m)$ is included independently with probability $p\_\{\backslash ell\; m\}$.

Many other popular random graph models can be understood as exchangeable random graph models defined by some graphon, a detailed survey is included in Orbanz and Roy.

A random graph of size $n$ can be represented as a random $n\backslash times\; n$ adjacency matrix. In order to impose consistency (in the sense of projectivity) between random graphs of different sizes it is natural to study the sequence of adjacency matrices arising as the upper-left $n\backslash times\; n$ sub-matrices of some infinite array of random variables; this allows us to generate $G\_n$ by adding a node to $G\_\{n-1\}$ and sampling the edges $(j,n)$ for

Following the fundamental importance of exchangeable sequences in classical probability, it is natural to look for an analogous notion in the random graph setting. One such notion is given by jointly exchangeable matrices; i.e. random matrices satisfying

: $(X\_\{ij\})\; \backslash \; \backslash overset\{d\}\{=\}\; \backslash ,\; (X\_\{\backslash sigma(i)\backslash sigma(j)\})$

for all permutations $\backslash sigma$ of the natural numbers, where $\backslash overset\{d\}\{=\}$ means equal in distribution. Intuitively, this condition means that the distribution of the random graph is unchanged by a relabeling of its vertices: that is, the labels of the vertices carry no information.

There is a representation theorem for jointly exchangeable random adjacency matrices, analogous to de Finetti’s representation theorem for exchangeable sequences. This is a special case of the Aldous–Hoover theorem for jointly exchangeable arrays and, in this setting, asserts that the random matrix $(X\_\{ij\})$ is generated by:

1. Sample $u\_j\backslash sim\; U[0,1]$ independently
2. $X\_\{ij\}=X\_\{ji\}=1$ independently at random with probability $W(u\_i,u\_j),$

where $W:[0,1]^2\backslash to[0,1]$ is a (possibly random) graphon. That is, a random graph model has a jointly exchangeable adjacency matrix if and only if it is a jointly exchangeable random graph model defined in terms of some graphon.

Due to identifiability issues, it is impossible to estimate either the graphon function $W$ or the node latent positions $u\_i,$ and there are two main directions of graphon estimation. One direction aims at estimating $W$up to an equivalence class,{{Cite arXiv|last1=Wolfe|first1=Patrick J.|last2=Olhede|first2=Sofia C.|date=2013-09-23|title=Nonparametric graphon estimation|eprint=1309.5936|class=math.ST}}{{Cite journal|last1=Choi|first1=David|last2=Wolfe|first2=Patrick J.|date=February 2014|title=Co-clustering separately exchangeable network data|arxiv=1212.4093|journal=The Annals of Statistics|volume=42|issue=1|pages=29–63|doi=10.1214/13-AOS1173|s2cid=16291079|issn=0090-5364}} or estimate the probability matrix induced by $W$.{{Cite journal|last1=Gao|first1=Chao|last2=Lu|first2=Yu|last3=Zhou|first3=Harrison H.|date=December 2015|title=Rate-optimal graphon estimation|journal=The Annals of Statistics|volume=43|issue=6|pages=2624–2652|doi=10.1214/15-AOS1354|issn=0090-5364|arxiv=1410.5837|s2cid=14267617}}{{Cite journal|last1=Yuan|first1=Zhang|last2=Elizaveta|first2=Levina|last3=Ji|first3=Zhu|date=2017|title=Estimating network edge probabilities by neighbourhood smoothing|url=https://academic.oup.com/biomet/article-abstract/104/4/771/4158787?redirectedFrom=fulltext|journal=Biometrika|volume=104|issue=4|pages=771–783|doi=10.1093/biomet/asx042|issn=0006-3444}}

Any graph on $n$ vertices $\backslash \{1,\; 2,\; \backslash dots,\; n\backslash \}$ can be identified with its adjacency matrix $A\_G$.

This matrix corresponds to a step function $W\_G\; :\; [0,1]^2\; \backslash to\; [0,\; 1]$,

defined by partitioning $[0,1]$ into intervals

$I\_1,\; I\_2,\; \backslash dots,\; I\_n$ such that $I\_j$ has interior

$$\backslash left(\backslash frac\{j-1\}\{n\},\; \backslash frac\{j\}\{n\}\backslash right)$$

and for each $(x,y)\backslash in\; I\_i\backslash times\; I\_j$, setting $W\_G(x,y)$ equal to the

$(i,j)^\{\backslash text\{th\}\}$

entry of $A\_G$.

This function $W\_G$ is the associated graphon of the graph $G$.

In general, if we have a sequence of graphs $(G\_n)$ where the number of vertices of $G\_n$ goes to infinity, we can analyze the limiting behavior of the sequence by considering the limiting behavior of the functions $(W\_\{G\_n\})$.

If these graphs converge (according to some suitable definition of convergence), then we expect the limit of these graphs to correspond to the limit of these associated functions.

This motivates the definition of a graphon (short for "graph function") as a symmetric measurable function $W:[0,1]^\{2\}\backslash to[0,1]$ which captures the notion of a limit of a sequence of graphs. It turns out that for sequences of dense graphs, several apparently distinct notions of convergence are equivalent and under all of them the natural limit object is a graphon.

Take a sequence of $(G\_n)$ Erdős–Rényi random graphs $G\_n\; =\; G(n,p)$ with some fixed parameter $p$.

Intuitively, as $n$ tends to infinity, the limit of this sequence of graphs is determined solely by edge density of these graphs.

In the space of graphons, it turns out that such a sequence converges almost surely to the constant $W(x,y)\backslash equiv\; p$, which captures the above intuition.

Take the sequence $(H\_n)$ of half-graphs, defined by taking $H\_n$ to be the bipartite graph on $2n$ vertices $u\_1,\; u\_2,\; \backslash dots,\; u\_n$ and $v\_1,\; v\_2,\; \backslash dots,\; v\_\{n\}$ such that $u\_i$ is adjacent to $v\_j$ precisely when $i\backslash le\; j$. If the vertices are listed in the presented order, then

the adjacency matrix $A\_\{H\_n\}$ has two corners of "half square" block matrices filled with ones, with the rest of the entries equal to zero. For example, the adjacency matrix of $H\_3$ is given by

As $n$ gets large, these corners of ones "smooth" out.

Matching this intuition, the sequence $(H\_n)$ converges to the half-graphon $W$ defined by $W(x,y)\; =\; 1$ when $|x-y|\; \backslash ge\; 1/2$ and $W(x,y)\; =\; 0$ otherwise.

Take the sequence $(K\_\{n,n\})$ of complete bipartite graphs with equal sized parts.

If we order the vertices by placing all vertices in one part at the beginning

and placing the vertices of the other part at the end,

the adjacency matrix of $(K\_\{n,n\})$ looks like a block off-diagonal matrix, with two blocks of ones and two blocks of zeros.

For example, the adjacency matrix of $K\_\{2,2\}$ is given by

As $n$ gets larger, this block structure of the adjacency matrix remains constant,

so that this sequence of graphs converges to a "complete bipartite" graphon $W$

defined by $W(x,y)\; =\; 1$ whenever $\backslash min(x,y)\; \backslash le\; 1/2$ and $\backslash max(x,y)\; >\; 1/2$, and setting $W(x,y)\; =\; 0$ otherwise.

If we instead order the vertices of $K\_\{n,n\}$ by alternating between parts,

the adjacency matrix has a chessboard structure of zeros and ones.

For example, under this ordering, the adjacency matrix of $K\_\{2,2\}$ is given by

As $n$ gets larger,

the adjacency matrices become a finer and finer chessboard.

Despite this behavior, we still want the limit of $(K\_\{n,n\})$ to be unique and result in the graphon from example 3.

This means that when we formally define convergence for a sequence of graphs, the definition of a limit should be agnostic to relabelings of the vertices.

Take a random sequence $(G\_n)$ of $W$-random graphs by drawing $G\_n\; \backslash sim\; \backslash mathbb\{G\}(n,\; W)$ for some fixed graphon $W$.

Then just like in the first example from this section, it turns out that $(G\_n)$ converges to $W$ almost surely.

Given graph $G$ with associated graphon $W\; =\; W\_G$, we can recover graph theoretic properties and parameters of $G$ by integrating transformations of $W$. For example, the edge density (i.e. average degree divided by number of vertices) of $G$ is given by the integral

$$\backslash int\_\{0\}^1\; \backslash int\_0^1\; W(x,y)\; \backslash ;\; \backslash mathrm\{d\}x\; \backslash ,\; \backslash mathrm\{d\}y\; .$$

This is because $W$ is $\backslash \{0,1\backslash \}$-valued, and each edge $(i,\; j)$

in $G$

corresponds to a region $I\_i\; \backslash times\; I\_j$

of area $1/n^2$ where $W$ equals $1$.

Similar reasoning shows that the triangle density in $G$ is equal to

$$\backslash frac\; 16\; \backslash int\_0^1\; \backslash int\_0^1\; \backslash int\_0^1\; W(x,y)W(y,z)W(z,x)\; \backslash ;\; \backslash mathrm\{d\}x\; \backslash ,\; \backslash mathrm\{d\}y\; \backslash ,\; \backslash mathrm\{d\}z\; .$$

There are many different ways to measure the distance between two graphs.

If we are interested in metrics that "preserve" extremal properties of graphs,

then we should restrict our attention to metrics that identify random graphs as similar.

For example, if we randomly draw two graphs independently from an Erdős–Rényi model $G(n,p)$ for some fixed $p$, the distance between these two graphs under a "reasonable" metric should be close to zero with high probability for large $n$.

Naively, given two graphs on the same vertex set, one might define their distance as the number of edges that must be added or removed to get from one graph to the other, i.e. their edit distance. However, the edit distance does not identify random graphs as similar; in fact, two graphs drawn independently from $G(n,\backslash tfrac\{1\}\{2\})$ have an expected (normalized) edit distance of $\backslash tfrac\{1\}\{2\}$.

There are two natural metrics that behave well on dense random graphs in the sense that we want.

The first is a sampling metric, which says that two graphs are close if their distributions of subgraphs are close.

The second is an edge discrepancy metric, which says two graphs are close when their edge densities are close on all their corresponding subsets of vertices.

Miraculously, a sequence of graphs converges with respect to one metric precisely when it converges with respect to the other.

Moreover, the limit objects under both metrics turn out to be graphons.

The equivalence of these two notions of convergence mirrors how various notions of quasirandom graphs are equivalent.{{r|qrandom}}

One way to measure the distance between two graphs $G$ and $H$ is to compare their relative subgraph counts.

That is, for each graph $F$ we can compare the number of copies of $F$ in $G$ and $F$ in $H$.

If these numbers are close for every graph $F$, then

intuitively $G$ and $H$ are similar looking graphs.

Rather than dealing directly with subgraphs, however, it turns out to be

easier to work with graph homomorphisms.

This is fine when dealing with large, dense graphs, since in this scenario

the number of subgraphs and the number of graph homomorphisms from a fixed graph are asymptotically equal.

Given two graphs $F$ and $G$, the

homomorphism density $t(F,\; G)$ of $F$ in $G$ is defined to be the number of graph homomorphisms from $F$ to $G$.

In other words, $t(F,G)$ is the probability a randomly chosen map from the vertices of $F$ to the vertices of $G$ sends adjacent vertices in $F$ to adjacent vertices in $G$.

Graphons offer a simple way to compute homomorphism densities.

Indeed, given a graph $G$ with associated graphon $W\_G$ and another $F$, we have

$$t(F,\; G)\; =\; \backslash int\; \backslash prod\_\{(i,j)\backslash in\; E(F)\}\; W\_G(x\_i,\; x\_j)\; \backslash ;\; \backslash left\backslash \{\backslash mathrm\{d\}x\_i\backslash right\backslash \}\_\{i\backslash in\; V(F)\}$$

where the integral is multidimensional, taken over the unit hypercube $[0,1]^\{V(F)\}$.

This follows from the definition of an associated graphon, by considering when the above integrand is equal to $1$.

We can then extend the definition of homomorphism density to arbitrary graphons $W$, by using the same integral and defining

$$t(F,\; W)\; =\; \backslash int\; \backslash prod\_\{(i,j)\backslash in\; E(F)\}\; W(x\_i,\; x\_j)\; \backslash ;\; \backslash left\backslash \{\backslash mathrm\{d\}x\_i\backslash right\backslash \}\_\{i\backslash in\; V(F)\}$$

for any graph $F$.

Given this setup, we say a sequence of graphs $(G\_n)$ is left-convergent if for every fixed graph $F$, the sequence of homomorphism densities $\backslash left(t(F,\; G\_n)\backslash right)$ converges.

Although not evident from the definition alone, if $(G\_n)$ converges in this sense, then there always exists a graphon $W$ such that for every graph $F$, we have

$$\backslash lim\_\{n\backslash to\backslash infty\}\; t(F,\; G\_n)\; =\; t(F,\; W)$$

simultaneously.

Take two graphs $G$ and $H$ on the same vertex set.

Because these graphs share the same vertices,

one way to measure their distance is to restrict to subsets $X,\; Y$ of the vertex set, and for each such pair of subsets compare the number of edges $e\_G(X,Y)$ from $X$ to $Y$ in $G$ to the number of edges $e\_H(X,Y)$ between $X$ and $Y$ in $H$. If these numbers are similar for every pair of subsets (relative to the total number of vertices), then that suggests $G$ and $H$ are similar graphs.

As a preliminary formalization of this notion of distance, for any pair of graphs $G$ and $H$ on the same vertex set $V$ of size $|V|\; =\; n$, define the labeled cut distance between $G$ and $H$ to be

$$d\_\backslash square(G,\; H)\; =\; \backslash frac\; 1\{n^2\}\; \backslash max\_\{X,\; Y\backslash subseteq\; V\}\backslash left|e\_G(X,Y)\; -\; e\_H(X,Y)\backslash right|.$$

In other words, the labeled cut distance encodes the maximum discrepancy of the edge densities between $G$ and $H$.

We can generalize this concept to graphons by expressing the edge density $\backslash tfrac\; 1\{n^2\}\; e\_G(X,\; Y)$ in terms of the associated graphon $W\_G$, giving the equality

$$d\_\backslash square(G,\; H)\; =\; \backslash max\_\{X,\; Y\backslash subseteq\; V\}\; \backslash left|\; \backslash int\_\{I\_X\}\; \backslash int\_\{I\_Y\}\; W\_G(x,\; y)\; -\; W\_H(x,\; y)\; \backslash ;\; \backslash mathrm\{d\}x\; \backslash ,\; \backslash mathrm\{d\}y\; \backslash right|$$

where $I\_X,\; I\_Y\; \backslash subseteq\; [0,\; 1]$ are unions of intervals corresponding to the vertices in $X$ and $Y$. Note that this definition can still be used even when the graphs being compared do not share a vertex set.

This motivates the following more general definition.

Definition 1. For any symmetric, measurable function $f\; :\; [0,1]^2\; \backslash to\; \backslash mathbb\{R\}$, define the cut norm of $f$ to be the quantity

$$\backslash lVert\; f\; \backslash rVert\_\backslash square\; =\; \backslash sup\_\{S,\; T\backslash subseteq\; [0,1]\}\; \backslash left|\; \backslash int\_S\; \backslash int\_\{T\}\; f(x,y)\; \backslash ;\; \backslash mathrm\{d\}x\; \backslash ,\; \backslash mathrm\{d\}y\; \backslash right|$$

taken over all measurable subsets $S,\; T$ of the unit interval.{{r|Lovasz:2013}}

This captures our earlier notion of labeled cut distance, as we have the equality $\backslash lVert\; W\_G\; -\; W\_H\; \backslash rVert\_\backslash square\; =\; d\_\backslash square(G,\; H)$.

This distance measure still has one major limitation: it can assign nonzero distance to two isomorphic graphs.

To make sure isomorphic graphs have distance zero, we should compute the minimum cut norm over all possible "relabellings" of the vertices.

This motivates the following definition of the cut distance.

Definition 2. For any pair of graphons $U$ and $W$, define their cut distance to be

$$\backslash delta\_\backslash square(U,\; W)\; =\; \backslash inf\_\{\backslash varphi\}\; \backslash lVert\; U\; -\; W^\backslash varphi\; \backslash rVert\_\backslash square$$

where $W^\backslash varphi(x,y)\; =\; W(\backslash varphi(x),\; \backslash varphi(y))$ is the composition of $W$ with the map $\backslash varphi$, and the infimum is taken over all measure-preserving bijections from the unit interval to itself.{{r|whatis}}

The cut distance between two graphs is defined to be the cut distance between their associated graphons.

We now say that a sequence of graphs $(G\_n)$ is convergent under the cut distance if it is a Cauchy sequence under the cut distance $\backslash delta\_\backslash square$. Although not a direct consequence of the definition, if such a sequence of graphs is Cauchy, then it always converges to some graphon $W$.

As it turns out, for any sequence of graphs $(G\_n)$, left-convergence is equivalent to convergence under the cut distance, and furthermore, the limit graphon $W$ is the same. We can also consider convergence of graphons themselves using the same definitions, and the same equivalence is true. In fact, both notions of convergence are related more strongly through what are called counting lemmas.{{r|Lovasz:2013}}

Counting Lemma. For any pair of graphons $U$ and $W$, we have

$$|t(F,\; U)\; -\; t(F,\; W)|\; \backslash le\; e(F)\; \backslash delta\_\backslash square(U,\; W)$$

for all graphs $F$.

The name "counting lemma" comes from the bounds that this lemma gives on homomorphism densities $t(F,\; W)$, which are analogous to subgraph counts of graphs. This lemma is a generalization of the graph counting lemma that appears in the field of regularity partitions, and it immediately shows that convergence under the cut distance implies left-convergence.

Inverse Counting Lemma. For every real number $\backslash varepsilon\; >\; 0$, there exist a real number $\backslash eta\; >\; 0$ and a positive integer $k$ such that for any pair of graphons $U$ and $W$ with

$$|t(F,\; U)\; -\; t(F,\; W)|\; \backslash le\; \backslash eta$$

for all graphs $F$ satisfying $v(F)\; \backslash le\; k$,

we must have .

This lemma shows that left-convergence implies convergence under the cut distance.

We can make the cut-distance into a metric by taking the set of all graphons and identifying two graphons $U\; \backslash sim\; W$ whenever $\backslash delta\_\backslash square(U,\; W)\; =\; 0$.

The resulting space of graphons is denoted $\backslash widetilde\{\backslash mathcal\{W\}\}\_0$, and together with $\backslash delta\_\backslash square$ forms a metric space.

This space turns out to be compact.

Moreover, it contains the set of all finite graphs, represented by their associated graphons, as a dense subset.

These observations show that the space of graphons is a completion of the space of graphs with respect to the cut distance. One immediate consequence of this is the following.

Corollary 1. For every real number $\backslash varepsilon\; >\; 0$, there is an integer $N$ such that for every graphon $W$, there is a graph $G$ with at most $N$ vertices such that .

To see why, let $\backslash mathcal\{G\}$ be the set of graphs. Consider for each graph $G\; \backslash in\; \backslash mathcal\{G\}$ the open ball $B\_\backslash square(G,\; \backslash varepsilon)$ containing all graphons $W$ such that . The set of open balls for all graphs covers $\backslash widetilde\{\backslash mathcal\{W\}\}\_0$, so compactness implies that there is a finite subcover $\backslash \{\; B\_\backslash square(G,\; \backslash varepsilon)\; \backslash mid\; G\; \backslash in\; \backslash mathcal\{G\}\_0\; \backslash \}$ for some finite subset $\backslash mathcal\{G\}\_0\; \backslash subset\; \backslash mathcal\{G\}$. We can now take $N$ to be the largest number of vertices among the graphs in $\backslash mathcal\{G\}\_0$.

Compactness of the space of graphons $(\backslash widetilde\{\backslash mathcal\{W\}\}\_0,\; \backslash delta\_\{\backslash square\})$ can be thought of as an analytic formulation of Szemerédi's regularity lemma; in fact, a stronger result than the original lemma.{{cite journal

| last1=Lovász | first1=László | authorlink1=László Lovász

| last2=Szegedy | first2=Balázs

| title=Szemerédi's lemma for the analyst

| journal=Geometric and Functional Analysis

| date=2007

| volume=17

| pages=252–270

| doi=10.1007/s00039-007-0599-6

| s2cid=15201345}}

Szemeredi's regularity lemma can be translated into the language of graphons as follows. Define a step function to be a graphon $W$ that is piecewise constant, i.e. for some partition $\backslash mathcal\{P\}$ of $[0,1]$, $W$ is constant on $S\; \backslash times\; T$ for all $S,\; T\; \backslash in\; \backslash mathcal\{P\}$. The statement that a graph $G$ has a regularity partition is equivalent to saying that its associated graphon $W\_G$ is close to a step function.

The proof of compactness requires only the weak regularity lemma:

Weak Regularity Lemma for Graphons. For every graphon $W$ and $\backslash varepsilon\; >\; 0$, there is a step function $W\text{'}$ with at most $\backslash lceil\; 4^\{1/\backslash varepsilon^2\}\; \backslash rceil$ steps such that $\backslash lVert\; W\; -\; W\text{'}\; \backslash rVert\_\backslash square\; \backslash le\; \backslash varepsilon$.

but it can be used to prove stronger regularity results, such as the strong regularity lemma:

Strong Regularity Lemma for Graphons. For every sequence $\backslash mathbf\{\backslash varepsilon\}\; =\; (\backslash varepsilon\_0,\; \backslash varepsilon\_1,\; \backslash dots)$ of positive real numbers, there is a positive integer $S$ such that for every graphon $W$, there is a graphon $W\text{'}$ and a step function $U$ with steps such that $\backslash lVert\; W\; -\; W\text{'}\; \backslash rVert\_1\; \backslash le\; \backslash varepsilon\_0$ and $\backslash lVert\; W\text{'}\; -\; U\; \backslash rVert\_\backslash square\; \backslash le\; \backslash varepsilon\_k.$

The proof of the strong regularity lemma is similar in concept to Corollary 1 above. It turns out that every graphon $W$ can be approximated with a step function $U$ in the $L\_1$ norm, showing that the set of balls $B\_1(U,\; \backslash varepsilon\_0)$ cover $\backslash widetilde\{\backslash mathcal\{W\}\}\_0$. These sets are not open in the $\backslash delta\_\backslash square$ metric, but they can be enlarged slightly to be open. Now, we can take a finite subcover, and one can show that the desired condition follows.

{{Main|Sidorenko's conjecture}}

The analytic nature of graphons allows greater flexibility in attacking inequalities related to homomorphisms.

For example, Sidorenko's conjecture is a major open problem in extremal graph theory, which asserts that for any graph $G$ on $n$ vertices with average degree $pn$ (for some $p\backslash in\; [0,1]$) and bipartite graph $H$ on $v$ vertices and $e$ edges, the number of homomorphisms from $H$ to $G$ is at least $p^\{e\}n^\{v\}$.{{r|sidorenko}}

Since this quantity is the expected number of labeled subgraphs of $H$ in a random graph $G(n,p)$,

the conjecture can be interpreted as the claim

that for any bipartite graph $H$, the random graph achieves (in expectation) the minimum number of copies of $H$ over all graphs with some fixed edge density.

Many approaches to Sidorenko's conjecture formulate the problem as an integral inequality on graphons, which then allows the problem to be attacked using other analytical approaches. {{r|norms}}

Graphons are naturally associated with dense simple graphs. There are extensions of this model to dense directed weighted graphs, often referred to as decorated graphons.{{r|decorate}} There are also recent extensions to the sparse graph regime, from both the perspective of random graph models and graph limit theory.

{{cite journal

| last1 = Chung | first1 = Fan R. K. | author1-link = Fan Chung

| author2-link = Ronald Graham | last2 = Graham | first2 = Ronald L.

| last3 = Wilson | first3 = R. M.

| title = Quasi-random graphs

| journal = Combinatorica

| year = 1989

| volume = 9

| issue = 4

| pages = 345–362

| doi = 10.1007/BF02125347 | doi-access = free }}

{{cite book

|last1 = Haupt |first1 = Andreas

|last2 = Schultz |first2 = Thomas

|first3 = Mohammed |last3 = Khatami

|first4 = Ngoc |last4 = Tran

|title = Advances in Mathematical Sciences

|editor-first1 = Bahar |editor-last1 = Acu

|editor-first2 = Donatella | editor-last2 = Danialli

|editor-first3 = Marta | editor-last3 = Lewicka

| editor-first4 = Arati | editor-last4 = Pati

| editor-first5 = Saraswathy |editor-last5 = RV

|editor-first6 = Miranda |editor-last6 = Teboh-Ewungkem

|series = Association for Women in Mathematics Series

|volume = 21

|chapter = Classification on Large Networks: A Quantitative Bound via Motifs and Graphons (Research)

|publisher = Springer, Cham

|doi = 10.1007/978-3-030-42687-3_7 |doi-access=free

|isbn = 978-3-030-42687-3

|date = July 17, 2020

|pages = 107–126

| arxiv = 1710.08878 }}

{{cite journal

| last1 = Hatami | first1 = H.

| title = Graph norms and Sidorenko's conjecture

| journal = Israel Journal of Mathematics

| year = 2010

| volume = 175

| issue = 1

| pages = 125–150

| doi = 10.1007/s11856-010-0005-1 | doi-access = | arxiv = 0806.0047 }}

{{cite journal

| last1 = Sidorenko | first1 = A. | author1-link = Alexander Sidorenko

| title = A correlation inequality for bipartite graphs

| journal = Graphs and Combinatorics

| year = 1993

| volume = 9

| issue = 2–4

| pages = 201–204

| doi = 10.1007/BF02988307 | doi-access =}}

{{cite journal

| last1 = Glasscock | first1 = D.

| title = What is a graphon

| journal = Notices of the American Mathematical Society

| year = 2015

| volume = 62

| issue = 1

| pages = 46–48

| arxiv = 1611.00718}}

{{Cite arXiv| last1 = Veitch| first1 = V.| last2 = Roy| first2 = D. M.| title = The Class of Random Graphs Arising from Exchangeable Random Measures |eprint=1512.03099| class = math.ST| year = 2015}}

{{Cite journal| last1 = Borgs| first1 = C.| last2 = Chayes| first2 = J. T.| last3 = Cohn| first3 = H.| last4 = Zhao| first4 = Y.| title = An L^p theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions | journal = Transactions of the American Mathematical Society| volume = 372| issue = 5| pages = 3019–3062|arxiv=1401.2906 | year = 2019| doi = 10.1090/tran/7543| s2cid = 50704206}}

{{Cite journal| last1 = Borgs| first1 = C.| last2 = Chayes| first2 = J. T.| last3 = Cohn| first3 = H.| last4 = Zhao| first4 = Y.| title = An L^p theory of sparse graph convergence II: LD convergence, quotients, and right convergence | journal = The Annals of Probability| volume = 46| issue = 2018| pages = 337–396|arxiv=1408.0744| year = 2018| doi = 10.1214/17-AOP1187| s2cid = 51786393}}

{{Cite book| publisher = American Mathematical Society| last = Lovász| first = L.| title = Large Networks and Graph Limits}}

{{Cite journal| volume = 37| issue = 2| pages = 437–461| last1 = Orbanz| first1 = P.| last2 = Roy| first2 = D.M.| title = Bayesian Models of Graphs, Arrays and Other Exchangeable Random Structures| journal = IEEE Transactions on Pattern Analysis and Machine Intelligence| doi=10.1109/tpami.2014.2334607| pmid = 26353253| arxiv = 1312.7857| year = 2015| s2cid = 566759}}

Category:Graph theory

Category:Probability theory