Talagrand-Type Correlation Inequalities for Submodular and Supermodular Functions on the Hypercube
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916021862924288 |
|---|---|
| author | Chang, Fan Chen, Yu |
| author_facet | Chang, Fan Chen, Yu |
| contents | Talagran's correlation inequality provides quantitative lower bounds on the covariance of two increasing Boolean functions in terms of their coordinate influences, but, in general, a logarithmic loss is necessary. Motivated by a question of Kalai, Keller and Mossel, we identify a natural log-free regime. We prove that if two increasing Boolean functions on $\{0,1\}^n$ are either both submodular or both supermodular, then $$ \mathbb{E}[fg]-\mathbb{E}[f]\mathbb{E}[g]\ge \frac{1}{4}\cdot\sum\limits_{i=1}^n\mathrm{Inf}_i[f]\mathrm{Inf}_i[g], $$ where the constant $1/4$ is optimal. We also prove a real-valued extension: for two functions with the same second-difference sign, the covariance is bounded below by the sum of products of their Level-1 Fourier coefficients. As a consequence, we verify the Friedgut--Kahn--Kalai--Keller spectral conjecture in this structured setting. The proofs combine a heat-semigroup representation based on second-order discrete derivatives with an independent induction argument for the Boolean case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_22307 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Talagrand-Type Correlation Inequalities for Submodular and Supermodular Functions on the Hypercube Chang, Fan Chen, Yu Combinatorics Functional Analysis Probability Talagran's correlation inequality provides quantitative lower bounds on the covariance of two increasing Boolean functions in terms of their coordinate influences, but, in general, a logarithmic loss is necessary. Motivated by a question of Kalai, Keller and Mossel, we identify a natural log-free regime. We prove that if two increasing Boolean functions on $\{0,1\}^n$ are either both submodular or both supermodular, then $$ \mathbb{E}[fg]-\mathbb{E}[f]\mathbb{E}[g]\ge \frac{1}{4}\cdot\sum\limits_{i=1}^n\mathrm{Inf}_i[f]\mathrm{Inf}_i[g], $$ where the constant $1/4$ is optimal. We also prove a real-valued extension: for two functions with the same second-difference sign, the covariance is bounded below by the sum of products of their Level-1 Fourier coefficients. As a consequence, we verify the Friedgut--Kahn--Kalai--Keller spectral conjecture in this structured setting. The proofs combine a heat-semigroup representation based on second-order discrete derivatives with an independent induction argument for the Boolean case. |
| title | Talagrand-Type Correlation Inequalities for Submodular and Supermodular Functions on the Hypercube |
| topic | Combinatorics Functional Analysis Probability |
| url | https://arxiv.org/abs/2510.22307 |