Home OALib Journal OALib PrePrints Submit Ranking News My Lib FAQ About Us Follow Us+ All Title Author Keywords Abstract
 Publish in OALib Journal ISSN: 2333-9721 APC: Only $99  Views Downloads  Relative Articles Linking number and writhe in random linear embeddings of graphs Threshold graph limits and random threshold graphs Monotone graph limits and quasimonotone graphs Graph limits and exchangeable random graphs Sparse graph limits, entropy maximization and transitive graphs An example of graph limits of growing sequences of random graphs The nonlinear heat equation on dense graphs and graph limits Quasi-random graphs and graph limits From Quasirandom graphs to Graph Limits and Graphlets Graph Isomorphism for Bounded Genus Graphs In Linear Time More... # Linear embeddings of graphs and graph limits  Full-Text Cite this paper 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$\Gamma^*$, which aims to measure the similarity of the graph to an instance of a random graph with a linear embedding. For a graph$G$,$\Gamma^*(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$\Gamma^*$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$\Gamma$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$\{ \Gamma^*(G_n)\}$converges as well. Moreover, there exists a function$w^*$arbitrarily close to$w$under the box distance, so that$\lim_{n\rightarrow \infty}\Gamma^*(G_n)$is arbitrarily close to$\Gamma (w^*)\$.

Full-Text 