Uniform linear embeddings of graphons

DOI10.1016/J.EJC.2016.09.004zbMATH Open1352.05163arXiv1507.04389OpenAlexW2963586314MaRDI QIDQ730252FDOQ730252

Jeannette Janssen, Mahya Ghandehari, H. Chuangpishit

Publication date: 27 December 2016

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

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.

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

Recommendations

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

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)

Cites Work

• Limits of dense graph sequences
• Title not available (Why is that?)
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Linear embeddings of graphs and graph limits
• Uniform linear embeddings of spatial random graphs
• Limits of randomly grown graph sequences

Cited In (6)

• Uniform embeddings for Robinson similarity matrices
• An Optimization Parameter for Seriation of Noisy Data
• Linear embeddings of simple graphs in \(\mathbb R^{3}\)
• Reconstruction of line-embeddings of graphons
• Uniform linear embeddings of spatial random graphs
• Symmetric Measures, Continuous Networks, and Dynamics

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)