Mathematics – Combinatorics
Scientific paper
2008-07-10
Mathematics
Combinatorics
Scientific paper
The logarithmic Sobolev inequality for the Hamming cube {0,1}^n states that for any real-valued function f on the cube holds E(f,f) \ge 2 Ent(f^2), where E(f,f) is the appropriate Dirichlet form (also known as "sum of influences"). We show that the constant C = 2 at the right hand side of this inequality can be replaced by a function C(rho) depending on rho = Ent(f^2) / (n Ef^2). The function C is an increasing convex function taking [0,log 2] to [2, 2/log 2]. We present some applications of this modified inequality. In particular, it is used to obtain a discrete version of the Faber-Krahn inequality for small subsets of the Hamming cube, answering a question of Friedman and Tillich. We introduce, following the approach of Friedman and Tillich, the notion of a fractional edge-boundary size of a subset of {0,1}^n, and show Hamming balls of radius at most n/2 - O(n^{3/4}) to be sets with (asymptotically) the smallest fractional edge-boundary for their size.
No associations
LandOfFree
A modified logarithmic Sobolev inequality for the Hamming cube and some applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A modified logarithmic Sobolev inequality for the Hamming cube and some applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A modified logarithmic Sobolev inequality for the Hamming cube and some applications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-459907