2015/07/15 by Chuangpishit, Huda, Ghandehari, Mahya, Janssen, Jeannette
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1507.04389
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 \mathbb 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.