--- title: "Superexponential strict-improvement distances in median graphs" date: 2026-09-21 version: "0.1.0-candidate" doi: 10.5281/zenodo.22878369 pdf: https://github.com/ipitchford/median-radius-obstructions/releases/download/v0.1.0-candidate/median-radius-obstructions-v0.1.0-candidate.pdf repository: https://github.com/ipitchford/median-radius-obstructions archive: https://zenodo.org/records/22878369 license: CC0-1.0 status: unrefereed (internally replayed; not peer reviewed, not independently reproduced, not formally verified) --- # Superexponential strict-improvement distances in median graphs ## Summary A point in a network can have no strictly better center nearby and still fail to be a center. This candidate constructs median graphs where the first strict improvement is extremely far away relative to cube dimension. It answers a proposed dimension-linear locality question negatively. ## Summary for specialists For every odd $d\ge3$, an explicit finite median graph of cube dimension $d$ has a noncentral origin with exact first strict eccentricity improvement distance $2F_d-1$. A transfer proposition realizes the minimum integer $\ell_1$ separation norm of any strictly feasible sign system as that graph distance. Alon–Vũ's threshold-weight theorem then gives the lower bound $d^{d/2}2^{-(2+o(1))d}$ for every sufficiently large $d$. For binary corner profiles on integer grids, a determinant argument supplies an upper bound $d^{d/2+1}$. Consequently the extremal logarithm is $(1/2+o(1))d\log_2d$. That upper bound is restricted to the corner-profile model. ## Technical account In the integer box $[-N,N]^d$, the distance from $x$ to corner $Ns$ is $dN-s\cdot x$. Thus improving the maximum distance to selected corners requires every corresponding dot product to be positive. Integer threshold representations can force the first feasible vector to have very large norm. An alternating AND/OR function yields an exact Fibonacci example with a self-contained proof. Long pendant paths at selected corners make their far endpoints determine ordinary eccentricity; the paths preserve the median property and cube dimension. The stronger all-dimensions estimate uses established work of Alon and Vũ. The threshold-weight theorem itself is not a new result of this release. The cover is a schematic grid-and-pendant-path composition, not a full drawing of a high-dimensional example or numerical evidence. ## Evidence, assurance and limitations The written proofs establish the proposed mathematical result. The exact checker audits eight finite Boolean instances, excludes closer improving grid vertices in dimensions three and five, and checks every distinct triple in the complete 51-vertex example. Normal and optimized Python runs include three negative controls. This remains an unrefereed candidate. Producer replay and internal model-mediated editorial reports do not establish unaffiliated reproduction, journal peer review, formal verification or historical priority. A supplied separate checker was rerun locally, but its authorship and unaffiliated status are unverified. Strict decrease matters: in the smallest example an equal-value move of length two permits a later improvement of length one. No running-time lower bound for arbitrary algorithms follows. Cube dimension is not graph order, and the constructed graphs can be large. ## Who should care, and why | Audience | Potential use | Required caution | |---|---|---| | Graph theorists | Test radius-unimodality conjectures against explicit median graphs | General median-graph upper bounds remain open here | | Threshold theorists | Translate integer-weight lower bounds into graph locality | The cited weight theorems are prior work | | Algorithm researchers | Identify limits of immediate-descent certificates | Plateau moves and global algorithms remain available | ## Why the problem matters A local optimality test is useful only when its inspection radius is justified. These examples show that the proposed radius cannot scale linearly with cube dimension, or even as any fixed-base exponential. The result clarifies what a local certificate can promise; it does not undermine established global eccentricity algorithms. ## How to inspect or reproduce the recorded checks Download and extract the versioned evidence archive. With standard-library Python, run: ``` python3 verify.py --output replay.json python3 -O verify.py --output replay-optimized.json ``` Compare both outputs with `verification.json`, then check `MANIFEST.sha256`. Read Sections 2–4 for the universal proofs, and the primary Alon–Vũ source for the external theorem. Finite replay is not a substitute for those arguments. ## The most valuable next projects Determine upper bounds for all median graphs, study plateau-permitting movement, and reduce graph order while retaining large strict-improvement distances. An unaffiliated proof review and separate reimplementation would strengthen assurance without changing the current status retrospectively. ## What is in the evidence package The package includes PDF, Markdown and TeX manuscripts; the exact verifier and expected output; claim and source records; internal editorial reports; the response to the supplied review; licence boundaries; and a complete file manifest. Original prose and data use CC0, and original code uses MIT. Cited papers and supplied third-party review files are linked or described, not relicensed or redistributed. ## Open directions for follow-up research - Determine upper locality bounds for ordinary eccentricity on all finite median graphs. - Understand what plateau moves permit and their dependence on dimension. - Find smaller graphs realizing large strict-improvement distances. ## Research process, metrics and reusable methods This is prospective process metadata under the Evidence Press operating model and research-metrics policy. It records the intended handoff, measured scope and claim boundary; it is not evidence that the method accelerated this work. - Work ID: ep-work:median-radius-obstructions - Attempt and metric receipts: ep-attempt:median-radius-obstructions-publication: published / positive; scope publication-only; target Internal editorial approval, immutable GitHub and Zenodo candidate assets, and complete Evidence Press page/media/canonical readback.; active forecast 150 minutes (90-240); Fermi components Source repairs and internal editorial gate: 1 x 30/50/80 minutes low/central/high (Established publication route; not an empirical speed comparison.); Immutable archives and communication assets: 1 x 30/50/80 minutes low/central/high (Established publication route; not an empirical speed comparison.); Composite CI and two deployment cycles: 1 x 30/50/80 minutes low/central/high (Established publication route; not an empirical speed comparison.); positive-signal/closure probabilities 0.95/0.85 within 240 active minutes; observed active-agent/human/compute/wait/blocked/rework minutes 4/unknown/unknown/1/0/0; cycles positive/negative/inconclusive 0/0/0; falsification gates 3; architectures tested/rejected 1/0; result target-closed; target reached true; forecast error -146 minutes; ratio 0.0267; inside interval false; positive-signal/target-closure Brier scores 0.0025/0.0225; missing telemetry activeHumanMinutes: Human effort not instrumented.; computeMinutes: No separately instrumented substantive-compute total; ordinary validation excluded.; deduplicatedModelTokens: Supported fork-aware counter unavailable.; uncachedInputTokens: Runtime cache/token accounting unavailable.; appended measurement corrections measurement.reworkMinutes -> metrics.outcome.reworkMinutes: Preserve intake null; retain scoped lower-bound terminal value and variance explanation. (reason: The intake retains unknown total rework. Terminal zero refers only to no separately timed rework interval in the instrumented final segment, not absence of earlier packaging repairs.). Work ledger: https://evidencepress.org/api/work-ledger.json. Metrics policy: https://evidencepress.org/api/research-metrics-policy.json - Intended aims: science - Artifact roles: research-output, evidence-assessment, communication - Decision object: counterexample — Exact sign-separation transfer and strict-improvement obstruction family. Scope: Dimension-linear radius unimodality question; corner-profile upper bound is restricted. - Reusable methods: Certificate-first, proof-carrying research (certificate-first); Adversarial scientific controls (adversarial-controls); Assurance as a vector (assurance-vector); Agent-readable research objects (agent-readable-research-object). Registry: https://evidencepress.org/api/method-registry.json - Targeted clocks: assurance, publication - Semantic bridge: explicit — Corner distances are dN minus signed dot products; strict improvement is equivalent to integer strict separation. Pendant paths preserve cube dimension. Remaining risks: Written proof and external threshold theorem require mathematical judgment.; Plateau-permitting algorithms are outside the obstruction.; Priority remains unestablished.. - Human judgement gates: Assess the source-to-claim correspondence and written proof.; Preserve rights, status and priority boundaries.; Publication is authorised; external review is a separate dimension. - Next assurance action: Inspect and independently reproduce the bounded result; explore extensions separately. External review is not a publication prerequisite. - Claim ceiling: Unrefereed candidate. No authenticated external peer review, formal verification, historical priority, or algorithmic running-time lower bound is established. - Aim-scoped impact evidence: - science: NO_IMPACT_EVIDENCE — Inspectable locality counterexample and exact graph transfer in Producer-coordinated mathematical publication; design none; comparator None.; estimand No acceleration or impact effect estimated.; no real-world effect evidence asserted ## Verification status Unrefereed candidate. No authenticated external peer review, formal verification, historical priority, or algorithmic running-time lower bound is established. ## References 1. Ducoffe (2026), Radius functions in median graphs: source Open Problem 2, p. 506. 2. Alon and Vũ (1997), Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs: external large-weight theorem. 3. Bergé, Ducoffe and Habib (2025), Quasilinear-time eccentricities computation, and more, on median graphs. 4. Chalopin et al. (2025), On G^p-unimodality of radius functions in graphs.