Energy of Convex Sets, Shortest Paths, and Resistance

✍ Scribed by László Lovász

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 152 KB
• Volume: 94
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.2000.3153

✦ Synopsis

Let us assign independent, exponentially distributed random edge lengths to the edges of an undirected graph. Lyons, Pemantle, and Peres (1999, J. Combin. 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 resistance between these nodes, where the resistance of an edge is the expectation of its length. They remarked that instead of exponentially distributed variables, one could consider random variables with a log-concave tail. 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 distribution is log-concave. Second, the inequality can be formulated as follows: the expected length of a shortest path between two given nodes is the expected optimum of a stochastic linear program over a flow polytope, while the resistance is the minimum of a convex quadratic function over this polytope. We show that the inequality between these quantities holds true for an arbitrary polytope provided its blocker has integral vertices.