Noise sensitivity under the Schaeffer bijection

Definitions and mathematical statement

Let $\Phi_n$ be the intended Schaeffer-based encoding of a quadrangulation by $2n$ random bits, and let $\xi=(\xi_1,\ldots,\xi_{2n})$ be the input. Under the usual unbiased product-bit interpretation, form $\xi^\varepsilon$ by independently replacing each coordinate, with probability $\varepsilon$, by a fresh independent unbiased bit. Replacement is not deterministic flipping; the actual flip probability is $\varepsilon/2$.

For $Q_n=\Phi_n(\xi)$ and $Q_n^\varepsilon=\Phi_n(\xi^\varepsilon)$, let $D_n$ and $D_n^\varepsilon$ be graph diameters. Choose a median $m_n$ of $D_n$ and a threshold/tie convention, for example \[ F_n(\xi)=\mathbf1\{D_n>m_n\},\qquad p_n(\varepsilon)=\Pr(F_n(\xi)\ne F_n(\xi^\varepsilon)). \] Estimate this crossing probability, and more generally determine noise sensitivity of natural geometric observables. In the product-space convention, Boolean noise sensitivity at fixed $\varepsilon>0$ asks whether \[ \operatorname{Cov}(F_n(\xi),F_n(\xi^\varepsilon))\longrightarrow0. \] Balanced threshold events would then have crossing probability tending to $1/2$, rather than one. Other limiting regimes, including $\varepsilon=\varepsilon_n\to0$, require separate specification.

The source does not supply the bit-to-map procedure or its sampling law. Schaeffer encodings usually involve tree and label data with validity constraints, so the record must explain how arbitrary perturbed bit strings remain valid inputs and what distribution they induce. No uniform-quadrangulation law is inferred merely from the bijection's name. Map size/rooting, additional randomness, median ties, and fixed-noise versus vanishing-noise regimes are also not fixed.

Short English statement

Measure how resampling bits in the intended Schaeffer encoding changes geometric observables, especially whether diameter moves across its median. Fix the encoding law, validity after perturbation, median ties, and noise regime.

Sources

• Itai Benjamini, Random Planar Metrics, Section 3 item (6), PDF page 3, https://www.wisdom.weizmann.ac.il/~itai/randomplanar2.pdf#page=3; preserved copy https://arquivo.pt/noFrame/replay/20201231041544id_/http://www.wisdom.weizmann.ac.il/~itai/randomplanar2.pdf; accessed 2026-07-29. The supplied provenance reports extracted text checked against rendered pages.
• The Schaeffer bijection is named in the source without a separate citation or a full bit-level implementation.
• Local registry data/unsolvedmath/problems.json, permanent UnsolvedMath ID $10000079$, source code catalogue entry, Noise sensitivity under the Schaeffer bijection. Dataset attribution: Ulam AI and the UnsolvedMath Contributors.