CSM

Seminar

Lipschitz functions on graphs

McDiarmid, C (Oxford)
Wednesday 25 June 2008, 16:20-17:00

Meeting Room 3, CMS

Abstract

Let G be a connected graph. A real vector x indexed by the vertices is called Lipschitz if the values on the ends of each edge differ by at most 1. Given a suitable function f(x) we are interested in the maximum value of f(x-\bar{x}) over all Lipschitz x. This maximum value f^*(G) is related to certain isoperimetric inequalities.