Why a graph generated from a graphon is said to be dense?

Question

Now, I'm studying about a Graphon proposed by Lovasz. Why a graph generated by a graphon is said to be dense? I cannot image this.

Answer 1

An $n$-vertex graph is dense in this sense if it has $m = \Theta(n^2)$ edges: if its density $m/\binom n2$ is positive. Such a graph has a constant fraction of all the positive edges it could have.

Suppose we have a graphon $W : [0,1]^2 \to [0,1]$, and let's exclude examples which are zero almost everywhere (such graphons will actually produce empty graphs almost surely). Then there is an $\epsilon>0$ such that the set $S = \{(x,y) \in [0,1]^2 : W(x,y) \ge \epsilon\}$ has positive measure $\mu(S)$.

We generate an $n$-vertex graph from this graphon by choosing values $u_1, u_2, \dots, u_n \in [0,1]$ independently and uniformly at random, and then adding edge $(i,j)$ with probability $W(u_i, u_j)$ (also independently for each $(i,j)$.) We have $$ \Pr[(i,j) \in E] = \Pr[(i,j) \in E \mid (u_i, u_j) \in S] \cdot \Pr[(u_i, u_j) \in S] \ge \epsilon \cdot \mu(S). $$ Therefore the expected number of edges in the graph is at least $\epsilon \mu(S) \binom n2$.

In fact the number of edges is tightly concentrated around the mean. We can prove this, for example, with McDiarmid's inequality: changing each $u_i$ can change the number of edges by at most $c_i = n-1$, so $$ \Pr\left[|E| \le (\epsilon \mu(S)- \delta) \binom n2 \right] \le \exp\left(\frac{2 (\delta \binom n2)^2}{\sum_{i=1}^n (n-1)^2}\right) = e^{-\delta^2 n/2}. $$ Therefore the graph has density at least $\epsilon \mu(S)-\delta$ with probability $1 - e^{-\delta n^2/2}$, which goes to $1$ as $n \to \infty$. This proves that the graph we get is dense asymptotically almost surely.