Say that a graph $G=(V,E)$ is a $c$-expander if for every subset $S \subseteq V$ with $|S| \leq |V|/2$, it holds that $|E(S,\bar{S})| \geq c |S|$. Suppose that for any $n$, it is possible to construct in polynomial time (in $n$) a $10$-regular graph $G_n$ that is a $c$-expander for some $c > 0$.
Describe and analyze a polynomial-time reduction $F$ from $\mathsf{3SAT}$ to $\mathsf{3SAT}$-$B$ that is gap preserving:
$\mathrm{gap}(\varphi) = 0 \implies \mathrm{gap}(F(\varphi)) = 0$
$\mathrm{gap}(F(\varphi)) \geq \mathrm{gap}(\varphi)/C$
where $B$ and $C$ are some constants.
Recall that $\mathsf{3SAT}$-$B$ is the $\mathsf{3SAT}$ problem where every variable can occur in at most $B$ clauses, and for a Boolean formula $\varphi$, $\mathrm{gap}(\varphi)$ is defined so that the best truth assignment to $\varphi$ satisfies a $(1-\mathrm{gap}(\varphi))$-fraction of the clauses.
Suppose that $G=(V,E)$ is a $d$-regular graph, let $A$ be the adjacency matrix. Let $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ be be the eigenvalues of $A$.
Prove that $G$ is bipartite if and only if $\lambda_1 = -d$.
Prove that $G$ is connected if and only if $\lambda_{n-1} < d$.
Again consider a $d$-regular graph $G$ with adjacency matrix $A$. Assume that $G$ is connected and not bipartite.
Define the walk matrix $W = \frac{1}{d} A$. Let $\vec{x}=(x_1,x_2,\ldots,x_n)$ be a vector with $x_1,\ldots,x_n \geq 0$ and $x_1+\cdots+x_n=1$. Let $\pi$ be the vector $(1/n,1/n,\ldots,1/n)$.
Show that $W \pi = \pi$.
Show that for any $\vec{x}$ as above: $\lim_{k \to \infty} W^k \vec{x} = \pi$. In other words, the random walk started from any probability distribution converges to the uniform measure on vertices.