Linear embeddings of graphs and graph limits

DOI10.1016/J.JCTB.2015.02.002MaRDI QIDQ2347848zbMATH OpenOpenAlexFDO

Authors H. Chuangpishit, Mahya Ghandehari, Matthew Hurshman, Nauzer Kalyaniwalla, Jeannette Janssen

Publication date 10 June 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4451

zbMATH Keywords

graph limitsinterval graphslinear embeddingrandom graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80)

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 $Gamm{a}^{\ast }$, which aims to measure the similarity of the graph to an instance of a random graph with a linear embedding. For a graph $G$, $Gamm{a}^{\ast }(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 $Gamm{a}^{\ast }$ 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 $Gamm{a}^{\ast }(G_n)$ converges as well. Moreover, there exists a function $w^{\ast }$ arbitrarily close to $w$ under the box distance, so that $li{m}_{nightarrowinfty}Gamm{a}^{\ast }(G_n)$ is arbitrarily close to $Gamma(w^{\ast })$.

Recommendations

• Uniform linear embeddings of graphons
• Interval graph limits
• On limits of sparse random graphs
• Limits of dense graph sequences
• Graph limits and parameter testing

Cites work

• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• From quasirandom graphs to graph limits and graphlets
• Graph limits and exchangeable random graphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Interval graph limits
• Large networks and graph limits
• Latent Space Approaches to Social Network Analysis
• Limits of dense graph sequences
• Limits of randomly grown graph sequences
• Metrics for sparse graphs
• Moments of two-variable functions and the uniqueness of graph limits
• Quick approximation to matrices and applications
• Random Geometric Graphs
• Regularity partitions and the topology of graphons
• Szemerédi's lemma for the analyst
• The cut metric, random graphs, and branching processes
• The phase transition in inhomogeneous random graphs
• The Roberts characterization of proper and unit interval graphs
• Threshold graph limits and random threshold graphs
• Unit disk graphs

Cited in

(15)

• Limits of iterated \(H\)-line graphs
• On a straight-line embedding problem of graphs
• Interval graph limits
• Reconstruction of line-embeddings of graphons
• Cut norm discontinuity of triangular truncation of graphons
• Linking number and writhe in random linear embeddings of graphs
• Uniform linear embeddings of spatial random graphs
• scientific article; zbMATH DE number 4160754 (Why is no real title available?)
• (Nearly-)tight bounds on the contiguity and linearity of cographs
• An optimization parameter for seriation of noisy data
• Graph sequences sampled from Robinson graphons
• Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
• Uniform linear embeddings of graphons
• General theoretical results on rectilinear embeddability of graphs
• Linear embeddings of simple graphs in \(\mathbb R^{3}\)

This page was built for publication: Linear embeddings of graphs and graph limits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347848)