Graphon model for random graphs and almost surely dense graphs

151 Views Asked by At

Consider the random graph generating process from a graphon.

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.

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

But what if I define $W(x,y)=10^{-6}\ \forall (x,y)\in[0,1]^2$? I don't see why this would produce dense graphs almost surely.

1

There are 1 best solutions below

3
On BEST ANSWER

Dense graphs are graphs with $\Theta(n^2)$ edges. Graphs sampled from your graphon have $10^{-6} \binom n2$ edges in expectation (and the number of edges is highly concentrated around this mean). That's still $\Theta(n^2)$.