skip to main content

Attention:

The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, January 16 until 2:00 AM ET on Friday, January 17 due to maintenance. We apologize for the inconvenience.


Title: A proof of the Kahn–Kalai conjecture

Proving the “expectation-threshold” conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing propertyF\mathcal {F}on a finite setXX,\[pc(F)=O(q(F)log⁡<#comment/>ℓ<#comment/>(F)),p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})),\]wherepc(F)p_c(\mathcal {F})andq(F)q(\mathcal {F})are the threshold and “expectation threshold” ofF\mathcal {F}, andℓ<#comment/>(F)\ell (\mathcal {F})is the maximum of22and the maximum size of a minimal member ofF\mathcal {F}.

 
more » « less
Award ID(s):
2324978
PAR ID:
10503739
Author(s) / Creator(s):
;
Publisher / Repository:
American Mathematical Society
Date Published:
Journal Name:
Journal of the American Mathematical Society
Volume:
37
Issue:
1
ISSN:
0894-0347
Page Range / eLocation ID:
235 to 243
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. For each odd integern≥<#comment/>3n \geq 3, we construct a rank-3 graphΛ<#comment/>n\Lambda _nwith involutionγ<#comment/>n\gamma _nwhose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>n,γ<#comment/>n)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)is stably isomorphic to the exotic Cuntz algebraEn\mathcal E_n. This construction is optimal, as we prove that a rank-2 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda ,\gamma )can never satisfyCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)∼<#comment/>MEEnC^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n, and Boersema reached the same conclusion for rank-1 graphs (directed graphs) in [Münster J. Math.10(2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank-1 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda , \gamma )whose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )is stably isomorphic to the suspensionSRS \mathbb {R}. In the Appendix, we show that theii-fold suspensionSiRS^i \mathbb {R}is stably isomorphic to a graph algebra iff−<#comment/>2≤<#comment/>i≤<#comment/>1-2 \leq i \leq 1.

     
    more » « less
  2. Let(R,m)(R,\mathfrak {m})be a Noetherian local ring of dimensiond≥<#comment/>2d\geq 2. We prove that ife(R^<#comment/>red)>1e(\widehat {R}_{red})>1, then the classical Lech’s inequality can be improved uniformly for allm\mathfrak {m}-primary ideals, that is, there existsε<#comment/>>0\varepsilon >0such thate(I)≤<#comment/>d!(e(R)−<#comment/>ε<#comment/>)ℓ<#comment/>(R/I)e(I)\leq d!(e(R)-\varepsilon )\ell (R/I)for allm\mathfrak {m}-primary idealsI⊆<#comment/>RI\subseteq R. This answers a question raised by Huneke, Ma, Quy, and Smirnov [Adv. Math. 372 (2020), pp. 107296, 33]. We also obtain partial results towards improvements of Lech’s inequality when we fix the number of generators ofII.

     
    more » « less
  3. We introduce the notions of symmetric and symmetrizable representations ofSL2⁡<#comment/>(Z){\operatorname {SL}_2(\mathbb {Z})}. The linear representations ofSL2⁡<#comment/>(Z){\operatorname {SL}_2(\mathbb {Z})}arising from modular tensor categories are symmetric and have congruence kernel. Conversely, one may also reconstruct modular data from finite-dimensional symmetric, congruence representations ofSL2⁡<#comment/>(Z){\operatorname {SL}_2(\mathbb {Z})}. By investigating aZ/2Z\mathbb {Z}/2\mathbb {Z}-symmetry of some Weil representations at prime power levels, we prove that all finite-dimensional congruence representations ofSL2⁡<#comment/>(Z){\operatorname {SL}_2(\mathbb {Z})}are symmetrizable. We also provide examples of unsymmetrizable noncongruence representations ofSL2⁡<#comment/>(Z){\operatorname {SL}_2(\mathbb {Z})}that are subrepresentations of a symmetric one.

     
    more » « less
  4. We show that for primesN,p≥<#comment/>5N, p \geq 5withN≡<#comment/>−<#comment/>1modpN \equiv -1 \bmod p, the class number ofQ(N1/p)\mathbb {Q}(N^{1/p})is divisible bypp. Our methods are via congruences between Eisenstein series and cusp forms. In particular, we show that whenN≡<#comment/>−<#comment/>1modpN \equiv -1 \bmod p, there is always a cusp form of weight22and levelΓ<#comment/>0(N2)\Gamma _0(N^2)whoseℓ<#comment/>\ellth Fourier coefficient is congruent toℓ<#comment/>+1\ell + 1modulo a prime abovepp, for all primesℓ<#comment/>\ell. We use the Galois representation of such a cusp form to explicitly construct an unramified degree-ppextension ofQ(N1/p)\mathbb {Q}(N^{1/p}).

     
    more » « less
  5. In this paper, we consider the linear convection-diffusion equation in one dimension with periodic boundary conditions, and analyze the stability of fully discrete methods that are defined with local discontinuous Galerkin (LDG) methods in space and several implicit-explicit (IMEX) Runge-Kutta methods in time. By using the forward temporal differences and backward temporal differences, respectively, we establish two general frameworks of the energy-method based stability analysis. From here, the fully discrete schemes being considered are shown to have monotonicity stability, i.e. theL2L^2norm of the numerical solution does not increase in time, under the time step conditionτ<#comment/>≤<#comment/>F(h/c,d/c2)\tau \le \mathcal {F}(h/c, d/c^2), with the convection coefficientcc, the diffusion coefficientdd, and the mesh sizehh. The functionF\mathcal {F}depends on the specific IMEX temporal method, the polynomial degreekkof the discrete space, and the mesh regularity parameter. Moreover, the time step condition becomesτ<#comment/>≲<#comment/>h/c\tau \lesssim h/cin the convection-dominated regime and it becomesτ<#comment/>≲<#comment/>d/c2\tau \lesssim d/c^2in the diffusion-dominated regime. The result is improved for a first order IMEX-LDG method. To complement the theoretical analysis, numerical experiments are further carried out, leading to slightly stricter time step conditions that can be used by practitioners. Uniform stability with respect to the strength of the convection and diffusion effects can especially be relevant to guide the choice of time step sizes in practice, e.g. when the convection-diffusion equations are convection-dominated in some sub-regions.

     
    more » « less