Detecting tampering in a random hypercube (Q388876)

Let us assume the graph of the hypercube \(H_2^n\), and let us consider its random subgraph obtained by deleting each edge with probability \(1-p_n\). Another measure on subgraphs of \(H_2^n\) can be obtained by additionally adding edges along a randomly chosen geodesic (that is, a path which makes one step in every of the \(n\) directions). Yet another measure can be obtained by adding edges along a randomly chosen geodesic starting at a fixed vertex of the hypecube. These additional modifications are called ``tamperings''.NEWLINENEWLINEThe paper studies the question how different these three measures are. The qualitative asymptotic behavior of the total variation distance of these measures as a function of \(p_n\)'s is described.