# Why a graph generated from a graphon is said to be dense? [closed]

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.

• I see the word gryphon in the title, I get excited because I'm a brony... Dec 27 '20 at 4:27
• Thanks! I edited. Dec 27 '20 at 4:29
• Please edit again to add sources for "a Graphon proposed by Lovasz". Oct 17 '21 at 3:31

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.
• Sorry, I should rephrase my assumptions. I want "not (zero almost everywhere)" rather than "(not zero) almost everywhere". The graphon in your example still has $\mu(S) = \frac14$ when $\epsilon=1$. Dec 29 '20 at 15:44