Uniform linear embeddings of graphons

Let w:[0,1]2→[0,1] be a symmetric function, and consider the random process G(n,w), where vertices are chosen from [0,1] uniformly at random, and w governs the edge formation probability. Such a random graph is said to have a linear embedding, if the probability of linking to a particular vertex v decreases with distance. The rate of decrease, in general, depends on the particular vertex v. A linear embedding is called uniform if the probability of a link between two vertices depends only on the distance between them. In this article, we consider the question whether it is possible to “transform” a linear embedding to a uniform one, through replacing the uniform probability space [0,1] with a suitable probability space on R. We give necessary and sufficient conditions for the existence of a uniform linear embedding for random graphs where w attains only a finite number of values. Our findings show that for a general w the answer is negative in most cases.