Isoperimetric and related constants for graphs and Markov chains.

摘要

Let (X, p ) be a probability space equipped with a kernel K : X x X → R +. For example, K is the transition matrix of a finite Markov chain or the adjacency matrix of a finite connected graph.; In this thesis we use functional-analytic methods to study discrete isoperimetric inequalities of the form p+A≥ cIpA ,A⊂X,c0, connecting suitably defined "surface" measures p +(A) and "volumes" p (A) via some non-negative functions I on [0,1]. The constant c is usually referred to as an isoperimetric constant. When estimating the isoperimetric constants, various functional constants appear naturally. These include the spectral gap, the log-Sobolev constant and others, not defined previously. Special attention is given to Cartesian products of Markov chains and graphs.