I have the following problem.
Show that there is a constant $c=c(p) > 0 $ such that almost all graphs in $\mathcal{G}_{n,p}$ verify the following property : for each subset $X \in V(G)$ with cardinality $|X|\leq n/2$, $$ e(X, V\backslash X) \geq c |X| $$
Where $ e(X, V\backslash X)$ denotes the number of edges connecting $X$ and $V\backslash X$.
I found a "standard" solution, using combinatorial arguments (the constant $c(p)=p$ satisfies the condition), but I have the feeling that a "more elegant" proof should exist.
My intuition is as follow : the problem is equivalent to proving, with $i(G)$ the isoperimetric constant : $$ \forall p, \ \exists c(p)>0, \ s.t. \ \mathbb{P}[ i(G) > c] \rightarrow 1 \text{ when }n\rightarrow \infty $$
And for any graph $G$, we know a lower bound for $i(G)$: $$ \mu_2 /2 \leq i(G)$$ With $\mu_2$ being the second smallest eigenvalue of the Laplacian matrix of $G$. Now if I can find some bound for $\mu_2$ I should be able to do something.
I know that for fixed $p$ the probability that $G$ is connected tends to 1, hence $\mu_2 > 0$. But can we find similar argument for $\mu_2 > c$ for some constant $c$ ? in term of connectivity surely? Thanks for the help!
From this paper we can estimate the normalized Laplacian spectrum of $\mathcal G_{n,p}$ from the spectrum of an "average-case Laplacian" $$\bar{L} = I - \bar{D}^{-1/2} \bar{A}\bar{D}^{-1/2}$$ where $\bar{D} = (n-1)pI$ is the expected value of $D$, and $\bar{A} = p(J-I)$ is the expected value of $A$. (As usual, $J$ is the all-ones matrix.) Since $\bar{D}$ commutes with everything, we can rewrite this as $I - \bar{D}^{-1}\bar{A}$ which simplifies to$$\frac{n}{n-1}I - \frac{1}{n-1}J.$$ The eigenvalues of $J$ are $n,0,0,\dots,0,0$ and so the eigenvalues of $\bar{L}$ are $0, \frac{n}{n-1}, \frac{n}{n-1}, \dots, \frac{n}{n-1}$.
This looks like a rather stupid estimate that doesn't depend on $p$, but the dependence on $p$ is hidden in the error bound. For all constant $\epsilon>0$, we have $$|\lambda_i(L) - \lambda_i(\bar{L})| \le \mathcal O\left(\sqrt{\frac{\log(n/\epsilon)}{(n-1)p}}\right)$$ provided $(n-1)p > k(\epsilon)\log n$. In other words, as long as $p$ is not a too-small function of $n$, we have $\lambda_2(L) \ge 1 - o(1)$ with high probability.
I guess Theorem 4 in the paper provides a slightly-tighter answer more easily, but then this answer would have been too short. (Also I didn't find Theorem 4 until I wrote all of the above.)