Detecting tampering in a random hypercube

Ross G Pinsky (Technion)


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$.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-12

Publication Date: February 18, 2013

DOI: 10.1214/EJP.v18-2290


  • Baik, Jinho; Deift, Percy; Johansson, Kurt. On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc. 12 (1999), no. 4, 1119--1178. MR1682248
  • Berger, N. and Peres, Y. Detecting the Trail of a Random Walker in a Random Scenery, preprint, arXiv:1210.0314
  • Bollobás, Béla. Modern graph theory. Graduate Texts in Mathematics, 184. Springer-Verlag, New York, 1998. xiv+394 pp. ISBN: 0-387-98488-7 MR1633290
  • Harris, Matthew; Keane, Michael. Random coin tossing. Probab. Theory Related Fields 109 (1997), no. 1, 27--37. MR1469918
  • Janson, Svante. The numbers of spanning trees, Hamilton cycles and perfect matchings in a random graph. Combin. Probab. Comput. 3 (1994), no. 1, 97--126. MR1285693
  • Komlós, János; Szemerédi, Endre. Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Math. 43 (1983), no. 1, 55--63. MR0680304
  • Levin, David A.; Pemantle, Robin; Peres, Yuval. A phase transition in random coin tossing. Ann. Probab. 29 (2001), no. 4, 1637--1669. MR1880236
  • Logan, B. F.; Shepp, L. A. A variational problem for random Young tableaux. Advances in Math. 26 (1977), no. 2, 206--222. MR1417317
  • Pinsky, Ross G. Law of large numbers for increasing subsequences of random permutations. Random Structures Algorithms 29 (2006), no. 3, 277--295. MR2254492
  • Pinsky, Ross G. When the law of large numbers fails for increasing subsequences of random permutations. Ann. Probab. 35 (2007), no. 2, 758--772. MR2308596
  • Vershik, A. M.; Kerov, S. V. Asymptotic behavior of the maximum and generic dimensions of irreducible representations of the symmetric group. (Russian) Funktsional. Anal. i Prilozhen. 19 (1985), no. 1, 25--36, 96. MR0783703

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.