# Expander mixing lemma

Let $$G$$ be a $$d$$-regular graph. Show the following version of the expander mixing lemma: For every set $$S\subseteq V(G)$$, $\Pr_{uv\in E(G)}\biggl\{ u\in S \land v\in S\biggr\} \le \Pr_{u\in V(G)}\bigl\{u\in S\bigr\} \cdot \biggl(\Pr_{v\in V(G)}\bigl\{v\in S\bigr\} + \lambda (G)\biggr) \,.$

# Lower bound on support by first two moments

Let $$X$$ be real-valued random variable such that $$\E X \ge 0$$. Show the following lower bound on the probability of its support in terms of its first two moments, $\Pr\bigl\{ X > 0\bigr\} \ge (\E X)^2 / \E X^2 \,.$

# Eigenvectors and eigenvalues of hypercube

Let $$G$$ be $$d$$-regular graph with $$V(G)=\bbF_2^d$$ and $E(G)=\biggl\{(x,x+\mathbf{1}_i) \biggm\vert x\in \bbF_2^d, i\in [d]\biggr\} \,,$ where $$\mathbf{1}_i\in \bbF_2^d$$ denotes the vector with $$i$$-th coordinate equal to $$1$$ and all others equal to $$0$$.

1. Show that Fourier basis is an eigenbasis of the adjacency matrix of the graph.
2. Determine $$\lambda(G)$$.
3. Construct the $$G'$$ by adding $$d$$ self-loops to every vertex of $$G$$ (so that $$G'$$ is $$2d$$-regular). Show that $$\lambda(G)\le 1-\Omega(1/d)$$.