JHJonathan Hermon

Jonathan Hermon

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Jonathan Hermon has a total of 33 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Existence and sharpness of the phase transition for the frog model on transitive graphs

    by Omer Angel, Daniel de la Riva, Jonathan Hermon, Yuliang Shi

  • Top Cited Papers

    Cutoff for almost all random walks on Abelian groups

    by Jonathan Hermon, Sam Olesker-Taylor

    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 by G_{k} . A conjecture of Aldous and Diaconis (1985) asserts, for k \gg{\log}|G| , that the random walk on this graph exhibits cutoff. Further, the cutoff time should be a function only of k and |G| , to sub-leading order. This was verified for all Abelian groups in the ’90s. We extend the conjecture to 1 \ll k \lesssim{\log}|G| . We establish cutoff for all Abelian groups under the condition k - d(G) \gg 1 , where d(G) is the minimal size of a generating subset of G , which is almost optimal. The cutoff time is described (abstractly) in terms of the entropy of random walk on \mathbb{Z}^{k} . This abstract definition allows us to deduce that the cutoff time can be written as a function only of k and |G| when d(G) \ll{\log}|G| and k - d(G) \asymp k \gg 1 ; this is not the case when d(G) \asymp{\log}|G| \asymp k . For certain regimes of k , we find the limit profile of the convergence to equilibrium. Wilson (1997) conjectured that \mathbb{Z}_{2}^{d} gives rise to the slowest mixing time for G_{k} amongst all groups of size at most 2^{d} . We give a partial answer, verifying the conjecture for nilpotent groups. This is obtained via a comparison result of independent interest between the mixing times of nilpotent G and a corresponding Abelian group \overline G , namely the direct sum of the Abelian quotients in the lower central series of G . We use this to refine a celebrated result of Alon and Roichman 1994: we show for nilpotent G that G_{k} is an expander provided k - d(\overline G) \gtrsim{\log}|G| . As another consequence, we establish cutoff for nilpotent groups with relatively small commutator subgroup, including high-dimensional special groups, such as Heisenberg groups. The aforementioned results all hold with high probability over the random Cayley graph G_{k} .


  • Open Access

    Stationary hitting times on vertex-transitive graphs

    by Nathanaël Berestycki, Jonathan Hermon, Lucas Teyssier

    We prove a refined version of the Aldous and Brown's exponential approximation of stationary hitting times. These are valid for all reversible Markov chains. We then specialise our estimates for vertex-transitive graphs, where we obtain improved bounds which depend on the growth of the graphs. The most delicate cases are when the diameter is comparable to that of low-dimensional tori. In particular, in "dimensions" less than four (up to logarithmic factors) our error terms are the square of those of Aldous and Brown. These improved bounds play a crucial role in the companion work arXiv:2202.02255 characterising the fluctuations of the cover time on vertex-transitive graphs.

  • Open Access

    Cutoff for generalised Bernoulli-Laplace urn models

    by Ritesh Goenka, Jonathan Hermon, Dominik Schmid

    We introduce a multi-colour multi-urn generalisation of the Bernoulli-Laplace urn model, consisting of $d$ urns, $m$ colours, and $dmn$ balls, with $dn$ balls of each colour and $mn$ balls in each urn. At each step, one ball is drawn uniformly at random from each urn, and the chosen balls are redistributed among the urns based on a permutation drawn from a distribution $μ$ on the symmetric group $S_d$. We study the mixing time of this Markov chain for fixed $m$, $d$, and $μ$, as $n \rightarrow \infty$. We show that there is cutoff whenever the chain on $[d]$ corresponding to the evolution of a single ball is irreducible, and that the same holds for a labeled version of the model. As an application, we also obtain partial results on cutoff for a card shuffling version of the model in which the cards are labeled and their ordering within each stack matters.

  • Open Access

    Phase transition for random walks on graphs with added weighted random matching

    by Zsuzsanna Baran, Jonathan Hermon, Anđela Šarković, Perla Sousi

    For a finite graph $$G=(V,E)$$ G = ( V , E ) let $$G^*$$ 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 whether for a sequence $$(G_n)$$ ( G n ) of graphs with bounded degrees and corresponding weights $$(\varepsilon _n)$$ ( ε n ) , the (weighted) random walk on $$(G_n^*)$$ ( G n ∗ ) has cutoff. For graphs with polynomial growth we show that $$\log \left( \frac{1}{\varepsilon _n}\right) \ll \log |V_n|$$ log 1 ε n ≪ log | V n | is a sufficient condition for cutoff. Under the additional assumption of vertex-transitivity we establish that this condition is also necessary. For graphs where the entropy of the simple random walk grows linearly up to some time of order $$\log |V_n|$$ log | V n | we show that $$\frac{1}{\varepsilon _n}\ll \log |V_n|$$ 1 ε n ≪ log | V n | is sufficient for cutoff. In the special case of expander graphs we also provide a complete picture for the complementary regime $$\frac{1}{\varepsilon _n}\gtrsim \log |V_n|$$ 1 ε n ≳ log | V n | .


  • Open Access

    Phase transition for random walks on graphs with added weighted random matching

    by Zsuzsanna Baran, Jonathan Hermon, Anđela Šarković, Perla Sousi

    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 whether for a sequence $(G_n)$ of graphs with bounded degrees and corresponding weights $(\varepsilon_n)$, the (weighted) random walk on $(G_n^*)$ has cutoff. For graphs with polynomial growth we show that $\log\left(\frac{1}{\varepsilon_n}\right)\ll\log|V_n|$ is a sufficient condition for cutoff. Under the additional assumption of vertex-transitivity we establish that this condition is also necessary. For graphs where the entropy of the simple random walk grows linearly up to some time of order $\log|V_n|$ we show that $\frac{1}{\varepsilon_n}\ll\log|V_n|$ is sufficient for cutoff. In case of expander graphs we also provide a complete picture for the complementary regime $\frac{1}{\varepsilon_n}\gtrsim\log|V_n|$.

  • Geometry of random Cayley graphs of Abelian groups

    by Jonathan Hermon, Sam Olesker-Taylor

    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 concentrates at a particular value M, which is the minimal radius of a ball in Zk of cardinality at least |G|, under mild conditions. In other words, the distance from the identity for all but o(|G|) of the elements of G lies in the interval [M−o(M),M+o(M)]. In the regime k≳log|G|, we show that the diameter of the graph is also asymptotically M. In the spirit of a conjecture of Aldous and Diaconis (Technical Report 231 (1985)), this M depends only on k and |G|, not on the algebraic structure of G. Write d(G) for the minimal size of a generating subset of G. We prove that the order of the spectral gap is |G|−2/k when k−d(G)≍k and |G| lies in a density-1 subset of N or when k−2d(G)≍k. This extends, for Abelian groups, a celebrated result of Alon and Roichman (Random Structures Algorithms 5 (1994) 271–284). The aforementioned results all hold with high probability over the random Cayley graph.


  • Open Access

    Sensitivity of mixing times of Cayley graphs

    by Jonathan Hermon, Gady Kozma

    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 of the two mixing times goes to infinity. The Cayley graphs serving as an example have unbounded degrees. For non-transitive graphs, we construct bounded degree graphs for which the mixing time from the worst starting point for one graph is asymptotically smaller than the mixing time from the best starting point of the random walk on a network obtained by increasing some of the edge weights from 1 to $1+o(1)$ .


  • Open Access

    Sensitivity of mixing times of Cayley graphs

    by Jonathan Hermon, Gady Kozma

    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 of the two mixing times goes to infinity. The Cayley graphs serving as an example have unbounded degrees. For non-transitive graphs we construct bounded degree graphs for which the mixing time from the worst starting point for one graph is asymptotically smaller than the mixing time from the best starting point of the random walk on a network obtained by increasing some of the edge weights from 1 to $1+o(1)$.

  • Open Access

    Relaxation times are stationary hitting times of large sets

    by Jonathan Hermon

    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 spectral profile. We also provide in the non-reversible setup a related characterization for stationary expected hitting times of large sets.