
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 spacetime 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
timestationary increments. Moreover, the only dependence on $a$ is through
time scaling by a factor of $\sqrt{a(1a)}$. To establish the existence of $U$,
we find a local limit for staircaseshaped Young tableaux. These Young tableaux
are related to sorting networks through a bijection of Edelman and Greene.

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}sR\'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.

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
BenjaminiSchramm limit of finite maps.

We characterize the minimumlength 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.

We show that the Mallows measure on permutations of $1,\ldots,n$ arises as
the law of the unique GaleShapley 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.

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
wellknown conjectures of Benjamini and Schramm are false when generalised from
transitive graphs to unimodular random rooted graphs.

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.

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 NPhard 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
maxcut problem, for which no polynomial time method is known. In a
breakthrough paper, Etscheid and R\"oglin proved that the smoothed complexity
of local maxcut is quasipolynomial, 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 maxcut, thus
confirming that finding local optima for maxcut is much easier than solving
it.

We consider selfloops 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 selfloops and multiple edges. We show that the number of selfloops
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 selfloops 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 selfloops and multiple edges follows
from a Poisson version of the Cram\'erWold 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 selfloops, 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.

The Brownian map is a random geodesic metric space arising as the scaling
limit of random planar maps. We strengthen the socalled 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.

For fixed $r\geq 2$, we consider bootstrap percolation with threshold $r$ on
the Erd\H{o}sR\'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
timevarying branching processes, and we derive asymptotic formulae for these
survival probabilities which are of interest in their own right.

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 selfaffine functions and generic
$\alpha$H\"older continuous functions.
Finally, let $\{\mathbf{B}(t): t\in [0,1]\}$ be a twodimensional 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
nondecreasing in each coordinate. It remains open whether $1/3$ is best
possible.

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
BenjaminiSchramm 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.

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 onedimensional result yields an upper bound of $n^{1/2 + o(1)}$. The
problem of determining the correct exponent remains open.

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).

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
redblue or redredgreen. We study translationinvariant schemes for
partitioning the points into families of allowed types. This generalizes the
1colour and 2colour matching schemes studied previously (where the sets of
allowed family types are the singletons {redred} and {redblue} 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 1colour and 2colour 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.

We prove a discrete analogue to a classical isoperimetric theorem of Weil for
surfaces with nonpositive 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.

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).

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.

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 HilbertSchmidt 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
mO(1)^{1/2}\A\_2$ for some absolute constant $c>0$.

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})$.

We characterize all translation invariant half planar maps satisfying a
certain natural domain Markov property. For pangulations with p \ge 3 where
all faces are simple, we show that these form a oneparameter 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 subcritical
maps are identified as all possible limits of uniform measures on finite maps
with given boundary and area.

We show that the local limit of unicellular maps whose genus is proportional
to the number of edges is a supercritical geometric GaltonWatson 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.

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)=n2$. 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) = n2$. This shows that it is possible to add $\Omega(n^2)$
edges to $P_n$ without changing the $\AC$ value of the graph.

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.