Name
Abstract | ||
|---|---|---|
Consider a random graph process where vertices are chosen from the interval 0 , 1 ] , and edges are chosen independently at random, but so that, for a given vertex x, the probability that there is an edge to a vertex y decreases as the distance between x and y increases. We call this a random graph with a linear embedding.We define a new graph parameter * , which aims to measure the similarity of the graph to an instance of a random graph with a linear embedding. For a graph G, * ( G ) = 0 if and only if G is a unit interval graph, and thus a deterministic example of a graph with a linear embedding.We show that the behaviour of * is consistent with the notion of convergence as defined in the theory of dense graph limits. In this theory, graph sequences converge to a symmetric, measurable function on 0 , 1 ] 2 . We define an operator which applies to graph limits, and which assumes the value zero precisely for graph limits that have a linear embedding. We show that, if a graph sequence { G n } converges to a function w, then { * ( G n ) } converges as well. Moreover, there exists a function w * arbitrarily close to w under the box distance, so that lim n ∞ * ( G n ) is arbitrarily close to ( w * ) . |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jctb.2015.02.002 | Journal of Combinatorial Theory Series B |
Keywords | DocType | Volume |
random graphs | Journal | 113 |
Issue | ISSN | Citations |
C | J. Combin. Th. B 113, July 2015, pp.162-184 | 1 |
PageRank | References | Authors |
0.48 | 12 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Huda Chuangpishit | 1 | 1 | 1.50 |
| Mahya Ghandehari | 2 | 21 | 3.43 |
| Matt Hurshman | 3 | 23 | 1.48 |
| Jeannette Janssen | 4 | 295 | 32.23 |
| Nauzer Kalyaniwalla | 5 | 31 | 2.68 |