Detecting tampering in a random hypercube

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, . . ., 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 o i n f t y

.