Proving the “expectationthreshold” conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing property
This content will become publicly available on April 9, 2025
Given a (bounded affine) permutation
 NSFPAR ID:
 10499665
 Publisher / Repository:
 American Mathematical Society (AMS)
 Date Published:
 Journal Name:
 Communications of the American Mathematical Society
 Volume:
 4
 Issue:
 8
 ISSN:
 26923688
 Format(s):
 Medium: X Size: p. 357386
 Size(s):
 ["p. 357386"]
 Sponsoring Org:
 National Science Foundation
More Like this

$\mathcal {F}$ on a finite set$X$ ,\[$p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})),$\] where$p_c(\mathcal {F})$ and$q(\mathcal {F})$ are the threshold and “expectation threshold” of$\mathcal {F}$ , and$\ell (\mathcal {F})$ is the maximum of$2$ and the maximum size of a minimal member of$\mathcal {F}$ . 
We show that for primes
$N, p \geq 5$ with$N \equiv 1 \bmod p$ , the class number of$\mathbb {Q}(N^{1/p})$ is divisible by$p$ . Our methods are via congruences between Eisenstein series and cusp forms. In particular, we show that when$N \equiv 1 \bmod p$ , there is always a cusp form of weight$2$ and level$\Gamma _0(N^2)$ whose$\ell$ th Fourier coefficient is congruent to$\ell + 1$ modulo a prime above$p$ , for all primes$\ell$ . We use the Galois representation of such a cusp form to explicitly construct an unramified degree$p$ extension of$\mathbb {Q}(N^{1/p})$ . 
We show that for any even logconcave probability measure
$\mu$ on$\mathbb {R}^n$ , any pair of symmetric convex sets$K$ and$L$ , and any$\lambda \in [0,1]$ ,$\begin{equation*} \mu ((1\lambda ) K+\lambda L)^{c_n}\geq (1\lambda ) \mu (K)^{c_n}+\lambda \mu (L)^{c_n}, \end{equation*}$ where$c_n\geq n^{4o(1)}$ . This constitutes progress towards the dimensional BrunnMinkowski conjecture (see Richard J. Gardner and Artem Zvavitch [Tran. Amer. Math. Soc. 362 (2010), pp. 5333–5353]; Andrea Colesanti, Galyna V. Livshyts, Arnaud Marsiglietti [J. Funct. Anal. 273 (2017), pp. 1120–1139]). Moreover, our bound improves for various special classes of logconcave measures. 
For each odd integer
$n \geq 3$ , we construct a rank3 graph$\Lambda _n$ with involution$\gamma _n$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)$ is stably isomorphic to the exotic Cuntz algebra$\mathcal E_n$ . This construction is optimal, as we prove that a rank2 graph with involution$(\Lambda ,\gamma )$ can never satisfy$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n$ , and Boersema reached the same conclusion for rank1 graphs (directed graphs) in [Münster J. Math.10 (2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank1 graph with involution$(\Lambda , \gamma )$ whose real$C^*$ algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )$ is stably isomorphic to the suspension$S \mathbb {R}$ . In the Appendix, we show that the$i$ fold suspension$S^i \mathbb {R}$ is stably isomorphic to a graph algebra iff$2 \leq i \leq 1$ . 
By discretizing an argument of Kislyakov, Naor and Schechtman proved that the 1Wasserstein metric over the planar grid
$\{0,1,\dots , n\}^2$ has$L_1$ distortion bounded below by a constant multiple of$\sqrt {\log n}$ . We provide a new “dimensionality” interpretation of Kislyakov’s argument, showing that if$\{G_n\}_{n=1}^\infty$ is a sequence of graphs whose isoperimetric dimension and Lipschitzspectral dimension equal a common number$\delta \in [2,\infty )$ , then the 1Wasserstein metric over$G_n$ has$L_1$ distortion bounded below by a constant multiple of$(\log G_n)^{\frac {1}{\delta }}$ . We proceed to compute these dimensions for$\oslash$ powers of certain graphs. In particular, we get that the sequence of diamond graphs$\{\mathsf {D}_n\}_{n=1}^\infty$ has isoperimetric dimension and Lipschitzspectral dimension equal to 2, obtaining as a corollary that the 1Wasserstein metric over$\mathsf {D}_n$ has$L_1$ distortion bounded below by a constant multiple of$\sqrt {\log  \mathsf {D}_n}$ . This answers a question of Dilworth, Kutzarova, and Ostrovskii and exhibits only the third sequence of$L_1$ embeddable graphs whose sequence of 1Wasserstein metrics is not$L_1$ embeddable.