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.