Uniform linear embeddings of graphons

DOI10.1016/J.EJC.2016.09.004MaRDI QIDQ730252zbMATH OpenOpenAlexFDO

Authors H. Chuangpishit, Mahya Ghandehari, Jeannette Janssen

Publication date 27 December 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

uniform linear embedding for random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Symmetric functions and generalizations (05E05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Let $w:[0,1{]}^{2}ightarrow[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 $mathbbR$. 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.

Recommendations

• Uniform linear embeddings of spatial random graphs
• Linear embeddings of graphs and graph limits
• scientific article; zbMATH DE number 178977
• On embedding random graphs into distance graphs and graphs of diameters in Euclidean spaces
• Recovering the structure of random linear graphs

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
• Large networks and graph limits
• Limits of dense graph sequences
• Limits of randomly grown graph sequences
• Linear embeddings of graphs and graph limits
• Uniform linear embeddings of spatial random graphs

Cited in

(7)

• Symmetric measures, continuous networks, and dynamics
• Uniform embeddings for Robinson similarity matrices
• Linear embeddings of graphs and graph limits
• Reconstruction of line-embeddings of graphons
• An optimization parameter for seriation of noisy data
• Linear embeddings of simple graphs in \(\mathbb R^{3}\)
• Uniform linear embeddings of spatial random graphs

This page was built for publication: Uniform linear embeddings of graphons

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