Let $G$ be a graph with $n$ vertices where each edge is chosen with probability $\frac{1}{2}$:
- $G$ is separated, if we can divide the vertices of the graph into two equal-sized sets where there are no edges between them.
- $G$ is almost-separated, if we can divide the vertices of the graph into two equal-sized sets where there are less than $10n$ edges between them.
1)What is the probability of G to be separated?
2)What is the probability of G to be almost-separated?
So far I have tried to calculate $\sum_{i=0}^n A_i$, Where $A_i$ is the probability of the cut $i$ to separate the graph. The problem is that $A_i$'s are dependent.
UPDATE: I thought about the problems as for each cut we have $\frac{{n}^{2}}{4}$ edges and we do not want anyone of them. It's is the same as having a random variable $X\sim Bin(\frac{{n}^{2}}{4})$.
1) So for the first part what we are calculating is:$P(X=0)$ $$P(X=0)=\binom{\frac{{n}^{2}}{4}}{0}*{(\frac{1}{2}})^{0} *{(\frac{1}{2}})^{\frac{{n}^{2}}{4}}={(\frac{1}{2}})^{\frac{{n}^{2}}{4}}$$
2)In the second part, we are calculating: $P(X\leq10n)$ .Which I could not calculate.
Solving this exactly seems hard. You could approximate it by the expected number of cuts,
$$ \frac12\binom n{\frac n2}2^{-\left(\frac n2\right)^2}\;. $$
Since the probability for more than one cut decreases very rapidly with $n$, this is a good approximation alread for moderate $n$. If you want, you can calculate successive corrections with (increasingly complicated) inclusion–exclusion terms. For two cuts, we can divide the vertices into four sets $A\cap B$, $A\cap\overline B$, $\overline A\cap B$ and $\overline A\cap\overline B$ of sizes $k$, $\frac n2-k$, $\frac n2-k$ and $k$, respectively, with a total of
$$ k^2+\left(\frac n2-k\right)^2+4k\left(\frac n2-k\right)=\left(\frac n2\right)^2+kn-2k^2 $$
edges that must not exist, for a contribution of
$$ -\frac14\sum_{k=1}^{\left\lfloor\frac n4\right\rfloor}\frac{n!}{k!^2\left(\frac n2-k\right)!^2}2^{-\left(\frac n2\right)^2-kn+2k^2} $$
(where a symmetry correction is required if $n$ is a multiple of $4$). For $n=6$ this is $-\frac{45}{8192}\approx-0.0055$, compared to the main term $\frac5{256}\approx0.02$, and for $n=10$ it’s $-\frac{7875}{34359738368}\approx-2.3\cdot10^{-7}$, compared to the main term $\frac{63}{16777216}\approx3.8\cdot10^{-6}$.