• ### The Local Limit of Random Sorting Networks(1702.08368)

March 19, 2019 math.CO, math.PR
A sorting network is a geodesic path from $12 \cdots n$ to $n \cdots 21$ in the Cayley graph of $S_n$ generated by adjacent transpositions. For a uniformly random sorting network, we establish the existence of a local limit of the process of space-time locations of transpositions in a neighbourhood of $an$ for $a\in[0,1]$ as $n\to\infty$. Here time is scaled by a factor of $1/n$ and space is not scaled. The limit is a swap process $U$ on $\mathbb{Z}$. We show that $U$ is stationary and mixing with respect to the spatial shift and has time-stationary increments. Moreover, the only dependence on $a$ is through time scaling by a factor of $\sqrt{a(1-a)}$. To establish the existence of $U$, we find a local limit for staircase-shaped Young tableaux. These Young tableaux are related to sorting networks through a bijection of Edelman and Greene.
• ### Large deviations for subcritical bootstrap percolation on the random graph(1705.06815)

June 13, 2018 math.CO, math.PR
In bootstrap percolation, some vertices in a graph are initially active and others become active if eventually they have $r$ active neighbours. We identify the large deviations rate function for the event that a small set of initially active vertices eventually activates atypically many vertices in the Erd\H{o}s-R\'enyi graph. To this end, we compare trajectories of the dynamics, via Guseinov's discrete calculus of variations. This complements the fundamental work of Janson, {\L}uczak, Turova and Vallier, which studies the typical behaviour of the model, and the recent work of Torrisi, Garetto and Leonardi on supercritical large deviations. As an application, we obtain lower bounds for the size of the smallest sets that activate the entire graph, improving those recently obtained by Feige, Krivelevich and Reichman.
• ### Hyperbolic and Parabolic Unimodular Random Maps(1612.08693)

March 21, 2018 math.PR
We show that for infinite planar unimodular random rooted maps, many global geometric and probabilistic properties are equivalent, and are determined by a natural, local notion of average curvature. This dichotomy includes properties relating to amenability, conformal geometry, random walks, uniform and minimal spanning forests, and Bernoulli bond percolation. We also prove that every simply connected unimodular random rooted map is sofic, that is, a Benjamini-Schramm limit of finite maps.
• ### Perfect shuffling by lazy swaps(1802.05200)

March 8, 2018 math.CO, math.PR
We characterize the minimum-length sequences of independent lazy simple transpositions whose composition is a uniformly random permutation. For every reduced word of the reverse permutation there is exactly one valid way to assign probabilities to the transpositions. It is an open problem to determine the minimum length of such a sequence when the simplicity condition is dropped.
• ### Mallows permutations as stable matchings(1802.07142)

Feb. 20, 2018 math.PR
We show that the Mallows measure on permutations of $1,\ldots,n$ arises as the law of the unique Gale-Shapley stable matching of the random bipartite graph conditioned to be perfect, where preferences arise from a total ordering of the vertices but are restricted to the (random) edges of the graph. We extend this correspondence to infinite intervals, for which the situation is more intricate. We prove that almost surely every stable matching of the random bipartite graph obtained by performing Bernoulli percolation on the complete bipartite graph $K_{\mathbb{Z},\mathbb{Z}}$ falls into one of two classes: a countable family $(\sigma_n)_{n\in\mathbb{Z}}$ of tame stable matchings, in which the length of the longest edge crossing $k$ is $O(\log |k|)$ as $k\to\pm \infty$, and an uncountable family of wild stable matchings, in which this length is $\exp \Omega(k)$ as $k\to +\infty$. The tame stable matching $\sigma_n$ has the law of the Mallows permutation of $\mathbb{Z}$ (as constructed by Gnedin and Olshanski) composed with the shift $k\mapsto k+n$. The permutation $\sigma_{n+1}$ dominates $\sigma_{n}$ pointwise, and the two permutations are related by a shift along a random strictly increasing sequence.
• ### Counterexamples for percolation on unimodular random graphs(1710.03003)

Oct. 9, 2017 math.PR
We construct an example of a bounded degree, nonamenable, unimodular random rooted graph with $p_c=p_u$ for Bernoulli bond percolation, as well as an example of a bounded degree, unimodular random rooted graph with $p_c<1$ but with an infinite cluster at criticality. These examples show that two well-known conjectures of Benjamini and Schramm are false when generalised from transitive graphs to unimodular random rooted graphs.
• ### The string of diamonds is nearly tight for rumour spreading(1704.00874)

July 18, 2017 math.PR, cs.DC, cs.SI
For a rumour spreading protocol, the spread time is defined as the first time that everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any $n$-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O \left({n}^{1/3}{\log^{2/3} n}\right)$. This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari, and Woelfel (in Proceedings of ACM Symposium on Principles of Distributed Computing, 2016). Our bound is tight up to a factor of $O(\log n)$, as illustrated by the string of diamonds graph. We also show that if for a pair $\alpha,\beta$ of real numbers, there exists infinitely many graphs for which the two spread times are $n^{\alpha}$ and $n^{\beta}$ in expectation, then $0\leq\alpha \leq 1$ and $\alpha \leq \beta \leq \frac13 + \frac23 \alpha$; and we show each such pair $\alpha,\beta$ is achievable.
• ### Local max-cut in smoothed polynomial time(1610.04807)

April 10, 2017 math.PR, cs.DS
In 1988, Johnson, Papadimitriou and Yannakakis wrote that "Practically all the empirical evidence would lead us to conclude that finding locally optimal solutions is much easier than solving NP-hard problems". Since then the empirical evidence has continued to amass, but formal proofs of this phenomenon have remained elusive. A canonical (and indeed complete) example is the local max-cut problem, for which no polynomial time method is known. In a breakthrough paper, Etscheid and R\"oglin proved that the smoothed complexity of local max-cut is quasi-polynomial, i.e., if arbitrary bounded weights are randomly perturbed, a local maximum can be found in $n^{O(\log n)}$ steps. In this paper we prove smoothed polynomial complexity for local max-cut, thus confirming that finding local optima for max-cut is much easier than solving it.
• ### Limit laws for self-loops and multiple edges in the configuration model(1603.07172)

Feb. 2, 2017 math.PR
We consider self-loops and multiple edges in the configuration model as the size of the graph tends to infinity. The interest in these random variables is due to the fact that the configuration model, conditioned on being simple, is a uniform random graph with prescribed degrees. Simplicity corresponds to the absence of self-loops and multiple edges. We show that the number of self-loops and multiple edges converges in distribution to two independent Poisson random variables when the second moment of the empirical degree distribution converges. We also provide an estimate on the total variation distance between the number of self-loops and multiple edges and the Poisson limit of their sum. This revisits previous works of Bollob\'as, of Janson, of Wormald and others. The error estimates also imply sharp asymptotics for the number of simple graphs with prescribed degrees. The error estimates follow from an application of Stein's method for Poisson convergence, which is a novel method for this problem. The asymptotic independence of self-loops and multiple edges follows from a Poisson version of the Cram\'er-Wold device using thinning, which is of independent interest. When the degree distribution has infinite second moment, our general results break down. We can, however, prove a central limit theorem for the number of self-loops, and for the multiple edges between vertices of degrees much smaller than the square root of the size of the graph, or when we truncate the degrees similarly. Our results and proofs easily extend to directed and bipartite configuration models.
• ### Stability of geodesics in the Brownian map(1502.04576)

Dec. 1, 2016 math.PR
The Brownian map is a random geodesic metric space arising as the scaling limit of random planar maps. We strengthen the so-called confluence of geodesics phenomenon observed at the root of the map, and with this, reveal several properties of its rich geodesic structure. Our main result is the continuity of the cut locus at typical points. A small shift from such a point results in a small, local modification to the cut locus. Moreover, the cut locus is uniformly stable, in the sense that any two cut loci coincide outside a closed, nowhere dense set of zero measure. We obtain similar stability results for the set of points inside geodesics to a fixed point. Furthermore, we show that the set of points inside geodesics of the map is of first Baire category. Hence, most points in the Brownian map are endpoints. Finally, we classify the types of geodesic networks which are dense. For each $k\in\{1,2,3,4,6,9\}$, there is a dense set of pairs of points which are joined by networks of exactly $k$ geodesics and of a specific topological form. We find the Hausdorff dimension of the set of pairs joined by each type of network. All other geodesic networks are nowhere dense.
• ### Thresholds for contagious sets in random graphs(1611.10167)

Nov. 30, 2016 math.CO, math.PR
For fixed $r\geq 2$, we consider bootstrap percolation with threshold $r$ on the Erd\H{o}s-R\'enyi graph ${\cal G}_{n,p}$. We identify a threshold for $p$ above which there is with high probability a set of size $r$ which can infect the entire graph. This improves a result of Feige, Krivelevich and Reichman, which gives bounds for this threshold, up to multiplicative constants. As an application of our results, we also obtain an upper bound for the threshold for $K_4$-bootstrap percolation on ${\cal G}_{n,p}$, as studied by Balogh, Bollob\'as and Morris. We conjecture that our bound is asymptotically sharp. These thresholds are closely related to the survival probabilities of certain time-varying branching processes, and we derive asymptotic formulae for these survival probabilities which are of interest in their own right.
• ### Restrictions of H\"older continuous functions(1504.04789)

Nov. 26, 2016 math.CA, math.PR
For $0<\alpha<1$ let $V(\alpha)$ denote the supremum of the numbers $v$ such that every $\alpha$-H\"older continuous function is of bounded variation on a set of Hausdorff dimension $v$. Kahane and Katznelson (2009) proved the estimate $1/2 \leq V(\alpha)\leq 1/(2-\alpha)$ and asked whether the upper bound is sharp. We show that in fact $V(\alpha)=\max\{1/2,\alpha\}$. Let $\dim_{H}$ and $\overline{\dim}_{M}$ denote the Hausdorff and upper Minkowski dimension, respectively. The upper bound on $V(\alpha)$ is a consequence of the following theorem. Let $\{B(t): t\in [0,1]\}$ be a fractional Brownian motion of Hurst index $\alpha$. Then, almost surely, there exists no set $A\subset [0,1]$ such that $\overline{\dim}_{M} A>\max\{1-\alpha,\alpha\}$ and $B\colon A\to \mathbb{R}$ is of bounded variation. Furthermore, almost surely, there exists no set $A\subset [0,1]$ such that $\overline{\dim}_{M} A>1-\alpha$ and $B\colon A\to \mathbb{R}$ is $\beta$-H\"older continuous for some $\beta>\alpha$. The zero set and the set of record times of $B$ witness that the above theorems give the optimal dimensions. We also prove similar restriction theorems for deterministic self-affine functions and generic $\alpha$-H\"older continuous functions. Finally, let $\{\mathbf{B}(t): t\in [0,1]\}$ be a two-dimensional Brownian motion. We prove that, almost surely, there is a compact set $D\subset [0,1]$ such that $\dim_{H} D\geq 1/3$ and $\mathbf{B}\colon D\to \mathbb{R}^2$ is non-decreasing in each coordinate. It remains open whether $1/3$ is best possible.
• ### Unimodular Hyperbolic Triangulations: Circle Packing and Random Walk(1501.04677)

Aug. 30, 2016 math.PR
We show that the circle packing type of a unimodular random plane triangulation is parabolic if and only if the expected degree of the root is six, if and only if the triangulation is amenable in the sense of Aldous and Lyons. As a part of this, we obtain an alternative proof of the Benjamini-Schramm Recurrence Theorem. Secondly, in the hyperbolic case, we prove that the random walk almost surely converges to a point in the unit circle, that the law of this limiting point has full support and no atoms, and that the unit circle is a realisation of the Poisson boundary. Finally, we show that the simple random walk has positive speed in the hyperbolic metric.
• ### Increasing subsequences of random walks(1407.2860)

Aug. 12, 2016 math.PR
Given a sequence of $n$ real numbers $\{S_i\}_{i\leq n}$, we consider the longest weakly increasing subsequence, namely $i_1<i_2<\dots <i_L$ with $S_{i_k} \leq S_{i_{k+1}}$ and $L$ maximal. When the elements $S_i$ are i.i.d. uniform random variables, Vershik and Kerov, and Logan and Shepp proved that $\mathbb{E} L=(2+o(1)) \sqrt{n}$. We consider the case when $\{S_i\}_{i\leq n}$ is a random walk on $\mathbb{R}$ with increments of mean zero and finite (positive) variance. In this case, it is well known (e.g., using record times) that the length of the longest increasing subsequence satisfies $\mathbb{E} L\geq c\sqrt{n}$. Our main result is an upper bound $\mathbb{E} L\leq n^{1/2 + o(1)}$, establishing the leading asymptotic behavior. If $\{S_i\}_{i\leq n}$ is a simple random walk on $\mathbb{Z}$, we improve the lower bound by showing that $\mathbb{E} L \geq c\sqrt{n} \log{n}$. We also show that if $\{\mathbf{S}_i\}$ is a simple random walk in $\mathbb{Z}^2$, then there is a subsequence of $\{\mathbf{S}_i\}_{i\leq n}$ of expected length at least $cn^{1/3}$ that is increasing in each coordinate. The above one-dimensional result yields an upper bound of $n^{1/2 + o(1)}$. The problem of determining the correct exponent remains open.
• ### Boundaries of planar graphs, via circle packings(1311.3363)

June 27, 2016 math.PR
We provide a geometric representation of the Poisson and Martin boundaries of a transient, bounded degree triangulation of the plane in terms of its circle packing in the unit disc. (This packing is unique up to M\"obius transformations.) More precisely, we show that any bounded harmonic function on the graph is the harmonic extension of some measurable function on the boundary of the disk, and that the space of extremal positive harmonic functions, that is, the Martin boundary, is homeomorphic to the unit circle. All our results hold more generally for any "good"-embedding of planar graphs, that is, an embedding in the unit disc with straight lines such that angles are bounded away from $0$ and $\pi$ uniformly, and lengths of adjacent edges are comparable. Furthermore, we show that in a good embedding of a planar graph the probability that a random walk exits a disc through a sufficiently wide arc is at least a constant, and that Brownian motion on such graphs takes time of order $r^2$ to exit a disc of radius $r$. These answer a question recently posed by Chelkak (2014).
• ### Multicolour Poisson Matching(1605.06485)

May 25, 2016 math.PR
Consider several independent Poisson point processes on R^d, each with a different colour and perhaps a different intensity, and suppose we are given a set of allowed family types, each of which is a multiset of colours such as red-blue or red-red-green. We study translation-invariant schemes for partitioning the points into families of allowed types. This generalizes the 1-colour and 2-colour matching schemes studied previously (where the sets of allowed family types are the singletons {red-red} and {red-blue} respectively). We characterize when such a scheme exists, as well as the optimal tail behaviour of a typical family diameter. The latter has two different regimes that are analogous to the 1-colour and 2-colour cases, and correspond to the intensity vector lying in the interior and boundary of the existence region respectively. We also address the effect of requiring the partition to be a deterministic function (i.e. a factor) of the points. Here we find the optimal tail behaviour in dimension 1. There is a further separation into two regimes, governed by algebraic properties of the allowed family types.
• ### An isoperimetric inequality for planar triangulations(1604.05863)

April 20, 2016 math.CO, math.MG
We prove a discrete analogue to a classical isoperimetric theorem of Weil for surfaces with non-positive curvature. It is shown that hexagons in the triangular lattice have maximal volume among all sets of a given boundary in any triangulation with minimal degree 6.
• ### The half plane UIPT is recurrent(1601.00410)

Jan. 4, 2016 math.PR
We prove that the half plane version of the uniform infinite planar triangulation (UIPT) is recurrent. The key ingredients of the proof are a construction of a new full plane extension of the half plane UIPT, based on a natural decomposition of the half plane UIPT into independent layers, and an extension of previous methods for proving recurrence of weak local limits (still using circle packings).
• ### The Liouville property for groups acting on rooted trees(1307.5652)

July 9, 2015 math.PR, math.GR
We show that on groups generated by bounded activity automata, every symmetric, finitely supported probability measure has the Liouville property. More generally we show this for every group of automorphisms of bounded type of a rooted tree. For automaton groups, we also give a uniform upper bound for the entropy of convolutions of every symmetric, finitely supported measure.
• ### The Hilbert Schmidt version of the commutator theorem for zero trace matrices(1503.07980)

March 27, 2015 math.FA
Let $A$ be a $m\times m$ complex matrix with zero trace. Then there are $m\times m$ matrices $B$ and $C$ such that $A=[B,C]$ and $\|B\|\|C\|_2\le (\log m+O(1))^{1/2}\|A\|_2$ where $\|D\|$ is the norm of $D$ as an operator on $\ell_2^m$ and $\|D\|_2$ is the Hilbert--Schmidt norm of $D$. Moreover, the matrix $B$ can be taken to be normal. Conversely there is a zero trace $m\times m$ matrix $A$ such that whenever $A=[B,C]$, $\|B\|\|C\|_2\ge |\log m-O(1)|^{1/2}\|A\|_2$ for some absolute constant $c>0$.
• ### Random walks on stochastic hyperbolic half planar triangulations(1408.4196)

Aug. 19, 2014 math.PR
We study the simple random walk on stochastic hyperbolic half planar triangulations constructed in Angel and Ray [3]. We show that almost surely the walker escapes the boundary of the map in positive speed and that the return probability to the starting point after n steps scales like $\exp(-cn^{1/3})$.
• ### Classification of Half Planar Maps(1303.6582)

Feb. 26, 2014 math.PR
We characterize all translation invariant half planar maps satisfying a certain natural domain Markov property. For p-angulations with p \ge 3 where all faces are simple, we show that these form a one-parameter family of measures H^{(p)}_{alpha}. For triangulations we also establish existence of a phase transition which affects many properties of these maps. The critical maps are the well known half plane uniform infinite planar maps. The sub-critical maps are identified as all possible limits of uniform measures on finite maps with given boundary and area.
• ### The local limit of unicellular maps in high genus(1309.6254)

Sept. 24, 2013 math.CO, math.PR
We show that the local limit of unicellular maps whose genus is proportional to the number of edges is a supercritical geometric Galton-Watson tree conditioned to survive. The proof relies on enumeration results obtained via the recent bijection given by the second author together with Feray and Fusy.
• ### A Tight Upper Bound on Acquaintance Time of Graphs(1307.6029)

July 23, 2013 math.CO, cs.DM
In this note we confirm a conjecture raised by Benjamini et al. \cite{BST} on the acquaintance time of graphs, proving that for all graphs $G$ with $n$ vertices it holds that $\AC(G) = O(n^{3/2})$, which is tight up to a multiplicative constant. This is done by proving that for all graphs $G$ with $n$ vertices and maximal degree $\Delta$ it holds that $\AC(G) \leq 20 \Delta n$. Combining this with the bound $\AC(G) \leq O(n^2/\Delta)$ from \cite{BST} gives the foregoing uniform upper bound of all $n$-vertex graphs. We also prove that for the $n$-vertex path $P_n$ it holds that $\AC(P_n)=n-2$. In addition we show that the barbell graph $B_n$ consisting of two cliques of sizes $\ceil{n/2}$ and $\floor{n/2}$ connected by a single edge also has $\AC(B_n) = n-2$. This shows that it is possible to add $\Omega(n^2)$ edges to $P_n$ without changing the $\AC$ value of the graph.
• ### Avoidance Coupling(1112.3304)

July 10, 2013 math.PR
We examine the question of whether a collection of random walks on a graph can be coupled so that they never collide. In particular, we show that on the complete graph on n vertices, with or without loops, there is a Markovian coupling keeping apart Omega(n/log n) random walks, taking turns to move in discrete time.