Monotone subsequences in locally uniform random permutations (Q6116328)

This paper studies monotone subsequences in locally uniform random permutations. Let \((\Omega,\rho)\) be a density domain and \(\{\tau_{\gamma}\}_{\gamma>0}\) be random point processes on \(\Omega\) approaching a Poisson point process with intensity function \(\gamma\rho\) as \(\gamma\) tends to infinity. It is shown that for any \(r\ge0\), for any \(\varepsilon>0\) asymptotically almost surely as \(\gamma\rightarrow\infty\), for every maximal \(\lfloor r\sqrt{\gamma}\rfloor\)-decreasing subset \(P\) of \(\tau_{\gamma}\) there is a \(u\in\mathcal{U}_{0,r}(\Omega)\) with \(F_{\rho}(u)=F_{\max}(r):=\sup_{u\in\mathcal{U}_r(\Omega)}F_{\rho}(u)\) such that \(\|k_P/\sqrt{\gamma}-u\|_{\Omega}<\varepsilon\), where \(k_P(x,y)\) is the maximal size of an increasing subsets of \(P\cap((-\infty,x]x(-\infty,y])\), \(F_{\rho}(u)=\|L(\rho,u_xu_y)\|_{\Omega}\): \(\mathcal{U}(\Omega)\rightarrow\mathbb{R}\) is a functional defined on \(\mathcal{U}(\Omega)\) and \(\mathcal{U}(\Omega)=\cup_{r\ge0}\mathcal{U}_r(\Omega)\) with \(\mathcal{U}_r(\Omega)\) being the set of doubly increasing functions \(u\) on \(\Omega\) with diameter of \(u(\Omega)\) no more than \(r\), and \(\mathcal{U}_{0,r}(\Omega)\) is the subset of \(\mathcal{U}_r(\Omega)\) consisting of functions with values in \([0,r]\). Moreover, let \(\Gamma^{(\gamma)}\) be the size of a maximal \(\lfloor r\sqrt{\gamma}\rfloor\)-decreasing subset of \(\tau_{\gamma}\). Then it is shown that \(\Gamma^{(\gamma)}/\gamma\rightarrow F_{\max}(r)\) in probability as \(\gamma\) approaches infinity.