Logconcave random graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Logconcave random graphs

Full text

Pdf (274 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 40th annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

SESSION: 16B table of contents

Pages 779-788

Year of Publication: 2008

ISBN:978-1-60558-047-0

Authors

Alan Frieze	Carnegie Mellon University, Pittsburgh, USA
Santosh Vempala	Georgia Tech., Atlanta, USA
Juan Vera	University of Waterloo, Waterloo, Canada

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 69, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1374376.1374487 What is a DOI?

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 ij with 1 ≤ i,j ≤ 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 ≤ p. The standard Erdos-Renyi model is the special case when F is uniform on the 0-1 unit cube. We determine 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	K. Ball: Normed spaces with a weak Gordon-Lewis property, Functional Analysis: Proc. of the Seminar at UT Austin, Lecture Notes in Mathematics 1470 (1987-89), 36--47.
	2	B. Bollobás: Random Graphs, Academic Press, 1985
	3	A. Dinghas: Über eine Klasse superadditiver Mengenfunktionale vonBrunn-Minkowski-Lusternik-schem Typus, Math. Zeitschr. 68 (1957), 111--125.
	4	Devdatt Dubhashi , Desh Ranjan, Balls and bins: a study in negative dependence, Random Structures & Algorithms, v.13 n.2, p.99-124, Sept. 1998 [doi>10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M]
	5	P. Erdös and A. Rényi: On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960) 17--61.
	6	A. Frieze: On the value of a random minimum spanning tree problem, Discrete Applied Mathemaics 10 (1985) 47 -- 56.
	7	Alan Frieze , Colin McDiarmid, Algorithmic theory of random graphs, Random Structures & Algorithms, v.10 n.1-2, p.5-42, Jan.–March 1997 [doi>10.1002/(SICI)1098-2418(199701/03)10:1/2<5::AID-RSA2>3.0.CO;2-Z]
	8	D. Hefeta, M. Krivelevich and T. Szábo, Hamilton cycles in highly connected and expanding graphs, to appear.
	9	Janson, T. Ł uczak and A Rucinski: Random Graphs, Wiley-Interscience, 2000
	10	R. Kannan, L. Lovász and M. Simonovits, Isoperimetric Problems for Convex Bodiesand a Localisation Lemma, Discrete and Computational Geometry 13 (1995) 541--559.
	11	R.M. Karp, Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane, Mathematics of Operations Research, Mathematics of Operations Research 2 (1977) 209-24.
	12	R.M. Karp and J.M. Steele, Probabilistic analysis of heuristics, in The traveling salesmanproblem: a guided tour of combinatorial optimization,E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys Eds.(1985) 181--206.
	13	L. Leindler: On a certain converse of Hölder's Inequality II, Acta Sci. Math. Szeged 33 (1972), 217--223.
	14	László Lovász , Santosh Vempala, The geometry of logconcave functions and sampling algorithms, Random Structures & Algorithms, v.30 n.3, p.307-358, May 2007 [doi>10.1002/rsa.v30:3]
	15	Laszlo Lovasz , Santosh Vempala, Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.57-68, October 21-24, 2006 [doi>10.1109/FOCS.2006.28]
	16	V. D. Milman and A. Pajor: Isotropic position and inertia ellipsoids and zonoids of the unit ball of a normed n-dimensional space, Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics 1376 (1987-88), 64-104.
	17	A. Prékopa: Logarithmic concave measures and functions, ActaSci. Math. Szeged 34 (1973), 335--343.
	18	A. Prékopa: On logarithmic concave measures with applications tostochasic programming, Acta Sci. Math. Szeged 32 (1973),301--316.
	19	Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]