Jonathan Hermon
YOU?
Author Swipe
View article: Covering a graph with independent walks
Covering a graph with independent walks Open
Let $P$ be an irreducible and reversible transition matrix on a finite state space $V$ with invariant distribution $π$. We let $k$ chains start by choosing independent locations distributed according to $π$ and then they evolve independent…
View article: Concentration of information on discrete groups
Concentration of information on discrete groups Open
Motivated by the Asymptotic Equipartition Property and its recently discovered role in the cutoff phenomenon, we initiate the systematic study of varentropy on discrete groups. Our main result is an approximate tensorization inequality whi…
View article: Cutoff for random Cayley graphs of nilpotent groups
Cutoff for random Cayley graphs of nilpotent groups Open
We consider the random Cayley graphs of a sequence of finite nilpotent groups of diverging sizes $G=G(n)$, whose ranks and nilpotency classes are uniformly bounded. For some $k=k(n)$ such that $1\ll\log k \ll \log |G|$, we pick a random se…
View article: Geometry of random Cayley graphs of Abelian groups
Geometry of random Cayley graphs of Abelian groups Open
Consider the random Cayley graph of a finite Abelian group G with respect to k generators chosen uniformly at random, with 1≪logk≪log|G|. Draw a vertex U∼Unif(G). We show that the graph distance dist(id,U) from the identity to U concentrat…
View article: Sensitivity of mixing times of Cayley graphs
Sensitivity of mixing times of Cayley graphs Open
We show that the total variation mixing time is not quasi-isometry invariant, even for Cayley graphs. Namely, we construct a sequence of pairs of Cayley graphs with maps between them that twist the metric in a bounded way, while the ratio …
View article: Phase transition for random walks on graphs with added weighted random matching
Phase transition for random walks on graphs with added weighted random matching Open
For a finite graph $G=(V,E)$ let $G^*$ be obtained by considering a random perfect matching of $V$ and adding the corresponding edges to $G$ with weight $\varepsilon$, while assigning weight 1 to the original edges of $G$. We consider whet…
View article: Relaxation times are stationary hitting times of large sets
Relaxation times are stationary hitting times of large sets Open
We give a characterization of the relaxation time up to an absolute constant factor, in terms of stationary expected hitting times of large sets. This resolves a conjecture of Aldous and Fill. We give a similar characterization for the spe…
View article: Cutoff for random walk on random graphs with a community structure
Cutoff for random walk on random graphs with a community structure Open
We consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has an internal $\mathrm{deg}^{\text{int}}\geq 3$ and an outgoing $\mathrm{de…
View article: On the universality of fluctuations for the cover time
On the universality of fluctuations for the cover time Open
We consider random walks on finite vertex-transitive graphs $Γ$ of bounded degree. We find a simple geometric condition which characterises the cover time fluctuations: the suitably normalised cover time converges to a standard Gumbel vari…
View article: A direct comparison between the mixing time of the interchange process with "few" particles and independent random walks
A direct comparison between the mixing time of the interchange process with "few" particles and independent random walks Open
We consider the interchange process with $k$ particles (${\rm IP}(k)$) on $n$-vertex hypergraphs in which each hyperedge $e$ rings at rate $r_e$. When $e$ rings, the particles occupying it are permuted according to a random permutation fro…
View article: Mean Field Behavior during the Big Bang for Coalescing Random Walk
Mean Field Behavior during the Big Bang for Coalescing Random Walk Open
In this paper we consider the coalescing random walk model on general graphs $G=(V,E)$. We set up a unified framework to study the leading order of decay rate of $P_t$, the expectation of the fraction of occupied sites at time $t$, particu…
View article: Mean Field Behavior during the Big Bang Regime for Coalescing Random Walks
Mean Field Behavior during the Big Bang Regime for Coalescing Random Walks Open
In this paper we consider coalescing random walks on a general connected graph $G=(V,E)$. We set up a unified framework to study the leading order of the decay rate of $P_t$, the expectation of the fraction of occupied sites at time $t$, p…
View article: Cutoff for Almost All Random Walks on Abelian Groups
Cutoff for Almost All Random Walks on Abelian Groups Open
Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll \log k \ll \log |G|$; denote it $G_k$. A conjecture of Aldous and Diaconis (1985) asserts, for $k \gg \log |G|$, …
View article: The interchange process on high-dimensional products
The interchange process on high-dimensional products Open
We resolve a long-standing conjecture of Wilson (2004), reiterated by Oliveira (2016), asserting that the mixing-time of the unit-rate Interchange Process on the $n$-dimensional hypercube is of order $n$. This follows from a sharp inequali…
View article: A comparison principle for random walk on dynamical percolation
A comparison principle for random walk on dynamical percolation Open
We consider the model of random walk on dynamical percolation introduced by Peres, Stauffer and Steif (2015). We obtain comparison results for this model for hitting and mixing times and for the spectral-gap and log-Sobolev constant with t…
View article: The exclusion process mixes (almost) faster than independent particles
The exclusion process mixes (almost) faster than independent particles Open
Oliveira conjectured that the order of the mixing time of the exclusion process with $k$-particles on an arbitrary $n$-vertex graph is at most that of the mixing-time of $k$ independent particles. We verify this up to a constant factor for…
View article: Universality of cutoff for graphs with an added random matching
Universality of cutoff for graphs with an added random matching Open
We establish universality of cutoff for simple random walk on a class of random graphs defined as follows. Given a finite graph $G=(V,E)$ with $|V|$ even we define a random graph $ G^*=(V,E \cup E')$ obtained by picking $E'$ to be the (uno…
View article: Sensitivity of mixing times of Cayley graphs
Sensitivity of mixing times of Cayley graphs Open
We show that the total variation mixing time is not quasi-isometry invariant, even for Cayley graphs. Namely, we construct a sequence of pairs of Cayley graphs with maps between them that twist the metric in a bounded way, while the ratio …
View article: The social network model on infinite graphs
The social network model on infinite graphs Open
Given an infinite connected regular graph $G=(V,E)$, place at each vertex Pois($\lambda$) walkers performing independent lazy simple random walks on $G$ simultaneously. When two walkers visit the same vertex at the same time they are decla…
View article: Cutoff for the mean-field zero-range process with bounded monotone rates
Cutoff for the mean-field zero-range process with bounded monotone rates Open
We consider the zero-range process with arbitrary bounded monotone rates on the complete graph, in the regime where the number of sites diverges while the density of particles per site converges. We determine the asymptotics of the mixing …
View article: On an epidemic model on finite graphs
On an epidemic model on finite graphs Open
We study a system of random walks, known as the frog model, starting from a profile of independent Poisson($\\lambda $) particles per site, with one additional active particle planted at some vertex $\\mathbf{o}$ of a finite connected simp…
View article: Random Cayley Graphs I: Cutoff and Geometry for Heisenberg Groups
Random Cayley Graphs I: Cutoff and Geometry for Heisenberg Groups Open
Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll \log k \ll \log \lvert G \rvert$. A conjecture of Aldous and Diaconis asserts, for $k \gg \log \lvert G \rvert$, …
View article: Random Cayley Graphs II: Cutoff and Geometry for Abelian Groups
Random Cayley Graphs II: Cutoff and Geometry for Abelian Groups Open
Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll \log k \ll \log \lvert G \rvert$. A conjecture of Aldous and Diaconis asserts, for $k \gg \log \lvert G \rvert$, …
View article: Further Results and Discussions on Random Cayley Graphs
Further Results and Discussions on Random Cayley Graphs Open
Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll k \lesssim \log |G|$. The results of this article supplement those in the three main papers on random Cayley grap…
View article: Cutoff for Random Walks on Upper Triangular Matrices
Cutoff for Random Walks on Upper Triangular Matrices Open
Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 \ll \log k \ll \log |G|$ (ie $1 \ll k = |G|^{o(1)}$). A conjecture of Aldous and Diaconis (1985) asserts, for $k\gg\l…
View article: No Percolation at Criticality on Certain Groups of Intermediate Growth
No Percolation at Criticality on Certain Groups of Intermediate Growth Open
We prove that critical percolation has no infinite clusters almost surely on any unimodular quasi-transitive graph satisfying a return probability upper bound of the form $p_n(v,v) \leq \exp \left [-\Omega (n^\gamma )\right ]$ for some $\g…
View article: Intersection times for critical branching random walk
Intersection times for critical branching random walk Open
We present results relating mixing times to the intersection time of branching random walk (BRW) in which the logarithm of the expected number of particles at time $t$ grows like $ \mathrm{gap} \cdot t $. This is a finite state space analo…
View article: Rapid mixing of hypergraph independent sets
Rapid mixing of hypergraph independent sets Open
We prove that the mixing time of the Glauber dynamics for sampling independent sets on n-vertex k-uniform hypergraphs is 0(n log n) when the maximum degree Δ satisfies Δ ≤ c2k/2, improving on the previous bound Bordewich and co-workers of …
View article: A Spectral Characterization for Concentration of the Cover Time
A Spectral Characterization for Concentration of the Cover Time Open
We prove that for a sequence of finite vertex-transitive graphs of increasing sizes, the cover times are asymptotically concentrated if and only if the product of the spectral gap and the expected cover time diverges. In fact, we prove thi…