# Shirshendu Ganguly

I am an Assistant 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.

## Education and past employment.

• UC Berkeley. Miller Postdoctoral Fellow. Statistics and Mathematics. 2016-2018.
• University of Washington. PhD in Mathematics. 2011-2016. Advised by Ioana Dumitriu and Chris Hoffman .
• Microsoft Research. Summer Internships. 2013,2014,2015.
• Indian Statistical Institute, Kolkata. BStat.2006-2009. MStat. 2009-2011.

## Recent Works

### Self Avoiding Walks.

• (with Hugo Duminil-Copin, Alan Hammond, Ioan Manolescu) 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 ℤ^d. Let μ denote the connective constant of ℤd. In 1962, Hammersley and Welsh [HW62] proved that, for each d≥2, there exists a constant C>0 such that c_n≤exp(Cn^1/2)μ^n for all n∈ℕ. While it is anticipated that c_nμ^(−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≤exp(Cn^(1/2−ϵ))μ^n for an explicit constant ϵ>0 (where here μ 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 ℍ for all n, and subsequentially in n for ℤ2. A power-law upper bound on cnμ−n for ℍ is also proved, contingent on a non-quantitative assertion concerning this lattice's connective constant.

### Polymer weight profile.

• (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≤n where r,n→∞ with r≪n or n−r≪n. We show that in the former case Corr(T_n,T_r)=Θ((r/n)^1/3) whereas in the latter case 1−Corr(T_n,T_r)=Θ(((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 Airy2 process coming from exponential LPP, and precise variance estimates for lengths of polymers constrained to be inside thin rectangles at the transversal fluctuation scale.

### 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.

### Fluctuation exponents, delocalization and large deviations of polymers.

• (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.

• (with Riddhipratim Basu, Allan Sly) 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.

• (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.

• (with Riddhipratim Basu) Arxiv

We consider the exactly solvable model of exponential directed last passage percolation on ℤ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.

### Random walk on stationary graphs.

• (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.

### Gibbs measure on Random Matrices and Lattice gauge theory.

• (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.

• (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.

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

We confirm Propp's prediction on smooth enough planar simply connected domains.

• (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.

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

• (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$$.

• (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.

• (with Bhaswar B. Bhattacharya) 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.

### Self organized criticality.

• (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).

• (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.

• (with Insuk Seo) 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.

• (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.

• (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.