{
"id": "1702.08368",
"version": "v1",
"published": "2017-02-27T16:44:46.000Z",
"updated": "2017-02-27T16:44:46.000Z",
"title": "The Local Limit of Random Sorting Networks",
"authors": [
"Omer Angel",
"Duncan Dauvergne",
"Alexander E. Holroyd",
"Bálint Virág"
],
"comment": "35 pages, 5 figures",
"categories": [
"math.PR",
"math.CO"
],
"abstract": "A sorting network is a shortest path from $12 \\dots n$ to $n \\dots 21$ in the Cayley graph of $S_n$ generated by adjacent transpositions. We establish existence of a local limit of sorting networks in a neighbourhood of $an$ for $a\\in[0,1]$ as $n\\to\\infty$, with time scaled by a factor of $n$. 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)}$.",
"revisions": [
{
"version": "v1",
"updated": "2017-02-27T16:44:46.000Z"
}
],
"analyses": {
"subjects": [
"60C05",
"05E10",
"68P10"
],
"keywords": [
"random sorting networks",
"local limit",
"cayley graph",
"adjacent transpositions",
"time-stationary increments"
],
"note": {
"typesetting": "TeX",
"pages": 35,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}