Let $G=([n],E)$ be a graph having minimum degree $\delta(G) \geq (1-\delta) n$. For some $q=q(n)$, let $G_q=([n], E_q)$ be the random subgraph of $G$ obtained by deleting each edge independently with probability $(1-q)$.
Now I wonder about the following things: (would be great if you could help me finding out whether it is correct)
(Remark: I write $\geq f$ with high probability, when I mean that actually we have that it is $\geq (1 + \epsilon) f$ with high probability for any small $\epsilon$)
- For a fixed set $X \subseteq [n]$ and a fixed vertex $v \in [n]$ we cannot say something concrete about $d_G(v,X):=|\{x \in X \colon \{v,x\} \in E\}|$, all we know is that $d_G(v,X) \geq |X|-\delta n$.
- For a random set $S \subseteq [n]$ however, we have that $d_G(v,S)\geq (1-\delta)|S|$ with high probability.
- and 2. then automatically lead to the fact that $d_{G_q}(v,X)\geq (|X|-\delta n)q$ and $d_{G_q}(v,S) \geq (1-\delta)|S|q$ with high probability. But this doesn't mean that it holds for all sets, only for a fixed but arbitrary $X$ or a random $S$. True?
So are these 3 observations correct? Is there an easy way to argue that they are?
Then, another type of problem:
For $X_1, X_2 \subseteq [n]$, deterministic: We can compute the probability (a lower bound) of having a certain amount of edges in the cut between $X_1$ and $X_2$ (say, for simplicity in the random graph $G(n,r)$, where each edge is present with probability $r$). We cannot conclude that for all such sets it holds, but for these two arbitrary sets it holds. Now, when we choose $S_1, S_2 \subseteq [n]$, at random, then we know that the same probability bound is also true for $S_1$ and $S_2$? To conclude that it holds for all sets $X_1,X_2$, we would need to have a large enough probability such that it can kill the union bound?
Thank you very much for your help! You see, I am struggling with probably very easy questions here.