Logconcave random graphs

MaRDI QIDQ986716zbMATH OpenFDO

Authors Santosh S. Vempala, Alan Frieze, Juan Vera

Publication date 12 August 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.3697, https://eudml.org/doc/224088, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r108.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Asymptotic theory of convex bodies (52A23)

Abstract: We propose the following model of a random graph on n vertices. Let F be a distribution in R_+^{n(n-1)/2} with a coordinate for every pair i$ with 1 le i,j le n. Then G_{F,p} is the distribution on graphs with n vertices obtained by picking a random point X from F and defining a graph on n vertices whose edges are pairs ij for which X_{ij} le p. The standard ErdH{o}s-R'{e}nyi model is the special case when F is uniform on the 0-1 unit cube. We examine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the X_{ij} are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

Review text

Summary: We propose the following model of a random graph on \(n\) vertices. Let \(F\) be a distribution in \(R_+^{n(n-1)/2}\) with a coordinate for every pair \(ij\) with \(1\leq i,j\leq n\). Then \(G_{F,p}\) is the distribution on graphs with \(n\) vertices obtained by picking a random point \(X\) from \(F\) and defining a graph on \(n\) vertices whose edges are pairs \(ij\) for which \(X_{ij}\leq p\). The standard Erdős-Rényi model is the special case when \(F\) is uniform on the 0-1 unit cube. We examine basic properties such as the connectivity threshold for quite general distributions. We also consider cases where the \(X_{ij}\) are the edge weights in some random instance of a combinatorial optimization problem. By choosing suitable distributions, we can capture random graphs with interesting properties such as triangle-free random graphs and weighted random graphs with bounded total weight.

Recommendations

• A note on log-concave random graphs
• The degree sequence of a random graph. I. The models
• Threshold Functions for Random Graphs on a Line Segment
• Random threshold graphs
• scientific article; zbMATH DE number 3168330

Cited in

(6)

• Uniform distributions and random variate generation over generalized \(l_p\) balls and spheres
• A note on log-concave random graphs
• scientific article; zbMATH DE number 3915378 (Why is no real title available?)
• Law of the iterated logarithm for random graphs
• The impact of edge correlations in random networks
• Graphon convergence of random cographs

This page was built for publication: Logconcave random graphs

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