0
$\begingroup$

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.

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

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.

$\endgroup$
3
  • $\begingroup$ What will happen if your assumptions are not true? Suppose a graphon W(x, y) = 1 (x < 1/2 and y < 1/2), 0 (otherwise). $\endgroup$ Dec 29 '20 at 13:37
  • $\begingroup$ 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$. $\endgroup$ Dec 29 '20 at 15:44
  • $\begingroup$ I understand. Thanks a lot! $\endgroup$ Dec 29 '20 at 17:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.