Expansion in supercritical random subgraphs of expanders and its consequences (Q6623578)

The paper studies expansion in supercritical random subgraphs of expanders and some of its consequences. Let \(\varepsilon>0\) be a sufficiently small constant and \(G=(V,E)\) be an \((n,d,\lambda)\)-graph with \(\lambda/d\le\varepsilon^4\). \(G_p\) is formed by retaining each edge of \(G\) independently with probability \(p\). Let \(L_1\) be the giant component of \(G_p\). It is shown that with high probability there exists \(L^\prime_1\subseteq L_1\) with \(|L^\prime_1|\ge 11\varepsilon n/6\) such that for every \(S\subseteq L^\prime_1\) with \(|S|\le|L^\prime_1|/2\), \(|N_{L^\prime_1}(S)|\ge c\varepsilon^2|S|/\ln^2(1/\varepsilon)\). Here, \(N_G(S)\) is the external neighborhood of \(S\subseteq V(G)\) in \(G\). Moreover, if \(p=(1+\varepsilon)/d\), then there exists an absolute constant \(C\) such that with high probability the mixing time of the lazy random walk on \(L_1\) is at most \(C\ln^2n/\varepsilon^4\).