Math-1693 · mathematics · Probability

Math-1693

Do peaks of random labelings repel each other?

Status Open · unsolvedmath.comLLM status Open unverified

Top Open Problems Not reported cataloguedOpenOpen

Statement

Definitions and mathematical statement

For $n\ge2$, let $G_n$ be the grid graph with vertex set $\{1,\ldots,n\}^2$, joining two vertices when their Euclidean coordinates differ by one in exactly one coordinate. There is no wrap-around at the boundary. Choose a bijection $\ell:V(G_n)\to\{1,\ldots,n^2\}$ uniformly from all $(n^2)!$ labelings.

A vertex $v$ is a peak when $\ell(v)>\ell(w)$ for every neighbor $w$ of $v$. Condition the labeling on the event that it has exactly two peaks, denoted $u_n$ and $v_n$ in either order. Let \[ \rho_n=d_{G_n}(u_n,v_n) =|u_n^{(1)}-v_n^{(1)}|+|u_n^{(2)}-v_n^{(2)}|. \] Does $\rho_n/n$ converge in distribution to zero under these conditional laws as $n\to\infty$?

Because the proposed limit is deterministic, the question is equivalently whether, for every $\varepsilon>0$, \[ \mathbb P\left(\rho_n>\varepsilon n\mid \ell\text{ has exactly two peaks}\right)\longrightarrow0. \] The conditioning is performed separately for each finite grid, on an event of positive probability. Boundary vertices are tested against only their actual neighbors. The assertion concerns distances on the linear scale of the square; it allows the unscaled distance to grow. No ordering of the two peaks is needed, and the question is about their positions rather than the difference between their numerical labels.

Short English statement

Conditioned on exactly two peaks in a uniformly labeled square grid, does their separation become negligible compared with the side length?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 0

No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.