@article{EJP2290,
author = {Ross Pinsky},
title = {Detecting tampering in a random hypercube},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {18},
year = {2013},
keywords = {random graph, random hypercube, total variation norm, detection},
abstract = {Consider the random hypercube $H_2^n(p_n)$ obtained from the hypercube $H_2^n$ by deleting any given edge with probabilty $1 -p_n$, independently of all the other edges. A diameter path in $H_2^n$ is a longest geodesic path in $H_2^n$. Consider the following two ways of tampering with the random graph $H_2^n(p_n)$: (i) choose a diameter path at random and adjoin all of its edges to $H_2^n(p_n)$; (ii) choose a diameter path at random from among those that start at $0=(0,\cdots, 0)$, and adjoin all of its edges to $H_2^n(p_n)$. We study the question of whether these tamperings are detectable asymptotically as $n\to\infty$.},
pages = {no. 28, 1-12},
issn = {1083-6489},
doi = {10.1214/EJP.v18-2290},
url = {http://ejp.ejpecp.org/article/view/2290}}