Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:Logconcave Random Graphs. | Logconcave Random Graphs Alan Frieze Santosh VempaW Department of Mathematical Sciences School of Computer Science Carnegie Mellon University Georgia Tech Pittsburgh PA15213 Atlanta GA 30332 alan@ vempala@ Juan Vera Department of Management Sciences University of Waterloo Waterloo ON N2L 3G1 Canada jvera@ Submitted Feb 15 2010 Accepted Jun 23 2010 Published Aug 9 2010 Mathematics Subject Classification 05C80 52A23 Abstract We propose the following model of a random graph on n vertices. Let F be a distribution in R n 1 2 with a coordinate for every pair ij with 1 i j n. Then Gp 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 Xj p. The standard Erdos-Renyi 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 Xj 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. 1 Introduction Probabilistic combinatorics is today a thriving field bridging the classical area of probability with modern developments in combinatorics. The theory of random graphs pioneered Research supported in part by NSF award CCF-0502793. 1 Supported in part by NSF award CCF-0721503. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R108 1 by Erdos-Renyi 7 has given us numerous insights surprises and techniques and has been used to count to establish structural properties and to analyze algorithms. In the standard unweighted model Gn p each pair of vertices ij of an n-vertex graph is independently declared to be an edge with probability p. Equivalently one picks a random number Xij for each ij in .
