Graphon
In graph theory and statistics, a graphon (also known as a graph limit) is a symmetric measurable function , that is important in the study of dense graphs. Graphons arise both as a natural notion for the limit of a sequence of dense graphs, and as the fundamental defining objects of exchangeable random graph models. Graphons are tied to dense graphs by the following pair of observations: the random graph models defined by graphons give rise to dense graphs almost surely, and, by the regularity lemma, graphons capture the structure of arbitrary large dense graphs. Statistical formulation 

A graphon is a symmetric measurable function . Usually a graphon is understood as defining an exchangeable random graph model according to the following scheme:

 Each vertex  of the graph is assigned an independent random value 
 Edge  is independently included in the graph with probability . 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  is sometimes denoted ,
by analogy with the Erdős–Rényi model of random graphs. A graph generated from a graphon  in this way is called a -random graph. It follows from this definition and the law of large numbers that, if , exchangeable random graph models are dense almost surely. Examples 

The simplest example of a graphon is  for some constant . In this case the associated exchangeable random graph model is the Erdős–Rényi model  that includes each edge independently with probability . If we instead start with a graphon that is piecewise constant by:

 dividing the unit square into  blocks, and
 setting  equal to  on the  block,
 
the resulting exchangeable random graph model is the  
community stochastic block model, a generalization of the Erdős–Rényi model. We can interpret this as a random graph model consisting of  distinct Erdős–Rényi graphs with parameters  respectively, with bigraphs between them where each possible edge between blocks  and  is included independently with probability . 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. Jointly exchangeable adjacency matrices 

A random graph of size  can be represented as a random  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  sub-matrices of some infinite array of random variables; this allows us to generate  by adding a node to  and sampling the edges  for . With this perspective, random graphs are defined as random infinite symmetric arrays . 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

 

for all permutations  of the natural numbers, where  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  is generated by:

 Sample  independently
  independently at random with probability 

where  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. Graphon estimation 
Due to identifiability issues, it is impossible to estimate either the graphon function  or the node latent positions  and there are two main directions of graphon estimation. One direction aims at estimating up to an equivalence class, or estimate the probability matrix induced by . Analytic formulation 
Any graph on  vertices  can be identified with its adjacency matrix . This matrix corresponds to a stepfunction ,
defined by partitioning  into intervals 
 such that  has interior

and for each , setting  equal to the 

entry of . This function  is the associated graphon of the graph . In general, if we have a sequence of graphs  where the number of vertices of  goes to infinity, we can analyze the
limiting behavior of the sequence by considering the limiting behavior of the functions . 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  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. Examples

Constant graphon 
Take a sequence of  Erdős–Rényi random graphs  with some fixed parameter . Intuitively, as  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 , which captures the above intuition. Half graphon 
Take the sequence  of half-graphs, defined by taking  to be the bipartite graph on  vertices  and  such that  is adjacent to  precisely when . If the vertices are listed in the presented order, then
the adjacency matrix  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  is given by

As  gets large, these corners of ones "smooth" out. Matching this intuition, the sequence  converges to the half-graphon  defined by  when  and  otherwise. Complete bipartite graphon 
Take the sequence  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  looks like a block off-diagonal matrix, with two blocks of ones and two blocks of zeros. For example, the adjacency matrix of  is given by

As  gets larger, this block structure of the adjacency matrix remains constant, 
so that this sequence of graphs converges to a "complete bipartite" graphon 
defined by  whenever  and , and setting  otherwise. If we instead order the vertices of  by alternating between parts,
the adjacency matrix has a chessboard structure of zeros and ones. For example, under this ordering, the adjacency matrix of  is given by

 

As  gets larger, 
the adjacency matrices become a finer and finer chessboard. Despite this behavior, we still want the limit of  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. Limit of W-random graphs 
Take a random sequence  of  -random graphs by drawing  for some fixed graphon . Then just like in the first example from this section, it turns out that  converges to  almost surely. Recovering graph parameters from graphons 

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

This is because  is -valued, and each edge 
in  
corresponds to a region 
of area  where  equals . Similar reasoning shows that the number of triangles in  is equal to

Notions of convergence 

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  for some fixed , the distance between these two graphs under a "reasonable" metric should be close to zero with high probability for large . 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  have an expected (normalized) edit distance of . 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. Homomorphism densities 

One way to measure the distance between two graphs  and  is to compare their relative subgraph counts. That is, for each graph  we can compare the number of copies of  in  and  in . If these numbers are close for every graph , then
intuitively  and  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  and , the 
homomorphism density  of  in  is defined to be the number of  graph homomorphisms from  to . In other words,  is the probability a randomly chosen map from the vertices of  to the vertices of  sends adjacent vertices in  to adjacent vertices in . Graphons offer a simple way to compute homomorphism densities. Indeed, given a graph  with associated graphon  and another , we have

where the integral is multidimensional, taken over the unit hypercube . This follows from the definition of an associated graphon, by considering when the above integrand is equal to . We can then extend the definition of homomorphism density to arbitrary graphons , by using the same integral and defining 

for any graph . Given this setup, we say a sequence of graphs  is left-convergent if for every fixed graph , the sequence of homomorphism densities  converges. Although not evident from the definition alone, if   converges in this sense, then there always exists a graphon  such that for every graph , we have

simultaneously. Cut distance 
Take two graphs  and  on the same vertex set. Because these graphs share the same vertices,
one way to measure their distance is to restrict to subsets  of the vertex set, and for each such pair subsets compare the number of edges  from  to  in  to the number of edges  between  and  in . If these numbers are similar for every pair of subsets (relative to the total number of vertices), then that suggests  and  are similar graphs. As a preliminary formalization of this notion of distance, for any pair of graphs  and  on the same vertex set  of size , define the labeled cut distance between  and  to be

In other words, the labeled cut distance encodes the maximum discrepancy of the edge densities between  and . We can generalize this concept to graphons by expressing the edge density  in terms of the associated graphon , giving the equality

where  are unions of intervals corresponding to the vertices in  and . 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 , define the cut norm of  to be the quantity

taken over all measurable subsets  of the unit interval. This captures our earlier notion of labeled cut distance, as we have the equality . 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  and , define their cut distance to be

where  is the composition of  with the map , and the infimum is taken over all  measure-preserving bijections from the unit interval to itself. 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  is convergent under the cut distance if it is a  Cauchy sequence under the cut distance . Although not a direct consequence of the definition, if such a sequence of graphs is Cauchy, then it always converges to some graphon . Equivalence of convergence 

As it turns out, for any sequence of graphs , left-convergence is equivalent to convergence under the cut distance, and furthermore, the limit graphon  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. Counting Lemma. For any pair of graphons  and , we have

for all graphs . The name "counting lemma" comes from the bounds that this lemma gives on homomorphism densities , 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 , there exist a real number  and a positive integer  such that for any pair of graphons  and  with

for all graphs  satisfying ,
we must have . This lemma shows that left-convergence implies convergence under the cut distance. The space of graphons 
We can make the cut-distance into a metric by taking the set of all graphons and  identifying two graphons  whenever . The resulting space of graphons is denoted , and together with  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 , there is an integer  such that for every graphon , there is a graph  with at most  vertices such that . To see why, let  be the set of graphs. Consider for each graph  the open ball  containing all graphons  such that . The set of open balls for all graphs covers , so compactness implies that there is a finite subcover  for some finite subset . We can now take  to be the largest number of vertices among the graphs in . Applications

Regularity lemma 

Compactness of the space of graphons  can be thought of as an analytic formulation of  Szemerédi's regularity lemma; in fact, a stronger result than the original lemma. Szemeredi's regularity lemma can be translated into the language of graphons as follows. Define a stepfunction to be a graphon  that is piecewise constant, i.e. for some partition  of ,  is constant on  for all . The statement that a graph  has a regularity partition is equivalent to saying that its associated graphon  is close to a stepfunction. The proof of compactness requires only the  weak regularity lemma:

Weak Regularity Lemma for Graphons. For every graphon  and , there is a stepfunction  with at most  steps such that . but it can be used to prove stronger regularity results, such as the  strong regularity lemma:

Strong Regularity Lemma for Graphons. For every sequence  of positive real numbers, there is a positive integer  such that for every graphon , there is a graphon  and a stepfunction  with  steps such that  and 

The proof of the strong regularity lemma is similar in concept to Corollary 1 above. It turns out that every graphon  can be approximated with a stepfunction  in the   norm, showing that the set of balls  cover . These sets are not open in the  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. 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  on  vertices with average degree  (for some ) and bipartite graph  on  vertices and  edges, the number of  homomorphisms from  to  is at least . Since this is quantity is the expected number of labeled subgraphs of  in a random graph ,
the conjecture can be interpreted as the claim 
that for any bipartite graph , the random graph achieves (in expectation) the minimum number of copies of  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. Generalizations 

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. There are also recent extensions to the sparse graph regime, from both the perspective of random graph models  and graph limit theory. References 

Graph theory
Probability theory