skip to main content

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Relations between scaling exponents in unimodular random graphs
Abstract

We investigate the validity of the “Einstein relations” in the general setting of unimodular random networks. These are equalities relating scaling exponents:$$\begin{aligned} d_{w} &= d_{f} + \tilde{\zeta }, \\ d_{s} &= 2 d_{f}/d_{w}, \end{aligned}$$wheredwis the walk dimension,dfis the fractal dimension,dsis the spectral dimension, and$\tilde{\zeta }$is the resistance exponent. Roughly speaking, this relates the mean displacement and return probability of a random walker to the density and conductivity of the underlying medium. We show that ifdfand$\tilde{\zeta } \geqslant 0$exist, thendwanddsexist, and the aforementioned equalities hold. Moreover, our primary new estimate$d_{w} \geqslant d_{f} + \tilde{\zeta }$is established for all$\tilde{\zeta } \in \mathbb{R}$.

For the uniform infinite planar triangulation (UIPT), this yields the consequencedw=4 usingdf=4 (Angel in Geom. Funct. Anal. 13(5):935–974, 2003) and$\tilde{\zeta }=0$(established here as a consequence of the Liouville Quantum Gravity theory, following Gwynne-Miller 2020 and (Ding and Gwynne in Commun. Math. Phys. 374(3):1877–1934, 2020)). The conclusiondw=4 had been previously established by Gwynne and Hutchcroft (2018) using more elaborate methods. A new consequence is thatdw=dffor the uniform infinite Schnyder-wood decorated triangulation, implying that the simple random walk is subdiffusive, sincedf>2.

  more » « less
Award ID(s):
2007079
PAR ID:
10483026
Author(s) / Creator(s):
Publisher / Repository:
Springer
Date Published:
Journal Name:
Geometric and Functional Analysis
Volume:
33
Issue:
6
ISSN:
1016-443X
Page Range / eLocation ID:
1539 to 1580
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ( , Mathematical Proceedings of the Cambridge Philosophical Society)
    Abstract

    When$k\geqslant 4$and$0\leqslant d\leqslant (k-2)/4$, we consider the system of Diophantine equations\begin{align*}x_1^j+\ldots +x_k^j=y_1^j+\ldots +y_k^j\quad (1\leqslant j\leqslant k,\, j\ne k-d).\end{align*}We show that in this cousin of a Vinogradov system, there is a paucity of non-diagonal positive integral solutions. Our quantitative estimates are particularly sharp when$d=o\!\left(k^{1/4}\right)$.

     
    more » « less
  2. ; ( , Scientific Reports)
    Abstract

    Recent spectacular advances by AI programs in 3D structure predictions from protein sequences have revolutionized the field in terms of accuracy and speed. The resulting “folding frenzy” has already produced predicted protein structure databases for the entire human and other organisms’ proteomes. However, rapidly ascertaining a predicted structure’s reliability based on measured properties in solution should be considered. Shape-sensitive hydrodynamic parameters such as the diffusion and sedimentation coefficients ($${D_{t(20,w)}^{0}}$$Dt(20,w)0,$${s_{{\left( {{20},w} \right)}}^{{0}} }$$s20,w0) and the intrinsic viscosity ([η]) can provide a rapid assessment of the overall structure likeliness, and SAXS would yield the structure-related pair-wise distance distribution functionp(r) vs.r. Using the extensively validated UltraScan SOlution MOdeler (US-SOMO) suite, a database was implemented calculating from AlphaFold structures the corresponding$${D_{t(20,w)}^{0}}$$Dt(20,w)0,$${s_{{\left( {{20},w} \right)}}^{{0}} }$$s20,w0, [η],p(r) vs.r, and other parameters. Circular dichroism spectra were computed using the SESCA program. Some of AlphaFold’s drawbacks were mitigated, such as generating whenever possible a protein’s mature form. Others, like the AlphaFold direct applicability to single-chain structures only, the absence of prosthetic groups, or flexibility issues, are discussed. Overall, this implementation of the US-SOMO-AF database should already aid in rapidly evaluating the consistency in solution of a relevant portion of AlphaFold predicted protein structures.

     
    more » « less
  3. ; ; ; ; ; ( , Mathematische Annalen)
    Abstract

    Consider two half-spaces$$H_1^+$$H1+and$$H_2^+$$H2+in$${\mathbb {R}}^{d+1}$$Rd+1whose bounding hyperplanes$$H_1$$H1and$$H_2$$H2are orthogonal and pass through the origin. The intersection$${\mathbb {S}}_{2,+}^d:={\mathbb {S}}^d\cap H_1^+\cap H_2^+$$S2,+d:=Sd∩H1+∩H2+is a spherical convex subset of thed-dimensional unit sphere$${\mathbb {S}}^d$$Sd, which contains a great subsphere of dimension$$d-2$$d-2and is called a spherical wedge. Choosenindependent random points uniformly at random on$${\mathbb {S}}_{2,+}^d$$S2,+dand consider the expected facet number of the spherical convex hull of these points. It is shown that, up to terms of lower order, this expectation grows like a constant multiple of$$\log n$$logn. A similar behaviour is obtained for the expected facet number of a homogeneous Poisson point process on$${\mathbb {S}}_{2,+}^d$$S2,+d. The result is compared to the corresponding behaviour of classical Euclidean random polytopes and of spherical random polytopes on a half-sphere.

     
    more » « less
  4. ; ; ( , Algorithmica)
    Abstract

    The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for space-bounded computation uses a seed of length$$O(\log n \cdot \log (nw/\varepsilon )+\log d)$$O(logn·log(nw/ε)+logd)to fool ordered branching programs of lengthn, widthw, and alphabet sizedto within error$$\varepsilon $$ε. A series of works have shown that the analysis of the INW generator can be improved for the class ofpermutationbranching programs or the more generalregularbranching programs, improving the$$O(\log ^2 n)$$O(log2n)dependence on the lengthnto$$O(\log n)$$O(logn)or$${\tilde{O}}(\log n)$$O~(logn). However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length$$O(\log (nwd/\varepsilon ))$$O(log(nwd/ε)). In this paper, we prove that any “spectral analysis” of the INW generator requires seed length$$\begin{aligned} \Omega \left( \log n\cdot \log \log \left( \min \{n,d\}\right) +\log n\cdot \log \left( w/\varepsilon \right) +\log d\right) \end{aligned}$$Ωlogn·loglogmin{n,d}+logn·logw/ε+logdto fool ordered permutation branching programs of lengthn, widthw, and alphabet sizedto within error$$\varepsilon $$ε. By “spectral analysis” we mean an analysis of the INW generator that relies only on the spectral expansion of the graphs used to construct the generator; this encompasses all prior analyses of the INW generator. Our lower bound matches the upper bound of Braverman–Rao–Raz–Yehudayoff (FOCS 2010, SICOMP 2014) for regular branching programs of alphabet size$$d=2$$d=2except for a gap between their$$O\left( \log n \cdot \log \log n\right) $$Ologn·loglognterm and our$$\Omega \left( \log n \cdot \log \log \min \{n,d\}\right) $$Ωlogn·loglogmin{n,d}term. It also matches the upper bounds of Koucký–Nimbhorkar–Pudlák (STOC 2011), De (CCC 2011), and Steinke (ECCC 2012) for constant-width ($$w=O(1)$$w=O(1)) permutation branching programs of alphabet size$$d=2$$d=2to within a constant factor. To fool permutation branching programs in the measure ofspectral norm, we prove that any spectral analysis of the INW generator requires a seed of length$$\Omega \left( \log n\cdot \log \log n+\log n\cdot \log (1/\varepsilon )\right) $$Ωlogn·loglogn+logn·log(1/ε)when the width is at least polynomial inn($$w=n^{\Omega (1)}$$w=nΩ(1)), matching the recent upper bound of Hoza–Pyne–Vadhan (ITCS 2021) to within a constant factor.

     
    more » « less
  5. ; ; ; ; ; ( , Mathematische Annalen)
    Abstract

    Let us call a simple graph on$$n\geqslant 2$$n⩾2vertices a prime gap graph if its vertex degrees are 1 and the first$$n-1$$n-1prime gaps. We show that such a graph exists for every largen, and in fact for every$$n\geqslant 2$$n⩾2if we assume the Riemann hypothesis. Moreover, an infinite sequence of prime gap graphs can be generated by the so-called degree preserving growth process. This is the first time a naturally occurring infinite sequence of positive integers is identified as graphic. That is, we show the existence of an interesting, and so far unique, infinite combinatorial object.

     
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email