Logconcave random graphs

zbMATH Open1193.05145arXiv0901.3697MaRDI QIDQ986716FDOQ986716

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)

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.

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

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

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

Mathematics Subject Classification ID

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

Cited In (6)

• The impact of edge correlations in random networks
• A note on log-concave random graphs
• Uniform distributions and random variate generation over generalized \(l_p\) balls and spheres
• Law of the iterated logarithm for random graphs
• Title not available (Why is that?)
• 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)