BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Shirshendu Ganguly

Shirshendu Ganguly appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.PRmath.COmath-phmath.MPcond-mat.stat-mechDiscrete Mathematicsmath.OAGenomicsInformation Theorymath.APmath.CVmath.ITmath.MGmath.STStatistics Theory

Catalog footprint

What is connected

27works
15topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

27 published item(s)

preprint2026arXiv

van den Berg-Kesten--type correlation inequalities for disjoint polymers in the KPZ universality class

In classical percolation theory, the van den Berg-Kesten (BK) inequality is a fundamental tool that shows that disjoint events induce negative conditionings on each other. The inequality also holds in the context of last passage percolation (LPP), which is the zero temperature limit of polymer models and an important subclass in the Kardar-Parisi-Zhang (KPZ) universality class. Recently, an analog of the BK inequality was discovered in the context of zero temperature line ensembles and the scaling limit of LPP, where it was used to study upper tail probabilities of the weight and the scaling limit of geodesics under such upper tail conditionings. However, while it has become apparent that such an inequality in the positive temperature setting would have a number of applications, it seems likely that a direct generalization of the zero temperature inequality would not hold. In this work we prove a version of the BK inequality for the KPZ line ensemble and the continuum directed random polymer. We do so by working with the log gamma polymer, making use of its integrability and the geometric RSK correspondence. Our inequality serves as a key input in analyzing the KPZ line ensemble and proving sharp upper tail estimates of the KPZ equation in arXiv:2208.08922, and proving convergence of the continuum directed random polymer to Brownian bridge under the upper tail event in arXiv:2311.12009. The crucial role of integrability in the validity of such an inequality is highlighted via a counter-example for a non-integrable model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

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

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 $(\pm 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.$

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Spectral large deviations of sparse random matrices

Eigenvalues of Wigner matrices has been a major topic of investigation. A particularly important subclass of such random matrices is formed by the adjacency matrix of an Erdős-Rényi graph $\mathcal{G}_{n,p}$ equipped with i.i.d. edge-weights. An observable of particular interest is the largest eigenvalue. In this paper, we study the large deviations behavior of the largest eigenvalue of such matrices, a topic that has received considerable attention over the years. We focus on the case $p = \frac{d}{n}$, where most known techniques break down. So far, results were known only for $\mathcal{G}_{n,\frac{d}{n}}$ without edge-weights (Krivelevich and Sudakov, '03), (Bhattacharya, Bhattacharya, and Ganguly, '21) and with Gaussian edge-weights (Ganguly and Nam, '21). In the present article, we consider the effect of general weight distributions. More specifically, we consider the entries whose tail probabilities decay at rate $e^{-t^α}$ with $α>0$, where the regimes $0<α<2$ and $α>2$ correspond to tails heavier and lighter than the Gaussian tail respectively. While in many natural settings the large deviations behavior is expected to depend crucially on the entry distribution, we establish a surprising and rare universal behavior showing that this is not the case when $α> 2.$ In contrast, in the $α< 2$ case, the large deviation rate function is no longer universal and is given by the solution to a variational problem, the description of which involves a generalization of the Motzkin-Straus theorem, a classical result from spectral graph theory. As a byproduct of our large deviation results, we also establish new law of large numbers results for the largest eigenvalue. In particular, we show that the typical value of the largest eigenvalue exhibits a phase transition at $α= 2$, i.e. the Gaussian distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Upper tail behavior of the number of triangles in random graphs with constant average degree

Let $N$ be the number of triangles in an Erdős-Rényi graph $\mathcal{G}(n,p)$ on $n$ vertices with edge density $p=d/n,$ where $d>0$ is a fixed constant. It is well known that $N$ weakly converges to the Poisson distribution with mean ${d^3}/{6}$ as $n\rightarrow \infty$. We address the upper tail problem for $N,$ namely, we investigate how fast $k$ must grow, so that the probability of $\{N\ge k\}$ is not well approximated anymore by the tail of the corresponding Poisson variable. Proving that the tail exhibits a sharp phase transition, we essentially show that the upper tail is governed by Poisson behavior only when $k^{1/3} \log k< (\frac{3}{\sqrt{2}})^{2/3} \log n$ (sub-critical regime) as well as pin down the tail behavior when $k^{1/3} \log k> (\frac{3}{\sqrt{2}})^{2/3} \log n$ (super-critical regime). We further prove a structure theorem, showing that the sub-critical upper tail behavior is dictated by the appearance of almost $k$ vertex-disjoint triangles whereas in the supercritical regime, the excess triangles arise from a clique like structure of size approximately $(6k)^{1/3}$. This settles the long-standing upper-tail problem in this case, answering a question of Aldous, complementing a long sequence of works, spanning multiple decades, culminating in (Harel, Moussat, Samotij,'19) which analyzed the problem only in the regime $p\gg \frac{1}{n}.$ The proofs rely on several novel graph theoretical results which could have other applications.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Large deviations for the largest eigenvalue of Gaussian networks with constant average degree

Large deviation behavior of the largest eigenvalue $λ_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. Recently in [6,30], a powerful approach was introduced based on tilting measures by suitable spherical integrals, particularly establishing a non-universal large deviation behavior for 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}$. We prove the following results towards a precise understanding of the large deviation behavior in this setting. 1. (Upper tail probabilities): For $δ>0,$ we pin down the exact exponent $ψ(δ)$ such that $$\mathbb{P}(λ_1\ge \sqrt{2(1+δ)\log n})=n^{-ψ(δ)+o(1)}.$$ Further, we show that conditioned on the upper tail event, with high probability, a unique maximal clique emerges with a very precise $δ$ 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 of $\mathbb{P}(λ_1\le \sqrt{2(1-δ)\log n})$ is also established. As an immediate corollary, we get $λ_1 \approx \sqrt{2 \log n}$ typically, a result that surprisingly appears to be new. A key ingredient is an extremal spectral theory for weighted graphs obtained via the classical Motzkin-Straus theorem.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

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

Consider the Ising model at low-temperatures and positive external field $λ$ on an $N\times N$ box with Dobrushin boundary conditions that are plus on the north, east, and west boundaries and minus on the south boundary. If $λ= 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 $λ_N \downarrow 0$, where the height fluctuations are expected to scale as $λ^{ -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^{ - Θ(x^{3/2})}$ upper tails reminiscent of the Tracy--Widom distribution, capturing a tradeoff between the locally Brownian oscillations and the global field effect. We further prove a concentration estimate for the number of points above which the interface attains a large height. These are used to deduce various geometric properties of the interface, including the order and tails of the area it confines, and the poly-logarithmic pre-factor governing its maximum height fluctuation. Our arguments combine classical inputs from the random-line representation of the Ising interface, with novel local resampling and coupling schemes.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Temporal Correlation in Last Passage Percolation with Flat Initial Condition via Brownian Comparison

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 by Ferrari and Spohn (SIGMA, 2016), 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})=Θ\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 Ferrari and Occelli (2018), Basu and Ganguly (2018), 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Information Percolation and Cutoff for the Random-Cluster Model

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 $λ_{\infty}^{-1}\log n$ with a window size $O(\log\log n)$, where $λ_{\infty}$ is the large $n$ limit of the spectral gap of the process. Our proof extends the Information Percolation framework of Lubetzky and Sly [21] to the Random-Cluster model and also relies on the arguments of Blanca and Sinclair [4] who proved a sharp $O(\log n)$ 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Interlacing and scaling exponents for the geodesic watermelon in last passage percolation

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 $μ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 $μnk$ by order $k^{5/3}n^{1/3}$, and its transversal fluctuation is of order $k^{1/3}n^{2/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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Recovery and Rigidity in a Regular Stochastic Block Model

The stochastic block model is a natural model for studying community detection in random networks. Its clustering properties have been extensively studied in the statistics, physics and computer science literature. Recently this area has experienced major mathematical breakthroughs, particularly for the binary (two-community) version, see Mossel, Neeman, Sly (2012, 2013) and Massoulie (2013). In this paper, we introduce a variant of the binary model which we call the regular stochastic block model (RSBM). We prove rigidity by showing that with high probability an exact recovery of the community structure is possible. Spectral methods exhibit a regime where this can be done efficiently. Moreover we also prove that, in this setting, any suitably good partial recovery can be bootstrapped to obtain a full recovery of the communities.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Spectral Edge in Sparse Random Graphs: Upper and Lower Tail Large Deviations

In 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 \geq 1$ 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Consistent nonparametric estimation for heavy-tailed sparse graphs

We study graphons as a non-parametric generalization of stochastic block models, and show how to obtain compactly represented estimators for sparse networks in this framework. Our algorithms and analysis go beyond previous work in several ways. First, we relax the usual boundedness assumption for the generating graphon and instead treat arbitrary integrable graphons, so that we can handle networks with long tails in their degree distributions. Second, again motivated by real-world applications, we relax the usual assumption that the graphon is defined on the unit interval, to allow latent position graphs where the latent positions live in a more general space, and we characterize identifiability for these graphons and their underlying position spaces. We analyze three algorithms. The first is a least squares algorithm, which gives an approximation we prove to be consistent for all square-integrable graphons, with errors expressed in terms of the best possible stochastic block model approximation to the generating graphon. Next, we analyze a generalization based on the cut norm, which works for any integrable graphon (not necessarily square-integrable). Finally, we show that clustering based on degrees works whenever the underlying degree distribution is atomless. Unlike the previous two algorithms, this third one runs in polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Diffusive estimates for random walks on stationary random graphs of polynomial growth

Let $(G,ρ)$ be a stationary random graph, and use $B^G_ρ(r)$ to denote the ball of radius $r$ about $ρ$ in $G$. Suppose that $(G,ρ)$ has annealed polynomial growth, in the sense that $\mathbb{E}[|B^G_ρ(r)|] \leq O(r^k)$ for some $k > 0$ and every $r \geq 1$. Then there is an infinite sequence of times $\{t_n\}$ at which the random walk $\{X_t\}$ on $(G,ρ)$ is at most diffusive: Almost surely (over the choice of $(G,ρ)$), there is a number $C > 0$ such that \[ \mathbb{E} \left[\mathrm{dist}_G(X_0, X_{t_n})^2 \mid X_0 = ρ, (G,ρ)\right]\leq C t_n\qquad \forall n \geq 1\,. \] 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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Sequence assembly from corrupted shotgun reads

The prevalent technique for DNA sequencing consists of two main steps: shotgun sequencing, where many randomly located fragments, called reads, are extracted from the overall sequence, followed by an assembly algorithm that aims to reconstruct the original sequence. There are many different technologies that generate the reads: widely-used second-generation methods create short reads with low error rates, while emerging third-generation methods create long reads with high error rates. Both error rates and error profiles differ among methods, so reconstruction algorithms are often tailored to specific shotgun sequencing technologies. As these methods change over time, a fundamental question is whether there exist reconstruction algorithms which are robust, i.e., which perform well under a wide range of error distributions. Here we study this question of sequence assembly from corrupted reads. We make no assumption on the types of errors in the reads, but only assume a bound on their magnitude. More precisely, for each read we assume that instead of receiving the true read with no errors, we receive a corrupted read which has edit distance at most $ε$ times the length of the read from the true read. We show that if the reads are long enough and there are sufficiently many of them, then approximate reconstruction is possible: we construct a simple algorithm such that for almost all original sequences the output of the algorithm is a sequence whose edit distance from the original one is at most $O(ε)$ times the length of the original sequence.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Upper triangular matrix walk: Cutoff for finitely many columns

We consider random walk on the group of uni-upper triangular matrices with entries in $\mathbb{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. The proof of the cutoff result is based on a recursive argument which uses a local version of a dual process appearing in Peres and Sly (2013), various combinatorial consequences of mixing and concentration results for the movement of the front in the one dimensional East process.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Convergence of discrete Green functions with Neumann boundary conditions

In this note we prove convergence of Green functions with Neumann boundary conditions for the random walk to their continuous counterparts. Also a few Beurling type hitting estimates are obtained for the random walk on discretizations of smooth domains. These have been used recently in the study of a two dimensional competing aggregation system known as $Competitive\, Erosion$. Some of the statements appearing in this note are classical for ${\mathbb{Z}}^2$. However additional arguments are needed for the proofs in the bounded geometry setting.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Formation of an interface by competitive erosion

In 2006, the fourth author proposed a graph-theoretic model of interface dynamics called competitive erosion. Each vertex of the graph is occupied by a particle that can be either red or blue. New red and blue particles alternately get emitted from their respective bases and perform random walk. On encountering a particle of the opposite color they kill it and occupy its position. We prove that on the cylinder graph (the product of a path and a cycle) an interface spontaneously forms between red and blue and is maintained in a predictable position with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Heat diffusion with frozen boundary

Consider "Frozen Random Walk" on $\mathbb{Z}$: $n$ particles start at the origin. At any discrete time, the leftmost and rightmost $\lfloor{\frac{n}{4}}\rfloor$ particles are "frozen" and do not move. The rest of the particles in the "bulk" independently jump to the left and right uniformly. The goal of this note is to understand the limit of this process under scaling of mass and time. To this end we study the following deterministic mass splitting process: start with mass $1$ at the origin. At each step the extreme quarter mass on each side is "frozen". The remaining "free" mass in the center evolves according to the discrete heat equation. We establish diffusive behavior of this mass evolution and identify the scaling limit under the assumption of its existence. It is natural to expect the limit to be a truncated Gaussian. A naive guess for the truncation point might be the $1/4$ quantile points on either side of the origin. We show that this is not the case and it is in fact determined by the evolution of the second moment of the mass distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Cutoff for the East process

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(\sqrt{L})$-window. The main ingredient is an analysis of the front of the process (its rightmost zero in the setup where zeros facilitate updates to their right). One expects the front to advance as a biased random walk, whose normal fluctuations would imply cutoff with an $O(\sqrt{L})$-window. The law of the process behind the front plays a crucial role: Blondel showed that it converges to an invariant measure $ν$, on which very little is known. Here we obtain quantitative bounds on the speed of convergence to $ν$, finding that it is exponentially fast. We then derive that the increments of the front behave as a stationary mixing sequence of random variables, and a Stein-method based argument of Bolthausen ('82) implies a CLT for the location of the front, yielding the cutoff result. 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Oil and water: a two-type internal aggregation model

We introduce a two-type internal DLA model which is an example of a non-unary abelian network. Starting with n "oil" and n "water" particles at the origin, the particles diffuse in Z according to the following rule: whenever some site x has at least 1 oil and at least 1 water particle present, it "fires" by sending 1 oil particle and 1 water particle each to an independent random neighbor x+1 or x-1. Firing continues until every site has at most one type of particles. We establish the correct order for several statistics of this model and identify the scaling limit under assumption of existence.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Permuted Random Walk Exits Typically in Linear Time

Given a permutation sigma of the integers {-n,-n+1,...,n} we consider the Markov chain X_{sigma}, which jumps from k to sigma (k\pm 1) equally likely if k\neq -n,n. We prove that the expected hitting time of {-n,n} starting from any point is Theta(n) with high probability when sigma is a uniformly chosen permutation. We prove this by showing that with high probability, the digraph of allowed transitions is an Eulerian expander; we then utilize general estimates of hitting times in directed Eulerian expanders.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Random Transposition Dynamics on Random Regular Graphs and the Gaussian Free Field

A single permutation, seen as union of disjoint cycles, represents a regular graph of degree two. Consider $d$ many independent random permutations and superimpose their graph structures. It is a common model of a random regular (multi-) graph of degree $2d$. We consider the following dynamics. The dimension (i.e. size) of each permutation grows by coupled Chinese Restaurant Processes, while in time each permutation evolves according to the random transposition chain. Asymptotically in the size of the graph one observes a remarkable evolution of short cycles and linear eigenvalue statistics in dimension and time. In dimension, it was shown by Johnson and Pal (2014) that cycle counts are described by a Poisson field of Yule processes. Here, we give a Poisson random surface description in dimension and time of the limiting cycle counts for every $d$. As $d$ grows to infinity, the fluctuation of the limiting cycle counts, across dimension, converges to the Gaussian Free Field. In time this field is preserved by a stationary Gaussian dynamics. The laws of these processes are similar to eigenvalue fluctuations of the minor process of a real symmetric Wigner matrix whose coordinates evolve as i.i.d. stationary stochastic processes.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Joint convergence of several copies of different patterned random matrices

We study the joint convergence of independent copies of several patterned matrices in the noncommutative probability setup. In particular, joint convergence holds for the well known Wigner, Toeplitz, Hankel, reverse circulant and symmetric circulant matrices. We also study some properties of the limits. In particular, we show that copies of Wigner becomes asymptotically free with copies of any of the above other matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Minimum-Weight Edge Discriminator in Hypergraphs

In this paper we introduce the concept of minimum-weight edge-discriminators in hypergraphs, and study its various properties. For a hypergraph $\mathcal H=(\mathcal V, \mathcal E)$, a function $λ: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\}$ is said to be an {\it edge-discriminator} on $\mathcal H$ if $\sum_{v\in E_i}{λ(v)}>0$, for all hyperedges $E_i\in \mathcal E$, and $\sum_{v\in E_i}{λ(v)}\ne \sum_{v\in E_j}{λ(v)}$, for every two distinct hyperedges $E_i, E_j \in \mathcal E$. An {\it optimal edge-discriminator} on $\mathcal H$, to be denoted by $λ_\mathcal H$, is an edge-discriminator on $\mathcal H$ satisfying $\sum_{v\in \mathcal V}λ_\mathcal H (v)=\min_λ\sum_{v\in \mathcal V}{λ(v)}$, where the minimum is taken over all edge-discriminators on $\mathcal H$. We prove that any hypergraph $\mathcal H=(\mathcal V, \mathcal E)$, with $|\mathcal E|=n$, satisfies $\sum_{v\in \mathcal V} λ_\mathcal H(v)\leq n(n+1)/2$, and equality holds if and only if the elements of $\mathcal E$ are mutually disjoint. For $r$-uniform hypergraphs $\mathcal H=(\mathcal V, \mathcal E)$, it follows from results on Sidon sequences that $\sum_{v\in \mathcal V}λ_{\mathcal H}(v)\leq |\mathcal V|^{r+1}+o(|\mathcal V|^{r+1})$, and the bound is attained up to a constant factor by the complete $r$-uniform hypergraph. Next, we construct optimal edge-discriminators for some special hypergraphs, which include paths, cycles, and complete $r$-partite hypergraphs. Finally, we show that no optimal edge-discriminator on any hypergraph $\mathcal H=(\mathcal V, \mathcal E)$, with $|\mathcal E|=n (\geq 3)$, satisfies $\sum_{v\in \mathcal V} λ_\mathcal H (v)=n(n+1)/2-1$, which, in turn, raises many other interesting combinatorial questions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Spectral properties of random triangular matrices

We prove the existence of the limiting spectral distribution (LSD) of symmetric triangular patterned matrices and also establish the joint convergence of sequences of such matrices. For the particular case of the symmetric triangular Wigner matrix, we derive expression for the moments of the LSD using properties of Catalan words. The problem of deriving explicit formulae for the moments of the LSD does not seem to be easy to solve for other patterned matrices. The LSD of the non-symmetric triangular Wigner matrix also does not seem to be easy to establish.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Limiting Spectral Distribution of Block Matrices with Toeplitz Block Structure

We study two specific symmetric random block Toeplitz (of dimension $k \times k$) matrices: where the blocks (of size $n \times n$) are (i) matrices with i.i.d. entries, and (ii) asymmetric Toeplitz matrices. Under suitable assumptions on the entries, their limiting spectral distributions (LSDs) exist (after scaling by $\sqrt{nk}$) when (a) $k$ is fixed and $n \to\infty$ (b) $n$ is fixed and $k\rightarrow \infty$ (c) $n$ and $k$ go to $\infty$ simultaneously. Further the LSD's obtained in (a) and (b) coincide with those in (c) when $n$ or respectively $k$ tends to infinity. This limit in (c) is the semicircle law in case (i). In Case (ii) the limit is related to the limit of the random symmetric Toepiltz matrix as obtained by Bryc et al.(2006) and Hammond and Miller(2005).

0 citations0 reviewsNo code linkedOpen access