• ### 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.
• ### Circular support in random sorting networks(1802.08933)

April 9, 2018 math.CO, math.PR
A sorting network is a shortest path from $12 \cdots n$ to $n \cdots 2 1$ in the Cayley graph of the symmetric group generated by adjacent transpositions. For a uniform random sorting network, we prove that in the global limit, particle trajectories are supported on $\pi$-Lipschitz paths. We show that the weak limit of the permutation matrix of a random sorting network at any fixed time is supported within a particular ellipse. This is conjectured to be an optimal bound on the support. We also show that in the global limit, trajectories of particles that start within distance $\epsilon$ of the edge are within $\sqrt{2\epsilon}$ of a sine curve in uniform norm.
• ### Asymptotic zero distribution of random orthogonal polynomials(1801.10125)

March 22, 2018 math.PR, math.CV
We consider random polynomials of the form $H_n(z)=\sum_{j=0}^n\xi_jq_j(z)$ where the $\{\xi_j\}$ are i.i.d non-degenerate complex random variables, and the $\{q_j(z)\}$ are orthonormal polynomials with respect to a compactly supported measure $\tau$ satisfying the Bernstein-Markov property on a regular compact set $K \subset \mathbb{C}$. We show that if $\mathbb{P}(|\xi_0|>e^{|z|})=o(|z|^{-1})$, then the normalized counting measure of the zeros of $H_n$ converges weakly in probability to the equilibrium measure of $K.$ This is the best possible result, in the sense that the roots of $G_n(z)=\sum_{j=0}^n\xi_jz^j$ fail to converge in probability to the appropriate equilibrium measure when the above condition on the $\xi_j$ is not satisfied. In addition, we give a multivariable version of this result. We also consider random polynomials of the form $\sum_{k=0}^n\xi_kf_{n,k}z^k$, where the coefficients $f_{n,k}$ are complex constants satisfying certain conditions, and the random variables $\{\xi_k\}$ satisfy $\mathbb{E} \log(1 + |\xi_0|) < \infty$. In this case, we establish almost sure convergence of the normalized counting measure of the zeros to an appropriate limiting measure. Again, this is the best possible result in the same sense as above.
• ### The Archimedean limit of random sorting networks(1802.08934)

March 19, 2018 math.CO, math.PR
A sorting network (also known as a reduced decomposition of the reverse permutation), is a shortest path from $12 \cdots n$ to $n \cdots 21$ in the Cayley graph of the symmetric group $S_n$ generated by adjacent transpositions. We prove that in a uniform random $n$-element sorting network $\sigma^n$, that all particle trajectories are close to sine curves with high probability. We also find the weak limit of the time-$t$ permutation matrix measures of $\sigma^n$. As a corollary of these results, we show that if $S_n$ is embedded into $\mathbb{R}^n$ via the map $\tau \mapsto (\tau(1), \tau(2), \dots \tau(n))$, then with high probability, the path $\sigma^n$ is close to a great circle on a particular $(n-2)$-dimensional sphere in $\mathbb{R}^n$. These results prove conjectures of Angel, Holroyd, Romik, and Virag.