On measure concentration in graph products
Articles
Matas Šileikis
Institute of Mathematics and Informatics
Published 2009-12-20
https://doi.org/10.15388/LMR.2009.78
PDF

Keywords

graph product
discrete isoperimetric inequalities
concentration of measure
sums of independent random variables
tail probabilities
large deviations

How to Cite

Šileikis M. (2009) “On measure concentration in graph products”, Lietuvos matematikos rinkinys, 50(proc. LMS), pp. 443–448. doi: 10.15388/LMR.2009.78.

Abstract

Bollobás and Leader [1] showed that among the n-fold products of connected graphs of order k the one with minimal t-boundary is the grid graph. Given any product graph G and a set A of its vertices that contains at least half of V (G), the number of vertices at a distance at least t from A decays (as t grows) at a rate dominated by P(X1 + . . . + X\geq   t) where Xi are some simple i.i.d. random variables. Bollobás and Leader used the moment generating function to get an exponentialbound for this probability. We insert a missing factor in the estimate by using a somewhat more subtle technique (cf. [3]).

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Please read the Copyright Notice in Journal Policy