Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a $p$ fraction of edges from $G$ arbitrarily. What is a lower bound on the probability that a $t$ step random walk on $G$ (with uniformly random starting vertex and transition at each step) is entirely contained in $G'$? I am most interested in the regime where $t$ is order $n$ and $p$ is order $\log n /n$ and I suspect one should be able to prove a lower bound of the form $2^{-pt}$.

I can show using small-set expansion on the hypercube that $G'$ has a connected component of size at least $2^{n(1-p)}$, but do not know how to argue about the random walk not leaving the component.


1 Answer 1


In 1959, Mulholland and Smith [1] proved that for any symmetric nonnegative matrix $A$, any integer $k \ge 1$ and any nonnegative vector $z$, $$(z^T A^k z) (z^Tz)^{k-1} \ge (z^T A z)^k \; \; \; (*) $$ This was rediscovered by Blakley-Roy (1965). More on the history below.

Let $m=n2^{n-1}(1-p)$ denote the number of edges in $G'$. If $A$ is the $2^n$ by $2^n$ adjacency matrix of $G'$ and $z$ is an all ones vector of length $2^n$, then $z^T A Z=2m $ so (*) implies that the number $W_k$ of walks of length $k$ in $G'$ is at least $(2m)^k/(2^n)^{k-1}$. Therefore the probability $P_k$ that a $k$ step random walk on $G$ (with uniformly random starting vertex and transition at each step) is entirely contained in $G′$ satisfies $$P_k=2^{-n}W_k n^{-k} \ge \Bigl(\frac{2m}{n2^n}\Bigr)^k =(1-p)^k . $$ This lower bound is sharp in many cases, e.g., if $p=b/n$ and all edges of the hypercube where one of the the first $b$ coordinates differs across the edge are erased to form $G'$. The argument above extends to any graph $G$, it need not be the hypercube. Upper bounds are discussed in [7] and the references therein.

The inequality (*) is a (proved) special case of the (still open} Sidorenko conjecture ([3],[4]) which is equivalent to a conjecture of Erdos-Simonovitz. For updates on the conjecture see [5], [6].

[1] H. P. Mulholland and C. A. B. Smith. An inequality arising in genetical theory. Amer. Math. Monthly, 66(8):673–683, 1959.

[2] G. R. Blakley and P. Roy. H¨older type inequality for symmetric matrices with nonnegative entries. Proc. Amer. Math. Soc., 16(6):1244–1245, 1965.

[3] A. Sidorenko. Inequalities for functionals generated by bipartite graphs. Discrete Math. Appl., 2(5):489–504, 1992.

[4] A. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combinatorics, 9(2):201–204, 1993.

[5] B. Szegedy. An information theoretic approach to Sidorenko’s conjecture. arXiv:1406.6738, 2014.

[6] Alexander Sidorenko , Inequalities for doubly nonnegative functions https://arxiv.org/pdf/1905.08210.pdf

[7] Levin, David A., and Yuval Peres. "Counting walks and graph homomorphisms via Markov chains and importance sampling." The American Mathematical Monthly 124, no. 7 (2017): 637-641.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.