An official website of the United States government
Abstract We elucidate the relationship between the threshold and the expectation‐threshold of a down‐set. Qualitatively, our main result demonstrates that there exist down‐sets with polynomial gaps between their thresholds and expectation‐thresholds; in particular, the logarithmic gap predictions of Kahn–Kalai and Talagrand (recently proved by Park–Pham and Frankston–Kahn–Narayanan–Park) about up‐sets do not apply to down‐sets. Quantitatively, we show that any collection of graphs on that covers the family of all triangle‐free graphs on satisfies the inequality for some universal , and this is essentially best‐possible.
more »
« less
On a problem of M. Talagrand
Abstract We address a special case of a conjecture of M. Talagrand relating two notions of “threshold” for an increasing family of subsets of a finite setV. The full conjecture implies equivalence of the “Fractional Expectation‐Threshold Conjecture,” due to Talagrand and recently proved by the authors and B. Narayanan, and the (stronger) “Expectation‐Threshold Conjecture” of the second author and G. Kalai. The conjecture under discussion here says there is a fixedLsuch that if, for a given , admits withand(a.k.a. isweakly p‐small), then admits such a taking values in ( is‐small). Talagrand showed this when is supported on singletons and suggested, as a more challenging test case, proving it when is supported on pairs. The present work provides such a proof.
more »
« less
- Award ID(s):
- 1501962
- PAR ID:
- 10521322
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- Volume:
- 61
- Issue:
- 4
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- 710 to 723
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The upper tail problem in a random graph asks to estimate the probability that the number of copies of some fixed subgraph in an Erdős‐Rényi random graph exceeds its expectation by some constant factor. There has been much exciting recent progress on this problem. We study the corresponding problem for hypergraphs, for which less is known about the large deviation rate. We present new phenomena in upper tail large deviations for sparse random hypergraphs that are not seen in random graphs. We conjecture a formula for the large deviation rate, that is, the first order asymptotics of the log‐probability that the number of copies of fixed subgraphHin a sparse Erdős‐Rényi randomk‐uniform hypergraph exceeds its expectation by a constant factor. This conjecture turns out to be significantly more intricate compared to the case for graphs. We verify our conjecture when the fixed subgraphHbeing counted is a clique, as well as whenHis the 3‐uniform 6‐vertex 4‐edge hypergraph consisting of alternating faces of an octahedron, where new techniques are required.more » « less
-
Abstract We study for bounded multiplicative functions sums of the formestablishing that their variance over residue classes is small as soon as , for almost all moduli , with a nearly power‐saving exceptional set of . This improves and generalizes previous results of Hooley on Barban–Davenport–Halberstam type theorems for such , and moreover our exceptional set is essentially optimal unless one is able to make progress on certain well‐known conjectures. We are nevertheless able to prove stronger bounds for the number of the exceptional moduli in the cases where is restricted to be either smooth or prime, and conditionally on GRH we show that our variance estimate is valid for every . These results are special cases of a “hybrid result” that we establish that works for sums of over almost all short intervals and arithmetic progressions simultaneously, thus generalizing the Matomäki–Radziwiłł theorem on multiplicative functions in short intervals. We also consider the maximal deviation of overallresidue classes in the square root range , and show that it is small for “smooth‐supported” , again apart from a nearly power‐saving set of exceptional , thus providing a smaller exceptional set than what follows from Bombieri–Vinogradov type theorems. As an application of our methods, we consider Linnik‐type problems for products of exactly three primes, and in particular prove a ternary approximation to a conjecture of Erdős on representing every element of the multiplicative group as the product of two primes less than .more » « less
-
Let\Sigmabe a strictly convex, compact patch of aC^{2}hypersurface in\mathbb{R}^{n}, with non-vanishing Gaussian curvature and surface measured\sigmainduced by the Lebesgue measure in\mathbb{R}^{n}. The Mizohata–Takeuchi conjecture states that \int |\widehat{g d\sigma}|^{2} w \leq C \|Xw\|_{\infty} \int |g|^{2} for allg\in L^{2}(\Sigma)and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), whereXdenotes theX-ray transform. As partial progress towards the conjecture, we show, as a straightforward consequence of recently-established decoupling inequalities, that for every\varepsilon>0, there exists a positive constantC_{\varepsilon}, which depends only on\Sigmaand\varepsilon, such that for allR \geq 1and all weightsw \colon \mathbb{R}^{n}\rightarrow [0,+\infty), we have \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\varepsilon} \sup_{T} \Big(\int_{T} w^{(n+1)/2}\Big)^{2/(n+1)}\int |g|^{2}, whereTranges over the family of tubes in\mathbb{R}^{n}of dimensionsR^{1/2}\times \cdots \times R^{1/2}\times R. From this we deduce the Mizohata–Takeuchi conjecture with anR^{(n-1)/(n+1)}-loss; i.e., that \int_{B_R}|\widehat{g d\sigma}|^{2} w \leq C_{\varepsilon} R^{\frac{n-1}{n+1}+ \varepsilon}\|Xw\|_{\infty} \int |g|^{2} for any ballB_{R}of radiusRand any\varepsilon>0. The power(n-1)/(n+1)here cannot be replaced by anything smaller unless properties of\widehat{g d\sigma}beyond ‘decoupling axioms’ are exploited. We also provide estimates which improve this inequality under various conditions on the weight, and discuss some new cases where the conjecture holds.more » « less
-
Abstract Letfbe an$$L^2$$-normalized holomorphic newform of weightkon$$\Gamma _0(N) \backslash \mathbb {H}$$withNsquarefree or, more generally, on any hyperbolic surface$$\Gamma \backslash \mathbb {H}$$attached to an Eichler order of squarefree level in an indefinite quaternion algebra over$$\mathbb {Q}$$. Denote byVthe hyperbolic volume of said surface. We prove the sup-norm estimate$$\begin{align*}\| \Im(\cdot)^{\frac{k}{2}} f \|_{\infty} \ll_{\varepsilon} (k V)^{\frac{1}{4}+\varepsilon} \end{align*}$$ with absolute implied constant. For a cuspidal Maaß newform$$\varphi $$of eigenvalue$$\lambda $$on such a surface, we prove that$$\begin{align*}\|\varphi \|_{\infty} \ll_{\lambda,\varepsilon} V^{\frac{1}{4}+\varepsilon}. \end{align*}$$ We establish analogous estimates in the setting of definite quaternion algebras.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1002/rsa.21077
