Results 171 - 180 of 24649
Isoperimetric inequalities on the Boolean hypercube play a fundamental role in the analysis of Boolean functions and have broad applications in probability theory, combinatorics, and theoretical computer science. These inequalities have been established primarily for the uniform measure and for biased product measures, using Fourier-analytic or inductive arguments. In this talk, we extend the Kahn–Kalai–Linial inequality, Talagrand’s L^1–L^2 and variance–surface-area inequalities, and the Eldan–Gross inequality to weakly dependent measures. We show that a Dobrushin-type condition implies all four inequalities. In particular, our results apply to Ising models whose interaction matrix has 1-norm less than 1. Our approach uses a semigroup framework based on discrete Bakry–Émery theory and gradient estimates. Joint work with Zejia Chen and Xinyuan Zhang.
Strong spatial mixing (SSM) is an important quantitative notion of correlation decay that has been surprisingly challenging to establish for many natural Gibbs distributions. Notably, it has been long conjectured that random $q$-colorings on $\Delta$-regular trees exhibit SSM whenever $q ≥ \Delta + 1$. We establish that for any $\Delta \ge 3$, SSM holds for random $q$-colorings on trees of maximum degree $\Delta$ whenever $q ≥ \Delta + 3$. Using this, we also establish optimal Glauber mixing for fixed $\Delta$ and $q ≥ \Delta + 3$ when the girth of the underlying graph is sufficiently large as a function of $\Delta$.
We study a refinement of the product replacement algorithm that is designed to output individual elements of a finite group $G$ in a random way. We show after how many steps, the distribution of the output is close to uniform on $G$. The proof proceeds via spectral gap estimates and uses computer assisted calculations. This is a joint work with Michał Marcinkowski.
The curvature of a graph is basically a measure of local geometry, with albeit too many different definitions. Here we will focus on how the discrete curvature, as a locally defined invariant, has nontrivial global consequences ---- through its relations with eigenvalues, eigenvectors, edge expansions, optimal transport and clustering effects of graphs.