Convergence of uniform 231-avoiding permutations to the Brownian binary tree

Let [n]={1,,n}[n]=\{1,\ldots,n\}, let SnS_n be a uniform 231231-avoiding permutation of [n][n], and define its normalized graph by

gr(Sn):={(i/n,Sn(i)/n):i[n]}.\operatorname{gr}(S_n):=\{(i/n,S_n(i)/n):i\in[n]\}.

View gr(Sn)\operatorname{gr}(S_n) as a random compact subset of [0,1]2[0,1]^2, taking values in (K([0,1]2),dhaus)(\mathcal{K}([0,1]^2),d_{\operatorname{haus}}), where dhausd_{\operatorname{haus}} is the Hausdorff metric. Conjecture. As nn\to\infty, gr(Sn)\operatorname{gr}(S_n) converges in law to the Brownian binary tree on (0,1)(0,1), with respect to the Hausdorff topology on K([0,1]2)\mathcal{K}([0,1]^2). The conjecture proposes a universality connection between large uniform pattern-avoiding permutations and the Brownian binary tree, motivated by the comparison with the limiting tree associated with Rémy's tree growth chain; its resolution is not indicated here.

Sources & referencesView supporting material

Primary source

Julian Gerstenberg, “Exchangeable interval hypergraphs and limits of ordered discrete structures”, arXiv:1802.09015 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.