BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Gady Kozma appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Let $f$ be sampled uniformly at random from the set of degree $n$ polynomials whose coefficients lie in $\{ \pm 1\}$. A folklore conjecture, known to hold under GRH, states that the probability that $f$ is irreducible tends to $1$ as $n$ goes to infinity. We prove unconditionally that $$\limsup_{n \to \infty} \mathbb{P}(f \text{ is irreducible}) = 1.$$
The collection $\mathcal{M}_n$ of all metric spaces on $n$ points whose diameter is at most $2$ can naturally be viewed as a compact convex subset of $\mathbb{R}^{\binom{n}{2}}$, known as the metric polytope. In this paper, we study the metric polytope for large $n$ and show that it is close to the cube $[1,2]^{\binom{n}{2}} \subseteq \mathcal{M}_n$ in the following two senses. First, the volume of the polytope is not much larger than that of the cube, with the following quantitative estimates: \[ \left(\tfrac{1}{6}+o(1)\right)n^{3/2} \le \log \mathrm{Vol}(\mathcal{M}_n)\le O(n^{3/2}). \] Second, when sampling a metric space from $\mathcal{M}_n$ uniformly at random, the minimum distance is at least $1 - n^{-c}$ with high probability, for some $c > 0$. Our proof is based on entropy techniques. We discuss alternative approaches to estimating the volume of $\mathcal{M}_n$ using exchangeability, Szemerédi's regularity lemma, the hypergraph container method, and the Kővári--Sós--Turán theorem.
We study the size of the near-critical window for Bernoulli percolation on $\mathbb Z^d$. More precisely, we use a quantitative Grimmett-Marstrand theorem to prove that the correlation length, both below and above criticality, is bounded from above by $\exp(C/|p-p_c|^2)$. Improving on this bound would be a further step towards the conjecture that there is no infinite cluster at criticality on $\mathbb Z^d$ for every $d\ge2$.
The goal of this paper is to prove that a random polynomial with i.i.d. random coefficients taking values uniformly in $\{1,\ldots, 210\}$ is irreducible with probability tending to $1$ as the degree tends to infinity. Moreover, we prove that the Galois group of the random polynomial contains the alternating group, again with probability tending to $1$.
We prove that a random bivariate polynomial with plus minus 1 coefficients is irreducible with high probability.
We show Green's function asymptotic upper bound for the two-point function of weakly self-avoiding walk in dimension bigger than 4, revisiting a classic problem. Our proof relies on Banach algebras to analyse the lace-expansion fixed point equation and is simpler than previous approaches in that it avoids Fourier transforms.
We study the minimal possible growth of harmonic functions on lamplighters. We find that $(\mathbb{Z}/2)\wr \mathbb{Z}$ has no sublinear harmonic functions, $(\mathbb{Z}/2)\wr \mathbb{Z}^2$ has no sublogarithmic harmonic functions, and neither has the repeated wreath product $(\dotsb(\mathbb{Z}/2\wr\mathbb{Z}^2)\wr\mathbb{Z}^2)\wr\dotsb\wr\mathbb{Z}^2$. These results have implications on attempts to quantify the Derriennic-Kaimanovich-Vershik theorem.
We show that the total variation mixing time of the simple random walk on the giant component of supercritical Erdos-Renyi graphs is log^2 n. This statement was only recently proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are "decorated expanders" - an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations.
We prove that vertex-reinforced random walk on the integers with weight of order k to the power alpha, for alpha in [0, 1/2), is recurrent. This confirms a conjecture of Volkov for alpha<1/2. The conjecture for alpha in [1/2, 1) remains open.
We prove that every finite union of rectangles in $R^d$ admits a Riesz basis of exponentials.
We study a natural discrete Bochner-type inequality on graphs, and explore its merit as a notion of curvature in discrete spaces. An appealing feature of this discrete version seems to be that it is fairly straightforward to compute this notion of curvature parameter for several specific graphs of interest - particularly, abelian groups, slices of the hypercube, and the symmetric group under various sets of generators. We further develop this notion by deriving Buser-type inequalities (a la Ledoux), relating functional and isoperimetric constants associated with a graph. Our derivations provide a tight bound on the Cheeger constant (i.e., the edge-isoperimetric constant) in terms of the spectral gap, for graphs with nonnegative curvature, particularly, the class of abelian Cayley graphs - a result of independent interest.
We study harmonic functions on random environments with particular emphasis on the case of the infinite cluster of supercritical percolation on $\mathbb{Z}^d$. We prove that the vector space of harmonic functions growing at most linearly is $(d+1)$-dimensional almost surely. Further, there are no nonconstant sublinear harmonic functions (thus implying the uniqueness of the corrector). A main ingredient of the proof is a quantitative, annealed version of the Avez entropy argument. This also provides bounds on the derivative of the heat kernel, simplifying and generalizing existing results. The argument applies to many different environments; even reversibility is not necessary.
We show that in high dimensional Bernoulli percolation, removing from a thin infinite cluster a much thinner infinite cluster leaves an infinite component. This observation has implications for the van den Berg-Brouwer forest fire process, also known as self-destructive percolation, for dimension high enough.
We prove central limit theorem under diffusive scaling for the displacement of a random walk on ${\mathbb Z}^d$ in stationary divergence-free random drift field, under the ${\mathcal H}_{-1}$-condition imposed on the drift field. The condition is equivalent to assuming that the stream tensor be stationary and square integrable. This improves the best existing result of Komorowski, Landim and Olla (2012), where it is assumed that the stream tensor be in ${\mathcal L}^{\max\{2+δ,d\}}$, with $δ>0$. Our proof relies on the relaxed sector condition of Horváth, Tóth and Vető (2012), and is technically rather simpler than existing earlier proofs of similar results by Oelschläger (1988) and Komorowski, Landim, Olla (2012).
We show that any finite union of intervals supports a Riesz basis of exponentials
We provide new bounds for the divisibility function of the free group F_2 and construct short laws for the symmetric groups Sym(n). The construction is random and relies on the classification of the finite simple groups. We also give bounds on the length of laws for finite simple groups of Lie type.
We demonstrate an algorithm that reconstructs the number of walkers in an unknown graph from observations of their returns to a fixed point.
We show that in the Lorentz mirror model, at any density of mirrors, the probability of a particle starting at the origin to reach distance n is at least 1/(2n+1).
We examine diffusion-limited aggregation for a one-dimensional random walk with long jumps. We achieve upper and lower bounds on the growth rate of the aggregate as a function of the number of moments a single step of the walk has. In this paper we handle the case of transient walks.
This is a survey of the "Fourier symmetry" of measures and distributions on the circle in relation with the size of their support. Mostly it is based on our paper arxiv:1004.3631 and a talk given by the second author in the 2012 Abel symposium.
Consider the process of random transpositions on the complete graph. We use representation theory to give an exact, simple formula for the expected number of cycles of size k at time t, in terms of an incomplete Beta function. Using this we show that the expected number of cycles of size k jumps from 0 to its equilibrium value, 1/k, at the time where the giant component of the associated random graph first exceeds k. Consequently we deduce a new and simple proof of Schramm's theorem on random transpositions, that giant cycles emerge at the same time as the giant component in the random graph. We also calculate the "window" for this transition and find that it is quite thin. Finally, we give a new proof of a result by the first author and Durrett that the random transposition process exhibits a certain slowdown transition. The proof makes use of a recent formula for the character decomposition of the number of cycles of a given size in a permutation, and the Frobenius formula for the character ratios.
We prove that the linearly edge reinforced random walk (LRRW) on any graph with bounded degrees is recurrent for sufficiently small initial weights. In contrast, we show that for non-amenable graphs the LRRW is transient for sufficiently large initial weights, thereby establishing a phase transition for the LRRW on non-amenable graphs. While we rely on the description of the LRRW as a mixture of Markov chains, the proof does not use the magic formula. We also derive analogous results for the vertex reinforced jump process.
We proved earlier that every measurable function on the circle, after a uniformly small perturbation, can be written as a power series (i.e. a series of exponentials with positive frequencies), which converges almost everywhere. Here we show that this result is basically sharp: the perturbation cannot be made smooth or even Hölder. We discuss also a similar problem for perturbations with lacunary spectrum.
A survey of reinforced random walk, with emphasis on the linear case.
We consider random self-avoiding walks between two points on the boundary of a finite subdomain of Z^d (the probability of a self-avoiding trajectory gamma is proportional to mu^{-length(gamma)}). We show that the random trajectory becomes space-filling in the scaling limit when the parameter mu is supercritical.
A dyadic tile of order n is any rectangle obtained from the unit square by n successive bisections by horizontal or vertical cuts. Let each dyadic tile of order n be available with probability p, independently of the others. We prove that for p sufficiently close to 1, there exists a set of pairwise disjoint available tiles whose union is the unit square, with probability tending to 1 as n->infinity, as conjectured by Joel Spencer in 1999. In particular we prove that if p=7/8, such a tiling exists with probability at least 1-(3/4)^n. The proof involves a surprisingly delicate counting argument for sets of unavailable tiles that prevent tiling.
We show that there exists a connected graph G with subexponential volume growth such that critical percolation on the product of G with the line has infinitely many infinite clusters. We also give some conditions under which this cannot occur.
There exists a graph with two vertices x and y such that the ratio of the heat kernels p(x,x;t)/p(y,y;t) does not converge as t goes to infinity.
We study the basis property of systems of exponentials with frequencies belonging to 'simple quasicrystals'. We show that a diophantine condition is necessary and sufficient for such a system to be a Riesz basis in L^2 on a finite union of intervals. For the proof we extend to BMO a theorem of Kesten about the discrepancy of irrational rotations of the circle.
We study the Laplacian-infinity path as an extreme case of the Laplacian-alpha random walk. Although, in the finite alpha case, there is reason to believe that the process converges to SLE, we show that this is not the case when alpha is infinite. In fact, the scaling limit depends heavily on the lattice structure, and is not conformal (or even rotational) invariant.
We prove that with high probability, d+1 random Bernoulli polynomials in d variables of degree n (n goes to infinity) do not possess a common root.
Inspired by Aldous' conjecture for the spectral gap of the interchange process and its recent resolution by Caputo, Liggett and Richthammer, we define an associated order on the irreducible representations of S_n. Aldous' conjecture is equivalent to certain representations being comparable in this order, and hence determining the "Aldous order" completely is a generalized question. We show a few additional entries in this order.
We show that critical percolation on a product of two regular trees of degree $\ge$ 3 satisfies the triangle condition. The proof does not examine the degrees of vertices and is not "perturbative" in any sense. It relies on an unpublished lemma of Oded Schramm.
We study the "Fourier symmetry" of measures and distributions on the circle, in relation with the size of their supports. The main results of this paper are: (1) A one-side extension of Frostman's theorem, which connects the rate of decay of Fourier transform of a distribution with the Hausdorff dimension of the support; (2) A construction of compacts of "critical" size, which support distributions (even pseudo-functions) with anti-analytic part belonging to l^2. We also give examples of non-symmetry which may occur for measures with "small" support. A number of open questions are stated.
The following random process on $\Z^4$ is studied. At first visit to a site, the two first coordinates perform a (2-dimensional) simple random walk step. At further visits, it is the last two coordinates which perform a simple random walk step. We prove that this process is almost surely transient. The lower dimensional versions are discussed and various generalizations and related questions are proposed.
Add to each level of binary tree edges to make the induced graph on the level a uniform expander. It is shown that such a graph admits no non-constant bounded harmonic functions.
We study the entropy of the set traced by an $n$-step random walk on $\Z^d$. We show that for $d \geq 3$, the entropy is of order $n$. For $d = 2$, the entropy is of order $n/\log^2 n$. These values are essentially governed by the size of the boundary of the trace.
We examine the incipient infinite cluster (IIC) of critical percolation in regimes where mean-field behavior has been established, namely when the dimension d is large enough or when d>6 and the lattice is sufficiently spread out. We find that random walk on the IIC exhibits anomalous diffusion with the spectral dimension d_s=4/3, that is, p_t(x,x)= t^{-2/3+o(1)}. This establishes a conjecture of Alexander and Orbach. En route we calculate the one-arm exponent with respect to the intrinsic distance.