Nonlocality of Cover-Time Changes Under Edge Addition
Abstract
Let G be a finite connected simple graph, let uv be a nonedge, and let s be a starting vertex. We study the exact change in the expected cover time of simple random walk when uv is inserted. A killed Green matrix update, combined with target-set inclusion-exclusion, gives an exact formula using only the original graph. The response can have either sign. Our main result is a nonlocality theorem. For every radius r≥ 1, we construct two marked configurations whose ambient-degree-labelled radius-r neighbourhoods at s,u,v are isomorphic but whose fixed-start cover-time responses have opposite signs. The construction also matches the three marked degrees, the marked distance, and the effective resistance Ruv. The two graphs have different orders; equal-order nonlocality remains open. We complement this result with a conductance interpolation theorem and an occupation interpretation of its high-conductance coefficient. After contracting u and v, that coefficient is a positive multiple of the expected pre-cover occupation of the contracted vertex, and its zero case is classified exactly. A path with two pendant insertion endpoints is solved for all starting vertices and shows a sharp change of sign across the start set.
Related
- Eigenspaces of Preserved Graph Laplacian Eigenvalues under Positive Edge-Weight Addition
- Two-disjoint-cycle-cover edge bipancyclicity in Cartesian products
- Edge-addition monotonicity of positive p-energy fails for every p >= 1
- Limit law for Brownian cover time of the two dimensional torus
- A limit law for the cover time of the two-dimensional discrete torus
BibTeX
@misc{si2026nonlocality,
title = {{Nonlocality of Cover-Time Changes Under Edge Addition}},
author = {Ian Meng Si},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.27474},
eprint = {2608.27474},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27474},
}
RIS
TY - UNPB
TI - Nonlocality of Cover-Time Changes Under Edge Addition
AU - Ian Meng Si
PY - 2026
DA - 2026/08/19
PB - arXiv
DO - 10.48550/arxiv.2608.27474
UR - https://arxiv.org/abs/2608.27474
AB - Let G be a finite connected simple graph, let uv be a nonedge, and let s be a starting vertex. We study the exact change in the expected cover time of simple random walk when uv is inserted. A killed Green matrix update, combined with target-set inclusion-exclusion, gives an exact formula using only the original graph. The response can have either sign. Our main result is a nonlocality theorem. For every radius r≥ 1, we construct two marked configurations whose ambient-degree-labelled radius-r neighbourhoods at s,u,v are isomorphic but whose fixed-start cover-time responses have opposite signs. The construction also matches the three marked degrees, the marked distance, and the effective resistance R_uv. The two graphs have different orders; equal-order nonlocality remains open. We complement this result with a conductance interpolation theorem and an occupation interpretation of its high-conductance coefficient. After contracting u and v, that coefficient is a positive multiple of the expected pre-cover occupation of the contracted vertex, and its zero case is classified exactly. A path with two pendant insertion endpoints is solved for all starting vertices and shows a sharp change of sign across the start set.
ER -