Uniform linear embeddings of graphons

详细信息    查看全文

• 作者：Huda Chuangpishit^a ; Mahya Ghandehari^b ; Jeannette Janssen^a ; ^{Jeannette.Janssen@dal.ca}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：61
• 期：Complete
• 页码：47-68
• 全文大小：532 K
• 卷排序：61

文摘

Let w:[0,1]2→[0,1]w:[0,1]2→[0,1] be a symmetric function, and consider the random process G(n,w)G(n,w), where vertices are chosen from [0,1][0,1] uniformly at random, and ww 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 vv decreases with distance. The rate of decrease, in general, depends on the particular vertex vv. 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][0,1] with a suitable probability space on RR. We give necessary and sufficient conditions for the existence of a uniform linear embedding for random graphs where ww attains only a finite number of values. Our findings show that for a general ww the answer is negative in most cases.