Search

In gossip networks, a source node forwards time-stamped updates to a network of observers according to a Poisson process. The observers then update each other on this information according to Poisson processes as well. The Age of Information (AoI) of a given node is the difference between the current time and the most recent time-stamp of source information that the node has received. We provide a method for evaluating the AoI of a node in terms of first passage percolation. We then use this distributional identity to prove matching upper and lower bounds on the AoI in terms of connectivity properties of the underlying network. In particular, if one sets $X_v$ to be the AoI of node $v$ on a finite graph $G$ with $n$ nodes, then we define $m_\ast = \min\{m : m \cdot |B_m(v)| \geq n\}$ where $B_m(v)$ is the ball of radius $m$ in $G$. In the case when the maximum degree of $G$ is bounded by $\Delta$ we prove $\mathbb{E} X_v = \Theta_\Delta(m_\ast)$. As corollaries, we solve multiple open problems in the literature such as showing the age of information on a subset of $\mathbb{Z}^d$ is $\Theta(n^{1/(d+1)})$. We also demonstrate examples of graphs with AoI scaling like $n^{\alpha}$ for each $\alpha \in (0,1/2)$. These graphs are not vertex-transitive and in fact we show that if one considers the AoI on a graph coming from a vertex-transitive infinite graph then either $\mathbb{E} X_v = \Theta(n^{1/k})$ for some integer $k \geq 2$ or $\mathbb{E} X_v = n^{o(1)}$., Comment: 12 pages

A result of Deza, Levin, Meesum, and Onn shows that the problem of deciding if a given sequence is the degree sequence of a 3-uniform hypergraph is NP complete. We tackle this problem in the random case and show that a random integer partition can be realized as the degree sequence of a $3$-uniform hypergraph with high probability. These results are in stark contrast with the case of graphs, where a classical result of Erd\H{o}s and Gallai provides an efficient algorithm for checking if a sequence is a degree sequence of a graph and a result of Pittel shows that with high probability a random partition is not the degree sequence of a graph. By the same method, we address analogous realizability problems about high-dimensional binary contingency tables. We prove that if $(\lambda,\mu,\nu)$ are three independent random partitions then with high probability one can construct a three-dimensional binary contingency table with marginals $(\lambda,\mu,\nu)$. Conversely, if one insists that the contingency table forms a pyramid shape, then we show that with high probability one cannot construct such a contingency table. These two results confirm two conjectures of Pak and Panova., Comment: 15 pages; comments welcome!

Consider a bipartite quantum system, where Alice and Bob jointly possess a pure state $|\psi\rangle$. Using local quantum operations on their respective subsystems, and unlimited classical communication, Alice and Bob may be able to transform $|\psi\rangle$ into another state $|\phi\rangle$. Famously, Nielsen's theorem [Phys. Rev. Lett., 1999] provides a necessary and sufficient algebraic criterion for such a transformation to be possible (namely, the local spectrum of $|\phi\rangle$ should majorise the local spectrum of $|\psi\rangle$). In the paper where Nielsen proved this theorem, he conjectured that in the limit of large dimensionality, for almost all pairs of states $|\psi\rangle, |\phi\rangle$ (according to the natural unitary invariant measure) such a transformation is not possible. That is to say, typical pairs of quantum states $|\psi\rangle, |\phi\rangle$ are entangled in fundamentally different ways, that cannot be converted to each other via local operations and classical communication. Via Nielsen's theorem, this conjecture can be equivalently stated as a conjecture about majorisation of spectra of random matrices from the so-called trace-normalised complex Wishart-Laguerre ensemble. Concretely, let $X$ and $Y$ be independent $n \times m$ random matrices whose entries are i.i.d. standard complex Gaussians; then Nielsen's conjecture says that the probability that the spectrum of $X X^\dagger / \operatorname{tr}(X X^\dagger)$ majorises the spectrum of $Y Y^\dagger / \operatorname{tr}(Y Y^\dagger)$ tends to zero as both $n$ and $m$ grow large. We prove this conjecture, and we also confirm some related predictions of Cunden, Facchi, Florio and Gramegna [J. Phys. A., 2020; Phys. Rev. A., 2021].

We show there exists a packing of identical spheres in $\mathbb{R}^d$ with density at least \[ (1-o(1))\frac{d \log d}{2^{d+1}}\, , \] as $d\to\infty$. This improves upon previous bounds for general $d$ by a factor of order $\log d$ and is the first asymptotically growing improvement to Rogers' bound from 1947.

For each $\alpha \in (0, 1)$, we construct a bounded monotone deterministic sequence $(c_k)_{k \geq 0}$ of real numbers so that the number of real roots of the random polynomial $f_n(z) = \sum_{k=0}^n c_k \varepsilon_k z^k$ is $n^{\alpha + o(1)}$ with probability tending to one as the degree $n$ tends to infinity, where $(\varepsilon_k)$ is a sequence of i.i.d. (real) random variables of finite mean satisfying a mild anti-concentration assumption. In particular, this includes the case when $(\varepsilon_k)$ is a sequence of i.i.d. standard Gaussian or Rademacher random variables. This result confirms a conjecture of O. Nguyen from 2019. More generally, our main results also describe several statistical properties for the number of real roots of $f_n$, including the asymptotic behavior of the variance and a central limit theorem., Comment: 10 pages, no figures. Incorporated referee's corrections

Let $Z_1,\, Z_2,\dots$ be independent and identically distributed complex random variables with common distribution $\mu$ and set $$ P_n(z) := (z - Z_1)\cdots (z - Z_n)\,. $$ Recently, Angst, Malicet and Poly proved that the critical points of $P_n$ converge in an almost-sure sense to the measure $\mu$ as $n$ tends to infinity, thereby confirming a conjecture of Cheung-Ng-Yam and Kabluchko. In this short note, we prove for any fixed $k\in \mathbb{N}$, the empirical measure of zeros of the $k$th derivative of $P_n$ converges to $\mu$ in the almost sure sense, as conjectured by Angst-Malicet-Poly., Comment: 8 pages

For a finite graph $F$ and a value $p \in [0,1]$, let $I(F,p)$ denote the largest $y$ for which there is a sequence of graphs of edge density approaching $p$ so that the induced $F$-density of the sequence approaches $y$. We show that for all $F$ on at least three vertices and all $p \in (0,1)$, the binomial random graph $G(n,p)$ has induced $F$-density strictly less than $I(F,p).$ This provides a negative answer to a problem posed by Liu, Mubayi and Reiher. Our approach is in the limiting setting of graphons, and we in fact show a stronger result: the binomial random graph is never a \emph{local} maximum in the space of graphons of edge density $p$. This is done by finding a sequence of balanced perturbations of arbitrarily small norm that increase the $F$-density., Comment: 13 pages. Significantly new results and proof. Fan Wei added as an author. VJ and MM thank an anonymous referee for pointing out an error in a proof in v1

Let $G$ be a graph on $n$ vertices of maximum degree $\Delta$. We show that, for any $\delta > 0$, the down-up walk on independent sets of size $k \leq (1-\delta)\alpha_c(\Delta)n$ mixes in time $O_{\Delta,\delta}(k\log{n})$, thereby resolving a conjecture of Davies and Perkins in an optimal form. Here, $\alpha_{c}(\Delta)n$ is the NP-hardness threshold for the problem of counting independent sets of a given size in a graph on $n$ vertices of maximum degree $\Delta$. Our mixing time has optimal dependence on $k,n$ for the entire range of $k$; previously, even polynomial mixing was not known. In fact, for $k = \Omega_{\Delta}(n)$ in this range, we establish a log-Sobolev inequality with optimal constant $\Omega_{\Delta,\delta}(1/n)$. At the heart of our proof are three new ingredients, which may be of independent interest. The first is a method for lifting $\ell_\infty$-independence from a suitable distribution on the discrete cube -- in this case, the hard-core model -- to the slice by proving stability of an Edgeworth expansion using a multivariate zero-free region for the base distribution. The second is a generalization of the Lee-Yau induction to prove log-Sobolev inequalities for distributions on the slice with considerably less symmetry than the uniform distribution. The third is a sharp decomposition-type result which provides a lossless comparison between the Dirichlet form of the original Markov chain and that of the so-called projected chain in the presence of a contractive coupling., Comment: 25 pages; comments welcome!

Smale's Seventh Problem asks for an efficient algorithm to generate a configuration of $n$ points on the sphere that nearly minimizes the logarithmic energy. As a candidate starting configuration for this problem, Armentano, Beltr\'an and Shub considered the set of points given by the stereographic projection of the roots of the random elliptic polynomial of degree $n$ and computed the expected logarithmic energy. We study the fluctuations of the logarithmic energy associated to this random configuration and prove a central limit theorem. Our approach shows that all cumulants of the logarithmic energy are asymptotically linear in $n$, and hence the energy is well-concentrated on the scale of $\sqrt{n}$., Comment: 43 pages; to appear in Probability Theory and Related Fields

Let $X_1,X_2,\ldots$ be independent and identically distributed random variables in $\mathbb{C}$ chosen from a probability measure $\mu$ and define the random polynomial $$ P_n(z)=(z-X_1)\ldots(z-X_n)\,. $$ We show that for any sequence $k = k(n)$ satisfying $k \leq \log n / (5 \log\log n)$, the zeros of the $k$th derivative of $P_n$ are asymptotically distributed according to the same measure $\mu$. This extends work of Kabluchko, which proved the $k = 1$ case, as well as Byun, Lee and Reddy who proved the fixed $k$ case., Comment: 12 pages

We demonstrate a quasipolynomial-time deterministic approximation algorithm for the partition function of a Gibbs point process interacting via a finite-range stable potential. This result holds for all activities $\lambda$ for which the partition function satisfies a zero-free assumption in a neighborhood of the interval $[0,\lambda]$. As a corollary, for all finite-range stable potentials we obtain a quasipolynomial-time determinsitic algorithm for all $\lambda < /(e^{B + 1} \hat C_\phi)$ where $\hat C_\phi$ is a temperedness parameter and $B$ is the stability constant of $\phi$. In the special case of a repulsive potential such as the hard-sphere gas we improve the range of activity by a factor of at least $e^2$ and obtain a quasipolynomial-time deterministic approximation algorithm for all $\lambda < e/\Delta_\phi$, where $\Delta_\phi$ is the potential-weighted connective constant of the potential $\phi$. Our algorithm approximates coefficients of the cluster expansion of the partition function and uses the interpolation method of Barvinok to extend this approximation throughout the zero-free region., Comment: Results extended to include stable potentials

Let $A$ be a $n \times n$ symmetric matrix with $(A_{i,j})_{i\leq j} $, independent and identically distributed according to a subgaussian distribution. We show that $$\mathbb{P}(\sigma_{\min}(A) \leq \varepsilon/\sqrt{n}) \leq C \varepsilon + e^{-cn},$$ where $\sigma_{\min}(A)$ denotes the least singular value of $A$ and the constants $C,c>0 $ depend only on the distribution of the entries of $A$. This result confirms a folklore conjecture on the lower-tail asymptotics of the least singular value of random symmetric matrices and is best possible up to the dependence of the constants on the distribution of $A_{i,j}$. Along the way, we prove that the probability $A$ has a repeated eigenvalue is $e^{-\Omega(n)}$, thus confirming a conjecture of Nguyen, Tao and Vu., Comment: 39 pages + 33 page Appendix. The appendix builds on our previous work arXiv:2105.11384 and provides the proof of a technical quasi-randomness statement. Accepted to Forum of Mathematics, Pi

We prove that a Gibbs point process interacting via a finite-range, repulsive potential $\phi$ exhibits a strong spatial mixing property for activities $\lambda < e/\Delta_{\phi}$, where $\Delta_{\phi}$ is the potential-weighted connective constant of $\phi$, defined recently in [MP21]. Using this we derive several analytic and algorithmic consequences when $\lambda$ satisfies this bound: (1) We prove new identities for the infinite volume pressure and surface pressure of such a process (and in the case of the surface pressure establish its existence). (2) We prove that local block dynamics for sampling from the model on a box of volume $N$ in $\mathbb R^d$ mixes in time $O(N \log N)$, giving efficient randomized algorithms to approximate the partition function and approximately sample from these models. (3) We use the above identities and algorithms to give efficient approximation algorithms for the pressure and surface pressure.

Let $\mu$ and $\nu$ be probability measures in the complex plane, and let $p$ and $q$ be independent random polynomials of degree $n$, whose roots are chosen independently from $\mu$ and $\nu$, respectively. Under assumptions on the measures $\mu$ and $\nu$, the limiting distribution for the zeros of the sum $p+q$ was by computed by Reddy and the third author [J. Math. Anal. Appl. 495 (2021) 124719] as $n \to \infty$. In this paper, we generalize and extend this result to the case where $p$ and $q$ have different degrees. In this case, the logarithmic potential of the limiting distribution is given by the pointwise maximum of the logarithmic potentials of $\mu$ and $\nu$, scaled by the limiting ratio of the degrees of $p$ and $q$. Additionally, our approach provides a complete description of the limiting distribution for the zeros of $p + q$ for any pair of measures $\mu$ and $\nu$, with different limiting behavior shown in the case when at least one of the measures fails to have a logarithmic moment., Comment: 31 pages, 2 figures. Final version with minor corrections and updates

Designing infinite impulse response filters to match an arbitrary magnitude response requires specialized techniques. Methods like modified Yule-Walker are relatively efficient, but may not be sufficiently accurate in matching high order responses. On the other hand, iterative optimization techniques often enable superior performance, but come at the cost of longer run-times and are sensitive to initial conditions, requiring manual tuning. In this work, we address some of these limitations by learning a direct mapping from the target magnitude response to the filter coefficient space with a neural network trained on millions of random filters. We demonstrate our approach enables both fast and accurate estimation of filter coefficients given a desired response. We investigate training with different families of random filters, and find training with a variety of filter families enables better generalization when estimating real-world filters, using head-related transfer functions and guitar cabinets as case studies. We compare our method against existing methods including modified Yule-Walker and gradient descent and show our approach is, on average, both faster and more accurate., Comment: Accepted to ICASSP 2022

We define a potential-weighted connective constant that measures the effective strength of a repulsive pair potential of a Gibbs point process modulated by the geometry of the underlying space. We then show that this definition leads to improved bounds for Gibbs uniqueness for all non-trivial repulsive pair potentials on $\mathbb R^d$ and other metric measure spaces. We do this by constructing a tree-branching collection of densities associated to the point process that captures the interplay between the potential and the geometry of the space. When the activity is small as a function of the potential-weighted connective constant this object exhibits an infinite volume uniqueness property. On the other hand, we show that our uniqueness bound can be tight for certain spaces: the same infinite volume object exhibits non-uniqueness for activities above our bound in the case when the underlying space has the geometry of a tree.

Let $A$ be drawn uniformly at random from the set of all $n\times n$ symmetric matrices with entries in $\{-1,1\}$. We show that \[ \mathbb{P}( \det(A) = 0 ) \leq e^{-cn},\] where $c>0$ is an absolute constant, thereby resolving a well-known conjecture., Comment: 51 pages. Sections 3+4 split up and reorganized and proof sketch expanded

This paper provides a connection between the concentration of a random variable and the distribution of the roots of its probability generating function. Let $X$ be a random variable taking values in $\{0,\ldots,n\}$ with $\mathbb{P}(X = 0)\mathbb{P}(X = n) > 0$ and with probability generating function $f_X$. We show that if all of the zeros $\zeta$ of $f_X$ satisfy $|\arg(\zeta)| \geq \delta$ and $R^{-1} \leq |\zeta| \leq R$ then \[ \operatorname{Var}(X) \geq c R^{-2\pi/\delta}n, \] where $c > 0$ is a absolute constant. We show that this result is sharp, up to the factor $2$ in the exponent of $R$. As a consequence, we are able to deduce a Littlewood--Offord type theorem for random variables that are not necessarily sums of i.i.d.\ random variables., Comment: 29 pages

We derive asymptotic formulas for the number of integer partitions with given sums of $j$th powers of the parts for $j$ belonging to a finite, non-empty set $J \subset \mathbb N$. The method we use is based on the `principle of maximum entropy' of Jaynes. This principle leads to an intuitive variational formula for the asymptotics of the logarithm of the number of constrained partitions as the solution to a convex optimization problem over real-valued functions.

Let $M_n$ be drawn uniformly from all $\pm 1$ symmetric $n \times n$ matrices. We show that the probability that $M_n$ is singular is at most $\exp(-c(n\log n)^{1/2})$, which represents a natural barrier in recent approaches to this problem. In addition to improving on the best-known previous bound of Campos, Mattos, Morris and Morrison of $\exp(-c n^{1/2})$ on the singularity probability, our method is different and considerably simpler., Comment: 12 pages

Let $f_n(z) = \sum_{k = 0}^n \varepsilon_k z^k$ be a random polynomial where $\varepsilon_0,\ldots,\varepsilon_n$ are i.i.d. random variables with $\mathbb{E} \varepsilon_1 = 0$ and $\mathbb{E} \varepsilon_1^2 = 1$. Letting $r_1, r_2,\ldots, r_k$ denote the real roots of $f_n$, we show that the point process defined by $\{|r_1| - 1,\ldots, |r_k| - 1 \}$ converges to a non-Poissonian limit on the scale of $n^{-1}$ as $n \to \infty$. Further, we show that for each $\delta > 0$, $f_n$ has a real root within $\Theta_{\delta}(1/n)$ of the unit circle with probability at least $1 - \delta$. This resolves a conjecture of Shepp and Vanderbei from 1995 by confirming its weakest form and refuting its strongest form., Comment: 19 pages

Let $f = \sum_{k=0}^n \varepsilon_k z^k$ be a random polynomial, where $\varepsilon_0,\ldots ,\varepsilon_n$ are iid standard Gaussian random variables, and let $\zeta_1,\ldots,\zeta_n$ denote the roots of $f$. We show that the point process determined by the magnitude of the roots $\{ 1-|\zeta_1|,\ldots, 1-|\zeta_n| \}$ tends to a Poisson point process at the scale $n^{-2}$ as $n\rightarrow \infty$. One consequence of this result is that it determines the magnitude of the closest root to the unit circle. In particular, we show that \[ \min_{k} ||\zeta_k| - 1|n^2 \rightarrow \mathrm{Exp}(1/6),\] in distribution, where $\mathrm{Exp}(\lambda)$ denotes an exponential random variable of mean $\lambda^{-1}$. This resolves a conjecture of Shepp and Vanderbei from 1995 that was later studied by Konyagin and Schlag.

We give a new criterion for a classical gas with a repulsive pair potential to exhibit uniqueness of the infinite volume Gibbs measure and analyticity of the pressure. Our improvement on the bound for analyticity is by a factor $e^2$ over the classical cluster expansion approach and a factor $e$ over the known limit of cluster expansion convergence. The criterion is based on a contractive property of a recursive computation of the density of a point process. The key ingredients in our proofs include an integral identity for the density of a Gibbs point process and an adaptation of the algorithmic correlation decay method from theoretical computer science. We also deduce from our results an improved bound for analyticity of the pressure as a function of the density.

We consider a spatial (line) model for invasion of a population by a single mutant with a stochastically selectively neutral fitness landscape, independent from the fitness landscape for non-mutants. This model is similar to those considered in Farhang-Sardroodi et al. [PLOS Comput. Biol., 13(11), 2017; J. R. Soc. Interface, 16(157), 2019]. We show that the probability of mutant fixation in a population of size $N$, starting from a single mutant, is greater than $1/N$, which would be the case if there were no variation in fitness whatsoever. In the small variation regime, we recover precise asymptotics for the success probability of the mutant. This demonstrates that the introduction of randomness provides an advantage to minority mutations in this model, and shows that the advantage increases with the system size. We further demonstrate that the mutants have an advantage in this setting only because they are better at exploiting unusually favorable environments when they arise, and not because they are any better at exploiting pockets of favorability in an environment that is selectively neutral overall., Comment: 25 pages, 4 figures

An integer partition is called graphical if it is the degree sequence of a simple graph. We prove that the probability that a uniformly chosen partition of size $n$ is graphical decreases to zero faster than $n^{-.003}$, answering a question of Pittel. A lower bound of $n^{-1/2}$ was proven by Erd\H{o}s and Richmond, and so this demonstrates that the probability decreases polynomially. Key to our argument is an asymptotic result of Pittel characterizing the joint distribution of the first rows and columns of a uniformly random partition, combined with a characterization of graphical partitions due to Erd\H{o}s and Gallai. Our proof also implies a polynomial upper bound for the probability that two randomly chosen partitions are comparable in the dominance order.

Let $f \in \mathbb{R}[x]$ be a polynomial with real coefficients. We say that $f$ is eventually non-negative if $f^m$ has non-negative coefficients for all sufficiently large $m \in \mathbb{N}$. In this short note, we give a classification of all eventually non-negative polynomials. This generalizes a theorem of De Angelis, and proves a conjecture of Bergweiler, Eremenko and Sokal

We examine an interacting particle system on trees commonly referred to as the frog model. For its initial state, it begins with a single active particle at the root and i.i.d. $\mathrm{Poiss}(\lambda)$ many inactive particles at each non-root vertex. Active particles perform discrete time simple random walk and in the process activate any inactive particles they encounter. We show that for $\textit{every}$ non-amenable tree with bounded degree there exists a phase transition from transience to recurrence (with a non-trivial intermediate phase sometimes sandwiched in between) as $\lambda$ varies.

We consider an interacting particle system on trees known as the frog model: initially, a single active particle begins at the root and i.i.d.~$\mathrm{Poiss}(\lambda)$ many inactive particles are placed at each non-root vertex. Active particles perform discrete time simple random walk and activate the inactive particles they encounter. We show that for Galton-Watson trees with offspring distributions $Z$ satisfying $\mathbf{P}(Z \geq 2) = 1$ and $\mathbf{E}[Z^{4 + \epsilon}] < \infty$ for some $\epsilon > 0$, there is a critical value $\lambda_c\in(0,\infty)$ separating recurrent and transient regimes for almost surely every tree, thereby answering a question of Hoffman-Johnson-Junge. In addition, we also establish that this critical parameter depends on the entire offspring distribution, not just the maximum value of $Z$, answering another question of Hoffman-Johnson-Junge and showing that the frog model and contact process behave differently on Galton-Watson trees., Comment: Accepted to Annals of Applied Probability

Let $X \in \{0,\ldots,n \}$ be a random variable, with mean $\mu$ and standard deviation $\sigma$ and let \[f_X(z) = \sum_{k} \mathbb{P}(X = k) z^k, \] be its probability generating function. Pemantle conjectured that if $\sigma$ is large and $f_X$ has no roots close to $1\in \mathbb{C}$ then $X$ must be approximately normal. We completely resolve this conjecture in the following strong quantitative form, obtaining sharp bounds. If $\delta = \min_{\zeta}|\zeta-1|$ over the complex roots $\zeta$ of $f_X$, and $X^{\ast} := (X-\mu)/\sigma$, then \[ \sup_{t \in \mathbb{R}} \left|\mathbb{P}(X^{\ast} \leq t) - \mathbb{P}( Z \leq t) \, \right| = O\left(\frac{\log n}{\delta\sigma} \right) \] where $Z \sim \mathcal{N}(0,1)$ is a standard normal. This gives the best possible version of a result of Lebowitz, Pittel, Ruelle and Speer. We also show that if $f_X$ has no roots with small argument, then $X$ must be approximately normal, again in a sharp quantitative form: if we set $\delta = \min_{\zeta}|\arg(\zeta)|$ then \[ \sup_{t \in \mathbb{R}} \left|\mathbb{P}(X^{\ast} \leq t) - \mathbb{P}( Z \leq t) \, \right| = O\left(\frac{1}{\delta\sigma} \right). \] Using this result, we answer a question of Ghosh, Liggett and Pemantle by proving a sharp multivariate central limit theorem for random variables with real-stable probability generating functions., Comment: 44 pages. Typo in abstract fixed

We analyze the asymptotic behavior of the average maximal number of balls in a bin obtained by throwing uniformly at random $r$ balls without replacement into $n$ bins, $T$ times. Writing the expected maximum as $\frac{r}{n}T+ C_{n,r}\sqrt{T} + o(\sqrt{T})$, a recent preprint of Behrouzi-Far and Zeilberger asks for an explicit expression for $C_{n,r}$ in terms of $n,r$ and $\pi$. In this short note, we find an expression for $C_{n,r}$ in terms of $n, r$ and the expected maximum of $n$ independent standard Gaussians. This provides asymptotics for large $n$ as well as closed forms for small $n$---e.g. $C_{4,2} = \frac{3}{2 \pi^{3/2}} \arccos(-1/3)$---and shows that computing a closed form for $C_{n,r}$ is precisely as hard as the difficult question of finding the expected maximum of $n$ independent standard Gaussians., Comment: 4 pages

We consider critical percolation on Galton-Watson trees and prove quenched analogues of classical theorems of critical branching processes. We show that the probability critical percolation reaches depth $n$ is asymptotic to a tree-dependent constant times $n^{-1}$. Similarly, conditioned on critical percolation reaching depth $n$, the number of vertices at depth $n$ in the critical percolation cluster almost surely converges in distribution to an exponential random variable with mean depending only on the offspring distribution. The incipient infinite cluster (IIC) is constructed for a.e. Galton-Watson tree and we prove a limit law for the number of vertices in the IIC at depth $n$, again depending only on the offspring distribution. Provided the offspring distribution used to generate these Galton-Watson trees has all finite moments, each of these results holds almost-surely., Comment: 14 pages

We explore the survival function for percolation on Galton-Watson trees. Letting $g(T,p)$ represent the probability a tree $T$ survives Bernoulli percolation with parameter $p$, we establish several results about the behavior of the random function $g(\mathbf{T} , \cdot)$, where $\mathbf{T}$ is drawn from the Galton-Watson distribution. These include almost sure smoothness in the supercritical region; an expression for the $k\text{th}$-order Taylor expansion of $g(\mathbf{T} , \cdot)$ at criticality in terms of limits of martingales defined from $\mathbf{T}$ (this requires a moment condition depending on $k$); and a proof that the $k\text{th}$ order derivative extends continuously to the critical value. Each of these results is shown to hold for almost every Galton-Watson tree., Comment: 38 pages

For each $n$, let $X_n \in \{0,\ldots,n\}$ be a random variable with mean $\mu_n$, standard deviation $\sigma_n$, and let \[ P_n(z) = \sum_{k=0}^n \mathbb{P}( X_n = k) z^k ,\] be its probability generating function. We show that if none of the complex zeros of the polynomials $\{ P_n(z)\}$ are contained in a neighbourhood of $1 \in \mathbb{C}$ and $\sigma_n > n^{\varepsilon}$ for some $\varepsilon >0$, then $ X_n^* =(X_n - \mu_n)\sigma^{-1}_n$ tends to a normal random variable $Z \sim \mathcal{N}(0,1)$ in distribution as $n \rightarrow \infty$. Moreover, we show this result is sharp in the sense that there exist sequences of random variables $\{X_n\}$ with $\sigma_n > C\log n $ for which $P_n(z)$ has no roots near $1$ and $X_n^*$ is not asymptotically normal. These results disprove a conjecture of Pemantle and improve upon various results in the literature. We go on to prove several other results connecting the location of the zeros of $P_n(z)$ and the distribution of the random variables $X_n$., Comment: Some more history added to the introduction

We consider invasion percolation on Galton-Watson trees. On almost every Galton-Watson tree, the invasion cluster almost surely contains only one infinite path. This means that for almost every Galton-Watson tree, invasion percolation induces a probability measure on infinite paths from the root. We show that under certain conditions of the progeny distribution, this measure is absolutely continuous with respect to the limit uniform measure. This confirms that invasion percolation, an efficient self-tuning algorithm, may be used to sample approximately from the limit uniform distribution. Additionally, we analyze the forward maximal weights along the backbone of the invasion cluster and prove a limit law for the process., Comment: 35 pages, 1 figure