0
$\begingroup$

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$)

  1. 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$.
  2. For a random set $S \subseteq [n]$ however, we have that $d_G(v,S)\geq (1-\delta)|S|$ with high probability.
    1. 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.

$\endgroup$
  • 1
    $\begingroup$ 1. is obviously false, as $d_G(v,X)$ can be zero (e.g. take $X$ an anticlique). Then you should probably try to clarify what means "arbitrary" and "random" formally, as your usage of the terms seems confused. $\endgroup$ – Graffitics May 10 '16 at 16:04
  • $\begingroup$ Thanks for your help. I do not get why this contradicts 1. I know that $d_G(v,X)$ can be zero, but this is no problem, as $|X|-\delta n \leq 0$ is fine. So probably this means that you cannot have an anticlique of size $> (1-\delta)n$, which seems to be fine for me. Then: For arbitrary $X$ means for me: We pick some $X$ and we do not say how we pick it, but we fixed it. For random $S$ means for me that we pick $S$ among all the possible subsets, each with equal probability. Where do you think that it is confusing how I use them? $\endgroup$ – user136457 May 10 '16 at 16:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.