Do peaks of random labelings repel each other?
Status Open · unsolvedmath.comLLM status Open unverified
Top Open Problems Not reported cataloguedOpenOpenStatement
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
- S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 9500009 (AMR-094-0009), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
- S2 Burdzy - My favorite open problems (2009), Problem 9. Original source indexed by AMR-094-0009. https://sites.math.washington.edu/~burdzy/open_mathjax.php.
Statement licence: CC-BY-4.0 · Source file
Contributions 0
No attempts yet. Significant partial results and substantial reductions are welcome. Contribute an attempt.