Shirshendu Ganguly

I am an Associate Professor in the Department of Statistics at UC Berkeley.

401 Evans Hall
UC Berkeley
Berkeley, CA 94720
sganguly@berkeley.edu.

Research

I am broadly interested in probability theory and its applications. Recently I have been working on problems in Disordered metric geometries with focus on geometry of geodesics in percolation models, Scaling limits and Phase transitions in statistical mechanics, Large deviations and counting problems in sparse non-linear settings, Mixing time of Markov Chains, Random walk on graphs and Random Matrix theory.

Publications and preprints

Education and past employment.

UC Berkeley. Assistant Professsor. 2018-2021.
UC Berkeley. Miller Postdoctoral Fellow. Statistics and Mathematics. 2016-2018.
University of Washington. PhD in Mathematics. 2011-2016. .

Teaching

Stat 155. Game theory. Fall 2018.
Stat C205A/ Math C218A. Probability theory. Fall 2019.
Stat C205A/ Math C218A. Probability theory. Fall 2020.

Stat C205A/ Math C218A. Probability theory (With Prof. Steve Evans). Fall 2021.
For access to bcourses mail me your SID with Stat C205A/ Math C218A as your subject.
Undergraduates wanting to enroll must fill out the google form .

Recent Works

Fractal Geometry of Airy Sheet

Fractal geometry of the space-time difference profile in the directed landscape via construction of geodesic local times.

(with Lingfu Zhang). Arxiv

The Directed Landscape, a random directed metric on the plane (where the first and the second coordinates are termed spatial and temporal respectively), was constructed in the breakthrough work of Dauvergne, Ortmann, and Virág, and has since been shown to be the scaling limit of various integrable models of Last Passage percolation, a central member of the Kardar-Parisi-Zhang universality class. It exhibits several scale invariance properties making it a natural source of rich fractal behavior. Such a study was initiated in Basu-Ganguly-Hammond, where the difference profile i.e., the difference of passage times from two fixed points (say (±1,0)), was considered. Owing to geodesic geometry, it turns out that this difference process is almost surely locally constant. The set of non-constancy is connected to disjointness of geodesics and inherits remarkable fractal properties. In particular, it has been established that when only the spatial coordinate is varied, the set of non-constancy of the difference profile has Hausdorff dimension 1/2, and bears a rather strong resemblance to the zero set of Brownian motion. The arguments crucially rely on a monotonicity property, which is absent when the temporal structure of the process is probed, necessitating the development of new methods. In this paper, we put forth several new ideas, and show that the set of non-constancy of the 2D difference profile and the 1D temporal process (when the spatial coordinate is fixed and the temporal coordinate is varied) have Hausdorff dimensions 5/3 and 2/3 respectively. A particularly crucial ingredient in our analysis is the novel construction of a local time process for the geodesic akin to Brownian local time, supported on the "zero set" of the geodesic. Further, we show that the latter has Hausdorff dimension 1/3 in contrast to the zero set of Brownian motion which has dimension 1/2.
Local and global comparisons of the Airy difference profile to Brownian local time

(with Milind Hegde). Arxiv

There has recently been much activity within the Kardar-Parisi-Zhang universality class spurred by the construction of the canonical limiting object, the parabolic Airy sheet $\mathcal{S}:\mathbb{R}^2\to\mathbb{R}$ \cite{dauvergne2018directed}. The parabolic Airy sheet provides a coupling of parabolic Airy$_2$ processes---a universal limiting geodesic weight profile in planar last passage percolation models---and a natural goal is to understand this coupling. Geodesic geometry suggests that the difference of two parabolic Airy$_2$ processes, i.e., a difference profile, encodes important structural information. This difference profile $\wdf$, given by $\mathbb{R}\to\mathbb{R}:x\mapsto \mathcal{S}(1,x)-\mathcal{S}(-1,x)$, was first studied by Basu, Ganguly, and Hammond \cite{basu2019fractal}, who showed that it is monotone and almost everywhere constant, with its points of non-constancy forming a set of Hausdorff dimension $1/2$. Noticing that this is also the Hausdorff dimension of the zero set of Brownian motion leads to the question: is there a connection between $\mathcal{D}$ and Brownian local time? Establishing that there is indeed a connection, we prove two results. On a global scale, we show that $\mathcal{D}$ can be written as a \emph{Brownian local time patchwork quilt}, i.e., as a concatenation of random restrictions of functions which are each absolutely continuous to Brownian local time (of rate four) away from the origin. On a local scale, we explicitly obtain Brownian local time of rate four as a local limit of $\mathcal{D}$ at a point of increase, picked by a number of methods, including at a typical point sampled according to the distribution function $\mathcal{D}$. Our arguments rely on the representation of $\S$ in terms of a last passage problem through the parabolic Airy line ensemble and an understanding of geodesic geometry at deterministic and random times.
Fractal geometry of Airy$_2$ processes coupled via the Airy sheet.

(with Riddhipratim Basu, Alan Hammond) To appear in Annals of Probability. Arxiv

n last passage percolation models lying in the Kardar-Parisi-Zhang universality class, maximizing paths that travel over distances of order n accrue energy that fluctuates on scale $n^{1/3}$; and these paths deviate from the linear interpolation of their endpoints on scale $n^{2/3}$. These maximizing paths and their energies may be viewed via a coordinate system that respects these scalings. What emerges by doing so is a system indexed by $x,y \in \mathbb{R}$ and $s,t \in \mathbb{R}$ with $s < t$ of unit order quantities $W_n(x,s;y,t)$ specifying the scaled energy of the maximizing path that moves in scaled coordinates between $(x,s)$ and $(y,t)$. The space-time Airy sheet is, after a parabolic adjustment, the putative distributional limit $W_{\infty}$ of this system as $n\to \infty$. The Airy sheet has recently been constructed in [15] as such a limit of Brownian last passage percolation. In this article, we initiate the study of fractal geometry in the Airy sheet. We prove that the scaled energy difference profile given by $\mathbb{R} \to \mathbb{R} :z \to W_{\infty}(1,0;z,1)−W_{\infty}(−1,0;z,1)$ is a non-decreasing process that is constant in a random neighbourhood of almost every $z \in \mathbb{R}$; and that the exceptional set of $z \in \mathbb{R}$ that violate this condition almost surely has Hausdorff dimension one-half. Points of violation correspond to special behaviour for scaled maximizing paths, and we prove the result by investigating this behaviour, making use of two inputs from recent studies of scaled Brownian LPP; namely, Brownian regularity of profiles, and estimates on the rarity of pairs of disjoint scaled maximizing paths that begin and end close to each other.
Hausdorff dimensions for shared endpoints of disjoint geodesics in the directed landscape.

(with Erik Bates, Alan Hammond) Arxiv

Within the Kardar-Parisi-Zhang universality class, the space-time Airy sheet is conjectured to be the canonical scaling limit for last passage percolation models. In recent work arXiv:1812.00309 of Dauvergne, Ortmann, and Virág, this object was constructed and shown to be the limit after parabolic correction of one such model: Brownian last passage percolation. This limit object, called the directed landscape, admits geodesic paths between any two space-time points $(x,s($ and $(y,t)$ with $s < t $. In this article, we examine fractal properties of the set of these paths. Our main results concern exceptional endpoints admitting disjoint geodesics. First, we fix two distinct starting locations $x_1$ and $x_2$, and consider geodesics traveling $(x_1,0)\to (y,1)$ and $(x_2,0)\to (y,1)$. We prove that the set of $y\in \mathbb{R}$ for which these geodesics coalesce only at time 1 has Hausdorff dimension one-half. Second, we consider endpoints $(x,0)$ and $(y,1)$ between which there exist two geodesics intersecting only at times 0 and 1. We prove that the set of such $(x,y)\in \mathbb{R}^2$ also has Hausdorff dimension one-half. The proofs require several inputs of independent interest, including (i) connections to the so-called difference weight profile studied in arXiv:1904.01717; and (ii) a tail estimate on the number of disjoint geodesics starting and ending in small intervals. The latter result extends the analogous estimate proved for the prelimiting model in arXiv:1709.04110..

Mixing time for random surface evolutions.

Cutoff for the Glauber dynamics of the lattice free field.

(with Reza Gheissari). Arxiv

The Gaussian Free Field (GFF) is a canonical random surface in probability theory generalizing Brownian motion to higher dimensions. In two dimensions, it is critical in several senses, and is expected to be the universal scaling limit of a host of random surface models in statistical physics. It also arises naturally as the stationary solution to the stochastic heat equation with additive noise. Focusing on the dynamical aspects of the corresponding universality class, we study the mixing time, i.e., the rate of convergence to stationarity, for the canonical prelimiting object, namely the discrete Gaussian free field (DGFF), evolving along the (heat-bath) Glauber dynamics. While there have been significant breakthroughs made in the study of cutoff for Glauber dynamics of random curves, analogous sharp mixing bounds for random surface evolutions have remained elusive. In this direction, we establish that on a box of side-length $n$ in $\mathbb{ℤ}^2$, when started out of equilibrium, the Glauber dynamics for the DGFF exhibit cutoff at time $\frac{2}{\pi^2}n^2\log n$.

Environment seen from infinite geodesics in Liouville Quantum Gravity.

Environment seen from infinite geodesics in Liouville Quantum Gravity.

(with Riddhipratim Basu and Manan Bhatia). Arxiv

First passage percolation (FPP) on ℤd or ℝd is a canonical model of a random metric space where the standard Euclidean geometry is distorted by random noise. Of central interest is the length and the geometry of the geodesic, the shortest path between points. Since the latter, owing to its length minimization, traverses through atypically low values of the underlying noise variables, it is an important problem to quantify the disparity between the environment rooted at a point on the geodesic and the typical one. We investigate this in the context of $\gamma$-Liouville Quantum Gravity (LQG) (where $\gamma \in (0,2)$ is a parameter) -- a random Riemannian surface induced on the complex plane by the random metric tensor $e^{2\gamma h/d_\gamma}(dx^2+dy^2)$, where $h$ is the whole plane, properly centered, Gaussian Free Field (GFF), and dγ is the associated dimension. We consider the unique infinite geodesic $\Gamma$ from the origin, parametrized by the logarithm of its chemical length, and show that, for an almost sure realization of h, the distributions of the appropriately scaled field and the induced metric on a ball, rooted at a point "uniformly" sampled on $\Gamma$, converge to deterministic measures on the space of generalized functions and continuous metrics on the unit disk respectively. Moreover, we show that the limiting objects living on the unit disk are singular with respect to their typical counterparts, but become absolutely continuous away from the origin. Our arguments rely on unearthing a regeneration structure with fast decay of correlation in the geodesic owing to coalescence and the domain Markov property of the GFF. While there have been significant recent advances around this question for stochastic planar growth models in the KPZ class, the present work initiates this research program in the context of LQG.

Stability, Noise sensitivity and Chaos in dynamical last passsage percolation models.

Stability and Chaos in dynamical last passage percolation.

(with Alan Hammond). Arxiv

Many complex statistical mechanical models have intricate energy landscapes. The ground state, or lowest energy state, lies at the base of the deepest valley. In examples such as spin glasses and Gaussian polymers, there are many valleys; the abundance of near-ground states (at the base of valleys) indicates the phenomenon of chaos, under which the ground state alters profoundly when the model's disorder is slightly perturbed. In this article, we compute the critical exponent that governs the onset of chaos in a dynamic manifestation of a canonical model in the Kardar-Parisi-Zhang [KPZ] universality class, Brownian last passage percolation [LPP]. In this model in its static form, semi-discrete polymers advance through Brownian noise, their energy given by the integral of the white noise encountered along their journey. A ground state is a geodesic, of extremal energy given its endpoints. We perturb Brownian LPP by evolving the disorder under an Ornstein-Uhlenbeck flow. We prove that, for polymers of length n, a sharp phase transition marking the onset of chaos is witnessed at the critical time $n^{−1/3}$. Indeed, the overlap between the geodesics at times zero and $t>0$ that travel a given distance of order n will be shown to be of order n when $t\ll n^{−1/3}$; and to be of smaller order when $t\gg n^{−1/3}$. We expect this exponent to be shared among many interface models. The present work thus sheds light on the dynamical aspect of the KPZ class; it builds on several recent advances. These include Chatterjee's harmonic analytic theory [Cha14] of equivalence of superconcentration and chaos in Gaussian spaces; a refined understanding of the static landscape geometry of Brownian LPP developed in the companion paper [GH20]; and, underlying the latter, strong comparison estimates of the geodesic energy profile to Brownian motion in [CHH19].
The geometry of near ground states in Gaussian polymer models.

(with Alan Hammond). Arxiv

The energy and geometry of maximizing paths in integrable last passage percolation models are governed by the characteristic KPZ scaling exponents of one-third and two-thirds. When represented in scaled coordinates that respect these exponents, this random field of paths may be viewed as a complex energy landscape. We investigate the structure of valleys and connecting pathways in this landscape. The routed weight profile $\mathbb{R}\to \mathbb{R}$ associates to $x\in \mathbb{R}$ the maximum scaled energy obtainable by a path whose scaled journey from $(0,0)$ to $(0,1)$ passes through the point $(x,1/2)$. Developing tools of Brownian Gibbs analysis from [Ham16] and [CHH19], we prove an assertion of strong similarity of this profile for Brownian last passage percolation to Brownian motion of rate two on the unit-order scale. A sharp estimate on the rarity that two macroscopically different routes in the energy landscape offer energies close to the global maximum results. We prove robust assertions concerning modulus of continuity for the energy and geometry of scaled maximizing paths, that develop the results and approach of [HS20], delivering estimates valid on all scales above the microscopic. The geometry of excursions of near ground states about the maximizing path is investigated: indeed, we estimate the energetic shortfall of scaled paths forced to closely mimic the geometry of the maximizing route while remaining disjoint from it. We also provide bounds on the approximate gradient of the maximizing path, viewed as a function, ruling out sharp steep movement down to the microscopic scale. Our results find application in a companion study [GH20a] of the stability, and fragility, of last passage percolation under a dynamical perturbation.

Geodesic watermelons and optimal tail exponents for general Last passsage percolation models.

Optimal tail exponents in general last passage percolation via bootstrapping & geodesic geometry.

(with Milind Hegde). Arxiv

We consider last passage percolation on $\mathbb{Z}^2$ with general weight distributions, which is expected to be a member of the Kardar-Parisi-Zhang (KPZ) universality class. In this model, an oriented path between given endpoints which maximizes the sum of the i.i.d. weight variables associated to its vertices is called a geodesic. Under natural conditions of curvature of the limiting geodesic weight profile and stretched exponential decay of both tails of the point-to-point weight, we use geometric arguments to upgrade the assumptions to prove optimal upper and lower tail behavior with the exponents of $3/2$ and $3$ for the weight of the geodesic from $(1,1)$ to $(r,r)$ for all large finite $r$. The proofs merge several ideas, including the well known super-additivity property of last passage values, concentration of measure behavior for sums of stretched exponential random variables, and geometric insights coming from the study of geodesics and more general objects called geodesic watermelons. Previously such optimal behavior was only known for exactly solvable models, with proofs relying on hard analysis of formulas from integrable probability, which are unavailable in the general setting. Our results illustrate a facet of universality in a class of KPZ stochastic growth models and provide a geometric explanation of the upper and lower tail exponents of the GUE Tracy-Widom distribution, the conjectured one point scaling limit of such models. The key arguments are based on an observation of general interest that super-additivity allows a natural iterative bootstrapping procedure to obtain improved tail.
Interlacing and scaling exponents for the geodesic watermelon in last passage percolation.

(with Riddhipratim Basu, Alan Hammond, Milind Hegde). Arxiv

In discrete planar last passage percolation (LPP), random values are assigned independently to each vertex in $\mathbb{Z}^2$, and each finite upright path in $\mathbb{Z}^2$ is ascribed the weight given by the sum of values of its vertices. The weight of a collection of disjoint paths is the sum of its members' weights. The notion of a geodesic, a maximum weight path between two vertices, has a natural generalization concerning several disjoint paths: a $k$-geodesic watermelon in $[1,n]^2 \cap \mathbb{Z}^2$ is a collection of k disjoint paths contained in this square that has maximum weight among all such collections. While the weights of such collections are known to be important objects, the maximizing paths have been largely unexplored beyond the $k=1$ case. For exactly solvable models, such as exponential and geometric LPP, it is well known that for $k=1$ the exponents that govern fluctuation in weight and transversal distance are $1/3$ and $2/3$; that is, typically, the weight of the geodesic on the route $(1,1)\to (n,n)$ fluctuates around a dominant linear growth of the form $\mu n$ by the order of $n^{1/3}$; and the maximum Euclidean distance of the geodesic from the diagonal has order $n^{2/3}$. Assuming a strong but local form of convexity and one-point moderate deviation bounds for the geodesic weight profile---which are available in all known exactly solvable models---we establish that, typically, the $k$-geodesic watermelon's weight falls below $\mu nk$ by order $k^{5/3}n^{1/3}$, and its transversal fluctuation is of order $k^{1/3}n^{3/3}$. Our arguments crucially rely on, and develop, a remarkable deterministic interlacing property that the watermelons admit. Our methods also yield sharp rigidity estimates for naturally associated point processes, which improve on estimates obtained via tools from the theory of determinantal point processes available in the integrable setting.

Random walk on stationary graphs.

Chemical subdiffusivity of critical 2D percolation.

(with James R. Lee) Arxiv

We show that random walk on the incipient infinite cluster (IIC) of two-dimensional critical percolation is subdiffusive in the chemical distance (i.e., in the intrinisc graph metric). Kesten (1986) famously showed that this is true for the Euclidean distance, but it is known that the chemical distance is typically asymptotically larger. More generally, we show that subdiffusivity in the chemical distance holds for stationary random graphs of polynomial volume growth, as long as there is a multiscale way of covering the graph so that "deep patches" have "thin backbones". Our estimates are quantitative and give explicit bounds in terms of the one and two-arm exponents $\eta_2 > \eta_1 > 0$: For $d$-dimensional models, the mean chemical displacement after $T$ steps of random walk scales asymptotically slower than $T^{1/\beta}$, whenever \[ \beta < 2 + \frac{\eta_2-\eta_1}{d-\eta_1}\,. \] Using the conjectured values of $\eta_2 = \eta_1 + 1/4$ and $\eta_1 = 5/48$ for 2D lattices, the latter quantity is $2+12/91$.
Diffusive estimates for random walks on stationary random graphs of polynomial growth.

Example of a tree of `stretched' expanders where at infinite sequence of times random walk is superdiffusive.

(with James R. Lee, Yuval Peres) To appear in GAFA (2017) Arxiv

We show that for any stationary random graph $(G,p)$ of annealed polynomial growth there is an infinite sequence of times ${t_n}$ at which the random walk ${X_t}$ on $(G,p)$ is at most diffusive. This result is new even in the case when $G$ is a stationary random subgraph of $\mathbb{Z}^d$. Combined with the work of Benjamini, Duminil-Copin, Kozma, and Yadin (2015), it implies that $G$ almost surely does not admit a non-constant harmonic function of sublinear growth. To complement this, we argue that passing to a subsequence of times ${t_n}$ is necessary, as there are stationary random graphs of (almost sure) polynomial growth where the random walk is almost surely superdiffusive at an infinite subset of times.

Interface geometry in low temperature Ising model.

Local and global geometry of the 2D Ising interface in critical pre-wetting.

(with Reza Gheissari). Arxiv

Consider the Ising model at low-temperatures and positive external field λ on an N×N box with Dobrushin boundary conditions that are plus on the north, east, and west boundaries and minus on the south boundary. If $\lambda=0$, the interface separating the plus and minus phases is diffusive, having $O(\sqrt{N}$ height fluctuations, and the model is fully wetted. Under an order one field, the interface fluctuations are $O(1)$ and the interface is only partially wetted, being pinned to its southern boundary. We study the critical pre-wetting regime of $\lambda_N \downarrow 0$, where the height fluctuations are expected to scale as $\lambda^{-1/3}$ and the rescaled interface is predicted to converge to the Ferrari--Spohn diffusion. Velenik (2004) identified the order of the area under the interface up to logarithmic corrections. Since then, more refined features of such interfaces have only been identified in simpler models of random walks under area tilts. In this paper, we resolve several conjectures of Velenik regarding the refined features of the Ising interface in the critical pre-wetting regime. Our main result is a sharp bound on the one-point height fluctuation, proving $e^{−\Theta(x^{3/2})}$ upper tails reminiscent of the Tracy--Widom distribution, capturing a tradeoff between the locally Brownian oscillations and the global field effect. This is used to deduce various geometric properties of the interface, including the sharp order of the area it confines, and the poly-logarithmic pre-factor governing its maximum height fluctuation. Our arguments combine inputs coming from the random-line representation of the Ising interface, with more probabilistic and geometric arguments guided by local resampling and coupling methods

Non-linear Large deviations and counting problems in sparse settings.

Upper tails and independence polynomials in random graphs.

(with Bhaswar B. Bhattacharya, Eyal Lubetzky, Yufei Zhao). To appear in Advances in Mathematics (2017). Arxiv

The upper tail problem in the Erdos-Renyi random graph $G∼G(n,p)$ asks to estimate the probability that the number of copies of a graph $H$ in $G$ exceeds its expectation by a factor $1+\delta$. Chatterjee and Dembo (2014) showed that in the sparse regime of $p \to 0$ as $ n\to \infty$ with $p$ bigger than an inverse power of $n$, this problem reduces to a natural variational problem on weighted graphs, which was thereafter asymptotically solved by two of the authors in the case where $H$ is a clique. Here we extend the latter work to any fixed graph $H$ and determine a function $c_H(\delta)$ such that, for $p$ as above and any fixed $\delta >0$, the logarithm of the upper tail probability properly normalized converges to cH(δ). As it turns out, the leading order constant in the large deviation rate function, $c_H(\delta)$, is governed by the independence polynomial of $H$.
Upper tails for arithmetic progressions in a random set.

(with with Bhaswar B. Bhattacharya, Xuancheng Shao, Yufei Zhao). To appear in International Mathematics Research Notices (2018). Arxiv

The second article investigates similar questions in the setting of counting arithmetic progressions in random subsets of $Z/nZ$ reducing large deviation questions to extremal problems in additive combinatorics.
Upper Tails for Edge Eigenvalues of Random Graphs.

(with Bhaswar B. Bhattacharya). To appear in SIDMA. Arxiv

In this note we prove a precise large deviation principle for the largest and second largest eigenvalues of a sparse Erdős-Rényi graph. Our arguments rely on various recent breakthroughs in the study of mean field approximations for large deviations of low complexity non-linear functions of independent Bernoulli variables and solutions of the associated entropic variational problems.
Spectral Edge in Sparse Random Graphs: Upper and Lower Tail Large Deviations.

(with Bhaswar B. Bhattacharya and Sohom Bhattacharya). To appear in Annals of Probability. Arxiv

n this paper we consider the problem of estimating the joint upper and lower tail large deviations of the edge eigenvalues of an Erdős-Rényi random graph $\mathcal{G}_{n,p}$, in the regime of p where the edge of the spectrum is no longer governed by global observables, such as the number of edges, but rather by localized statistics, such as high degree vertices. Going beyond the recent developments in mean-field approximations of related problems, this paper provides a comprehensive treatment of the large deviations of the spectral edge in this entire regime, which notably includes the well studied case of constant average degree. In particular, for $r\ge1$ fixed, we pin down the asymptotic probability that the top r eigenvalues are jointly greater/less than their typical values by multiplicative factors bigger/smaller than 1, in the regime mentioned above. The proof for the upper tail relies on a novel structure theorem, obtained by building on estimates of Krivelevich and Sudakov (2003), followed by an iterative cycle removal process, which shows, conditional on the upper tail large deviation event, with high probability the graph admits a decomposition in to a disjoint union of stars and a spectrally negligible part. On the other hand, the key ingredient in the proof of the lower tail is a Ramsey-type result which shows that if the K-th largest degree of a graph is not atypically small (for some large K depending on r), then either the top eigenvalue or the r-th largest eigenvalue is larger than that allowed by the lower tail event on the top r eigenvalues, thus forcing a contradiction. The above arguments reduce the problems to developing a large deviation theory for the extremal degrees which could be of independent interest.
Large deviations for the largest eigenvalue of Gaussian networks with constant average degree.

(with Kyeongsik Nam). Arxiv

Large deviation behavior of the largest eigenvalue $\lambda_1$ of Gaussian networks Erdős-Rényi random graphs $\mathcal{G}_{n,p}$ with i.i.d. Gaussian weights on the edges) has been the topic of considerable interest. In the recent works [6,30], a powerful approach was introduced based on tilting measures by suitable spherical integrals to prove a large deviation principle, particularly establishing a non-universal behavior for a fixed $p<1$ compared to the standard Gaussian ($p=1$) case. The case when $p\to 0$ was however completely left open {with one expecting the dense behavior to hold only until the average degree is logarithmic in $n$. In this article we focus on the case of constant average degree i.e., $p=\frac{d}{n}$ for some fixed $d>0$. Results on general non-homogeneous Gaussian matrices imply that in this regime $\lambda_1$ scales like $\sqrt{\log n}.$ We prove the following results towards a precise understanding of the large deviation behavior in this setting.

1. (Upper tail probabilities and structure theorem): For $\delta>0,$ we pin down the exact exponent $\psi(\delta)$ such that $\mathbb{P}(\lambda_1\ge \sqrt{2(1+\delta)\log n})=n^{-\psi(\delta)+o(1)}.$ Further, we show that conditioned on the upper tail event, with high probability, a unique maximal clique emerges with a very precise $\delta$ dependent size (takes either one or two possible values) and the Gaussian weights are uniformly high in absolute value on the edges in the clique. Finally, we also prove an optimal localization result for the leading eigenvector, showing that it allocates most of its mass on the aforementioned clique which is spread uniformly across its vertices.

2. (Lower tail probabilities): The exact stretched exponential behavior $\mathbb{P}(\lambda_1\le \sqrt{2(1-\delta)\log n})=\exp\left(-n^{\ell(\delta)+o(1)}\right)$ is also established.
As an immediate corollary, one obtains that $\lambda_1$ is typically $(1+o(1))\sqrt{2\log n}$, a result which surprisingly appears to be new. A key ingredient in our proofs is an extremal spectral theory for weighted graphs obtained by an $\ell_1-$reduction of the standard $\ell_2-$variational formulation of the largest eigenvalue via the classical Motzkin-Straus theorem, which could be of independent interest.

Polymer weight profile.

Time Correlation Exponents in Last Passage Percolation.

Illustrating overlap between polymers ending at (r,r) and (n,n)..

(with Riddhipratim Basu) Arxiv

For directed last passage percolation on ℤ2 with exponential passage times on the vertices, let $T_n$ denote the last passage time from $(0,0)$ to $(n,n)$. We consider asymptotic two point correlation functions of the sequence $T_n$. In particular we consider $Corr(T_n,T_r)$ for $r\le n$ where $r,n \to \infty$ with $r\ll n$ or $n−r\ll n$. We show that in the former case $Corr(T_n,T_r)=\Theta((r/n)^{1/3})$ whereas in the latter case $1−Corr(T_n,T_r)=\Theta(((n−r)/n)^{2/3})$. The argument revolves around finer understanding of polymer geometry and is expected to go through for a larger class of integrable models of last passage percolation. As by-products of the proof, we also get a couple of other results of independent interest: Quantitative estimates for locally Brownian nature of pre-limits of Airy$_2$ process coming from exponential LPP, and precise variance estimates for lengths of polymers constrained to be inside thin rectangles at the transversal fluctuation scale.
Temporal Correlation in Last Passage Percolation with Flat Initial Condition via Brownian Comparison.

(with Riddhipratim Basu and Lingfu Zhang) Arxiv

We consider directed last passage percolation on $\mathbb{Z}^2$ with exponential passage times on the vertices. A topic of great interest is the coupling structure of the weights of geodesics as the endpoints are varied spatially and temporally. A particular specialization is when one considers geodesics to points varying in the time direction starting from a given initial data. This paper considers the flat initial condition which corresponds to line-to-point last passage times. Settling a conjecture in \cite{FS16}, we show that for the passage times from the line $x+y=0$ to the points $(r,r)$ and $(n,n)$, denoted $X_{r}$ and $X_{n}$ respectively, as $n\to \infty$ and $\frac{r}{n}$ is small but bounded away from zero, the covariance satisfies $\mbox{Cov}(X_{r},X_{n})=\Theta\left((\frac{r}{n})^{4/3+o(1)} n^{2/3}\right),$ thereby establishing $\frac{4}{3}$ as the temporal covariance exponent. This differs from the corresponding exponent for the droplet initial condition recently rigorously established in \cite{FO18,BG18} and requires novel arguments. Key ingredients include the understanding of geodesic geometry and recent advances in quantitative comparison of geodesic weight profiles to Brownian motion using the Brownian Gibbs property. The proof methods are expected to be applicable for a wider class of initial data.

Fluctuation exponents, delocalization and large deviations of polymers.

The Competition of Roughness and Curvature in Area-Constrained Polymer Models .

(with Riddhipratim Basu, Alan Hammond) To appear in Communications in Mathematical Physics (2018).Arxiv

The competition between local Brownian roughness and global parabolic curvature experienced in many random interface models reflects an important aspect of the KPZ universality class. It may be summarised by an exponent triple (1/2,1/3,2/3) representing local interface fluctuation, local roughness (or inward deviation) and convex hull facet length. In the first article, we offer a new perspective on this phenomenon. We consider directed last passage percolation model in the plane, and constrain the maximizing path under the additional requirement of enclosing an atypically large area. We prove that the exponent triple is now (2/3,1/2,3/4). This phenomenon appears to be shared among various isoperimetrically extremal circuits in local randomness.
Delocalization of polymers in lower tail large deviation.

Illustrating overlap between polymers ending at (r,r) and (n,n).

(with Riddhipratim Basu, Allan Sly) To appear in Communications in Mathematical Physics (2019) Arxiv

We consider the large deviation regime, i.e., when the geodesic has much smaller (lower tail) or larger (upper tail) weight than typical. How the geometry of the geodesic changes under such a large deviation event was considered by Dueschel and Zeitouni (1998) where it was shown that the geodesic (from (0,0) to (n,n), say) remain concentrated around the straight line joining the end points in the upper tail large deviation regime, but left open the corresponding question in the lower tail. We answer their question by establishing a contrasting behaviour in the lower tail large deviation regime; we show that conditioned on the latter, in both the models, the geodesic is not concentrated around any deterministic curve.
Upper tail large deviations in First Passage Percolation.

(with Riddhipratim Basu, Allan Sly) Arxiv

We establish a precise large deviation principle for the upper tail in First passage percolation which had remained open since Kesten's seminal work in 1986 which established the asymptotic decay rate of probabilities.
Connecting Eigenvalue Rigidity with Polymer Geometry: Diffusive Transversal Fluctuations under Large Deviation.

(with Riddhipratim Basu) Arxiv

We consider the exactly solvable model of exponential directed last passage percolation on $\mathbb{Z}^2$ in the large deviation regime. Conditional on the upper tail large deviation event $U_{\delta}:=\{T_n\ge(4+\delta)n\}$ where $T_n$ denotes the last passage time from (1,1) to (n,n), we study the geometry of the polymer/geodesic $\Gamma_n$, i.e., the optimal path attaining $T_n$. We show that conditioning on $U_{\delta}$ changes the transversal fluctuation exponent from the characteristic 2/3 of the KPZ universality class to 1/2, i.e., conditionally, the smallest strip around the diagonal that contains $\Gamma_n$ has width $n^{1/2+o(1)}$ with high probability. This sharpens a result of Deuschel and Zeitouni (1999) who proved a $o(n)$ bound on the transversal fluctuation in the context of Poissonian last passage percolation, and complements (Basu, Ganguly, Sly, 2017), where the transversal fluctuation was shown to be $\Theta(n)$ in the lower tail large deviation event. Our proof exploits the correspondence between last passage times in the exponential LPP model and the largest eigenvalue of the Laguerre Unitary Ensemble (LUE) together with the determinantal structure of the spectrum of the latter. A key ingredient in our proof is a sharp refinement of the large deviation result for the largest eigenvalue (Seppäläinen '98, Johansson '99), using rigidity properties of the spectrum, which could be of independent interest.

Concentration of measure for Exponential Random Graphs.

Sub-critical exponential random graphs: concentration of measure and some applications.

(with Kyeongsik Nam) Arxiv

The exponential random graph model (ERGM) is a central object in the study of clustering properties in social networks as well as canonical ensembles in statistical physics. Despite some breakthrough works in the mathematical understanding of ERGM, most notably in (Bhamidi, Bresler, Sly, 2011), through the analysis of a natural Heat-bath Glauber dynamics and in (Chatterjee, Diaconis, 2013) and (Eldan, Gross, 2018), via a large deviation theoretic perspective, several basic questions have remained unanswered owing to the lack of exact solvability unlike the much studied Curie-Weiss model (Ising model on the complete graph). In this paper, we establish a series of new concentration of measure results for the ERGM $\textit{throughout the entire sub-critical phase}$, including a Poincare inequality, Gaussian concentration for Lipschitz functions, and a central limit theorem. In addition, partial results about exponential decay of entropy along Glauber dynamics and a new proof of a quantitative bound on the $W_1$−Wasserstein distance to Erdos-Renyi graphs, previously obtained in (Reinert, Ross, 2017), are also presented. The arguments rely on translating refined temporal mixing properties of Glauber dynamics to static spatial mixing properties of the equilibrium measure and have the potential of being useful in proving similar functional inequalities for other Gibbsian systems, beyond the perturbative regime..

Law of iterated logarithm for coupled polymer weights.

Lower Deviations in $\beta$-ensembles and Law of Iterated Logarithm in Last Passage Percolation.

(with Riddhipratim Basu, Milind Hegde and Manjunath Krishnapur). To appear in Israel Journal of Mathematics. Arxiv

For the last passage percolation (LPP) on $\mathbb{Z}^2$ with exponential passage times, let Tn denote the passage time from $(1,1)$ to $(n,n)$. We investigate the law of iterated logarithm of the sequence $\{T_n\}_{n\ge1}$; we show that $\liminf_{n\to \infty}\frac{T_n−4n}{n^{1/3}(\log\log n)^{1/3}}$ almost surely converges to a deterministic negative constant and obtain some estimates on the same. This settles a conjecture of Ledoux (J. Theor. Probab., 2018) where a related lower bound and similar results for the corresponding upper tail were proved. Our proof relies on a slight shift in perspective rom point-to-point passage times to considering point-to-line passage times instead, and exploiting the correspondence of the latter to the largest eigenvalue of the Laguerre Orthogonal Ensemble (LOE). A key technical ingredient, which is of independent interest, is a new lower bound of lower tail deviation probability of the largest eigenvalue of $\beta$-Laguerre ensembles, which extends the results proved in the context of the $\beta$-Hermite ensembles by Ledoux and Rider (Electron. J. Probab., 2010).

Rigidity of Coulomb gases.

Ground States And Hyperuniformity Of The Hierarchical Coulomb Gas In All Dimensions.

(with Sourav Sarkar) To appear in Probab. Theory and Related Fields. Arxiv

Stochastic point processes with Coulomb interactions arise in various natural examples of statistical mechanics, random matrices and optimization problems. Often such systems due to their natural repulsion exhibit remarkable hyperuniformity properties, that is, the number of points landing in any given region fluctuates at a much smaller scale compared to that of a set of i.i.d. random points. A well known conjecture from physics appearing in the works of Jancovici, Lebowitz, Manificat, Martin, and Yalcin ('80,'83,'93), states that the variance of the number of points landing in a set should grow like the surface area instead of the volume unlike i.i.d. random points. In a recent beautiful work, Chatterjee (2017) gave the first proof of such a result in dimension three for a Coulomb type system, known as the hierarchical Coulomb gas, inspired by Dyson's hierarchical model of the Ising ferromagnet. However the case of dimensions greater than three had remained open. In this paper, we establish the correct fluctuation behavior up to logarithmic factors in all dimensions greater than three, for the hierarchical model. Using similar methods, we also prove sharp variance bounds for smooth linear statistics which were unknown in any dimension bigger than two. A key intermediate step is to obtain precise results about the ground states of such models whose behavior can be interpreted as hierarchical analogues of various crystalline conjectures predicted for energy minimizing systems, and could be of independent interest.

Self Avoiding Walks.

Bounding the number of self-avoiding walks: Hammersley-Welsh with polygon insertion.

Figure illustrating the key geometric strategy to beat Hammersley-Welsh by inserting polygons into a SAW in a way that the latter can be recovered. The entropy in the location of the attachement then is enough to beat the classical exp(n^{1/2)) HW term.

(with Hugo Duminil-Copin, Alan Hammond, Ioan Manolescu). To appear in Annals of Probability Arxiv

Let $c_n=c_n(d)$ denote the number of self-avoiding walks of length n starting at the origin in the Euclidean nearest-neighbour lattice $\mathbb{Z}^d$. Let $\mu$ denote the connective constant of $\mathbb{Z}^d$. In 1962, Hammersley and Welsh [HW62] proved that, for each $d\ge 2$, there exists a constant $C>0$ such that $c_n \le \exp(Cn^{1/2})\mu^n$ for all $n \in \mathbb{N}$. While it is anticipated that $c_n \mu^{(−n)}$ has a power-law growth in $n$, the best known upper bound in dimension two has remained of the form $n^{(1/2)}$ inside the exponential. We consider two planar lattices and prove that $c_n \le \exp(Cn^{(1/2−\epsilon)})\mu^n$ for an explicit constant $\epsilon>0$ (where here $\mu$ denotes the connective constant for the lattice in question). The result is conditional on a lower bound on the number of self-avoiding polygons of length $n$, which is proved to hold on the hexagonal lattice $\mathbb{H}$ for all $n$, and subsequentially in $n$ for $\mathbb{Z}^2$. A power-law upper bound on $c_n \mu^{(−n)}$ for $\mathbb{H}$ is also proved, contingent on a non-quantitative assertion concerning this lattice's connective constant.

Eigenvectors of high girth graphs.

On Non-localization of Eigenvectors of High Girth Graphs.

(with Nikhil Srivastava) To appear in International Mathematics Research Notices. Arxiv

We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.
High-girth near-Ramanujan graphs with localized eigenvectors.

(with Nogal Alon, Nikhil Srivastava). Arxiv

We show that for every prime $d$ and $\alpha \in (0,1/6)$, there is an infinite sequence of $(d+1)$-regular graphs $G=(V,E)$ with girth at least $2\alpha \log_d|V|(1−o_{d}(1))$, second adjacency matrix eigenvalue bounded by $(3/2)\sqrt{d}$, and many eigenvectors fully localized on small sets of size $O(|V|^{\alpha})$. This strengthens the results of Ganguly-Srivastava, who constructed high girth (but not expanding) graphs with similar properties, and may be viewed as a discrete analogue of the "scarring" phenomenon observed in the study of quantum ergodicity on manifolds. Key ingredients in the proof are a technique of Kahale for bounding the growth rate of eigenfunctions of graphs, discovered in the context of vertex expansion and a method of Erdős and Sachs for constructing high girth regular graphs.

Gibbs measure on Random Matrices and Lattice gauge theory.

$SO(N)$ Lattice Gauge Theory, Planar and Beyond .

(with Riddhipratim Basu) To appear in Communications on Pure and Applied Mathematics (2017). Arxiv

Lattice Gauge theories have been studied in the physics literature as discrete approximations to quantum Yang-Mills theory for a long time. Primary statistics of interest in these models are expectations of the so called “Wilson loop variables”. In this article we continue the program initiated by Chatterjee (2015) to understand Wilson loop expectations in Lattice Gauge theories in a certain limit through gauge-string duality. The objective in this paper is to better understand the underlying combinatorics in the strong coupling regime, by giving a more geometric picture of string trajectories involving correspondence to objects such as decorated trees and non-crossing partitions. Using connections with Free Probability theory, we provide an elaborate description of loop expectations in the the planar setting, which provides certain insights about structures of higher dimensional trajectories as well. Exploiting this, we construct a counter example showing that in any dimension, the Wilson loop area law lower bound does not hold in full generality.

Competitive Erosion.

Interface formation by Competitive Erosion.

(with Lionel Levine, Yuval Peres and James Propp) To appear in PTRF (2016) Arxiv

We study a graph-theoretic model of interface dynamics called Competitive Erosion. Each vertex of the graph is occupied by a particle, which can be either red or blue. New red and blue particles are emitted alternately from their respective bases and perform random walk. On encountering a particle of the opposite color they remove it and occupy its position. Based on conformally invariant nature of reflected brownian motion Propp conjectured in 2003 that at stationarity, with high probability the blue and the red regions are separated by an orthogonal circular arc on the disc and by a suitable hyperbolic geodesic on a general simply connected domain.
Competitive erosion is conformally invariant.

Competitive erosion started from a random coloring spontaneously forms an interface.

(with Yuval Peres) To appear in Communications in Mathematical Physics (2018) Arxiv

We confirm Propp's prediction on smooth enough planar simply connected domains.
Formation of large scale random structure by competitive erosion.

(with Lionel Levine and Sourav Sarkar) To appear in Annals of Probability (2019) Arxiv

we study a variant on the line with the same source for both the particles which exhibit a random interface dynamics unlike the former cases. We describe the fractal properties of the clusters by extremal functionals of a one dimensional Brownian motion.

Self organized criticality.

Non-fixation for conservative stochastic dynamics on the line.

(with Riddhipratim Basu, Christopher Hoffman). To appear in Communications in Mathematical Physics (2017). Arxiv

We consider Activated Random Walk (ARW), a model which generalizes the Stochastic Sandpile, one of the canonical examples of self organized criticality. Informally ARW is a particle system on Z, with initial mass density μ > 0 of active particles. Active particles do a symmetric random walk at rate one and fall asleep at rate λ > 0. Sleepy particles become active on coming in contact with other active particles. We investigate the question of fixation/non-fixation of the process and show for small enough λ the critical mass density for fixation is strictly less than one. Moreover, the critical density goes to zero as λ tends to zero. This positively answers two open questions from Dickman, Rolla, Sidoravicius (J. Stat. Phys., 2010) and Rolla, Sidoravicius (Invent. Math., 2012).
Activated Random walk on a cycle.

(with Riddhipratim Basu, Christopher Hoffman and Jacob Richey).To appear in AIHP (2018). Arxiv

Quantitative analogues of the results of the first paper are proved considering ARW on a cycle.

Mixing time of Markov chains.

Information Percolation and Cutoff for the Random-Cluster Model.

Figure illustrating the key geometric strategy to beat Hammersley-Welsh by inserting polygons into a SAW in a way that the latter can be recovered. The entropy in the location of the attachement then is enough to beat the classical exp(n^{1/2)) HW term.

(with Insuk Seo) To appear in Random Structures and Algorithms. Arxiv

We consider the Random-Cluster model on $(\mathbb{Z}/n\mathbb{Z})^d$ with parameters $p\in(0,1)$ and $q \ge 1$. This is a generalization of the standard bond percolation (with open probability $p$) which is biased by a factor q raised to the number of connected components. We study the well known FK-dynamics on this model where the update at an edge depends on the global geometry of the system unlike the Glauber Heat Bath dynamics for spin systems, and prove that for all small enough $p$ (depending on the dimension) and any $q>1$, the FK-dynamics exhibits the cutoff phenomenon at $\lambda_\infty \log n$ with a window size $O(\log\log n)$, where $\lambda_\infty$ is the large n limit of the spectral gap of the process. Our proof extends the Information Percolation framework of Lubetzky and Sly to the Random-Cluster model and also relies on the arguments of Blanca and Sinclair who proved a sharp O(logn) mixing time bound for the planar version. A key aspect of our proof is the analysis of the effect of a sequence of dependent (across time) Bernoulli percolations extracted from the graphical construction of the dynamics, on how information propagates.
Cutoff for the East Process.

(with Eyal Lubetzky and Fabio Martinelli) Communications in Mathematical Physics (2015). Arxiv

The East process is a 1D kinetically constrained interacting particle system, introduced in the physics literature in the early 90's to model liquid-glass transitions. Spectral gap estimates of Aldous and Diaconis in 2002 imply that its mixing time on L sites has order L. We complement that result and show cutoff with an O(√L)-window. Finally, we supplement these results by a study of analogous kinetically constrained models on trees, again establishing cutoff, yet this time with an O(1)-window.
Upper triangular matrix walk: cutoff for finitely many columns.

(with Fabio Martinelli) To appear in Random Structures and Algorithms (2018). Arxiv

In the second article we consider random walk on the group of uni-upper triangular matrices with entries in F_2 which forms an important example of a nilpotent group. Peres and Sly (2013) proved tight bounds on the mixing time of this walk up to constants. It is well known that the single column projection of this chain is the one dimensional East process. In this article, we complement the Peres-Sly result by proving a cutoff result for the mixing of finitely many columns in the upper triangular matrix walk at the same location as the East process of the same dimension. Moreover, we also show that the spectral gaps of the matrix walk and the East process are equal.