Energy of convex sets, shortest paths, and resistance

Authors
Citation
L. Lovasz, Energy of convex sets, shortest paths, and resistance, J COMB TH A, 94(2), 2001, pp. 363-382
Citations number
12
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES A
ISSN journal
0097-3165 → ACNP
Volume
94
Issue
2
Year of publication
2001
Pages
363 - 382
Database
ISI
SICI code
0097-3165(200105)94:2<363:EOCSSP>2.0.ZU;2-A
Abstract
Let us assign independent. exponentially distributed random edge lengths to the edges of an undirected graph. Lyons. Pemantle, and Peres ( 1999, J. Co mbin. Theory Ser. A 86 (1999). 158-168) proved that the expected length of the shortest path between two given nodes is bounded from below by the resi stance between these nodes. where the resistance of an edge is the expectat ion of its length. They remarked that instead or exponentially distributed variables, one could consider random variables with a log-concave rail. We generalize this result in two directions. First. we note that the variables do not have to be independent: it suffices to assume that their joint dist ribution is log-concave. Second. the inequality can be formulated as follow s: the expected length of a shortest path between two given nodes is the ex pected optimum of a stochastic linear program over a flow polytope. while t he resistance is the minimum of a convex quadratic function over this polyt ope. We show that the inequality between these quantities holds true for an arbitrary polytope provided its blocker has integral vertices. (C) 2001 Ac ademic Press.