I think it can be done by standard but very tedious calculations, at least if you do it by brute force (if anyone knows a more clever approach, I'd be happy to hear about it). It's of course possible I messed things up somewhere. I don't know if that counts a simple.

Let $m = n^{d}$, $m' = n^{d'}$, $|B| = cn$. We want to show that: $$ \mathbb{P}(|B \cap R| \leq m') \to 0 $$

First we do the union bound: $$ \mathbb{P}(|B \cap R| \leq m') = \sum\limits_{k=0}^{m'} \mathbb{P}(|B \cap R| = k) $$ so it's enough to show that each term in the sum goes to $0$ faster than polynomially.

Fix $k$ between $0$ and $m'$. To get a random $R$, we first choose exactly $k$ elements from $B$ and then the remaining $|R|-k = m-k$ elements from the complement of $B$, which has size $(1-c)n$. So: $$ \mathbb{P}(|B \cap R| = k) = \frac{1}{\binom{n}{m}}\binom{cn}{k}\binom{(1-c)n}{m-k} $$

Now you have to use Stirling approximation for each term and carefully collect exponents together. I did the calculation and it seemed to work, but I'll spare you the details unless you insist. A possibly easier way to proceed (I haven't checked it very carefully though) is to use the asymptotic formula: $$ \log \binom{n}{k} \approx nH\left(\frac{k}{n}\right) $$ where $H$ is the binary entropy (valid for $n,k \gg 1$)

Taking the log of our probability gives: $$ -\log \binom{n}{m} + \log\binom{cn}{k} + \log \binom{(1-c)n}{m-k} \approx -nH\left(\frac{m}{n}\right) + cnH\left(\frac{k}{cn}\right) + (1-c)n H\left(\frac{m-k}{(1-c)n}\right) $$

So if for large $n$ we have: $$ -H\left(\frac{m}{n}\right) + cH\left(\frac{k}{cn}\right) + (1-c) H\left(\frac{m-k}{(1-c)n}\right) < 0 $$ then our probability will go to $0$ superpolynomially quickly and we are done.

For $k \ll m$ it should be provable by checking that it holds at $k=0$, $k=m'$ and calculating the derivative - then by monotonicity we have our bound everywhere. Rough calculations show this should hold, but you need to check it yourself.

I think it can be done by standard but very tedious calculations, at least if you do it by brute force (if anyone knows a more clever approach, I'd be happy to hear about it). I don't know if that counts as simple. It's of course possible I messed things up somewhere.

Let $m = n^{d}$, $m' = n^{d'}$, $|B| = cn$. We want to show that: $$ \mathbb{P}(|B \cap R| \leq m') \to 0 $$

First we do the union bound: $$ \mathbb{P}(|B \cap R| \leq m') = \sum\limits_{k=0}^{m'} \mathbb{P}(|B \cap R| = k) $$ so it's enough to show that each term in the sum goes to $0$ faster than polynomially.

Fix $k$ between $0$ and $m'$. To get a random $R$, we first choose exactly $k$ elements from $B$ and then the remaining $|R|-k = m-k$ elements from the complement of $B$, which has size $(1-c)n$. So: $$ \mathbb{P}(|B \cap R| = k) = \frac{1}{\binom{n}{m}}\binom{cn}{k}\binom{(1-c)n}{m-k} $$

Now you have to use Stirling approximation for each term and carefully collect exponents together. I did the calculation and it seemed to work, but I'll spare you the details unless you insist. A possibly easier way to proceed (I haven't checked it very carefully though) is to use the asymptotic formula: $$ \log \binom{n}{k} \approx nH\left(\frac{k}{n}\right) $$ where $H$ is the binary entropy (valid for $n,k \gg 1$)

Taking the log of our probability gives: $$ -\log \binom{n}{m} + \log\binom{cn}{k} + \log \binom{(1-c)n}{m-k} \approx -nH\left(\frac{m}{n}\right) + cnH\left(\frac{k}{cn}\right) + (1-c)n H\left(\frac{m-k}{(1-c)n}\right) $$

So if for large $n$ we have: $$ -H\left(\frac{m}{n}\right) + cH\left(\frac{k}{cn}\right) + (1-c) H\left(\frac{m-k}{(1-c)n}\right) < 0 $$ then our probability will go to $0$ superpolynomially quickly and we are done.

For $k \ll m$ it should be provable by checking that it holds at $k=0$, $k=m'$ and calculating the derivative - then by monotonicity we have our bound everywhere. Rough calculations show this should hold, but you need to check it yourself.

I think it can be done by standard but very tedious calculations, at least if you do it by brute force (if anyone knows a more clever approach, I'd be happy to hear about it). It's of course possible I messed things up somewhere. I don't know if that counts a simple.

Let $m = n^{d}$, $m' = n^{d'}$, $|B| = cn$. We want to show that: $$ \mathbb{P}(|B \cap R| \leq m') \to 0 $$

First we do the union bound: $$ \mathbb{P}(|B \cap R| \leq m') = \sum\limits_{k=0}^{m'} \mathbb{P}(|B \cap R| = k) $$ so it's enough to show that each term in the sum goes to $0$ faster than polynomially.

Fix $k$ between $0$ and $m'$. To get a random $R$, we first choose exactly $k$ elements from $B$ and then the remaining $|R|-k = m-k$ elements from the complement of $B$, which has size $(1-c)n$. So: $$ \mathbb{P}(|B \cap R| = k) = \frac{1}{\binom{n}{m}}\binom{cn}{k}\binom{(1-c)n}{m-k} $$

Now you have to use Stirling approximation for each term and carefully collect exponents together. I did the calculation and it seemed to work, but I'll spare you the details unless you insist. A possibly easier way to proceed (I haven't checked it very carefully though) is to use the asymptotic formula: $$ \log \binom{n}{k} \approx nH\left(\frac{k}{n}\right) $$ where $H$ is the binary entropy (valid for $n,k \gg 1$)

Taking the log of our probability gives: $$ -\log \binom{n}{m} + \log\binom{cn}{k} + \log \binom{(1-c)n}{m-k} \approx -nH\left(\frac{m}{n}\right) + cnH\left(\frac{k}{cn}\right) + (1-c)n H\left(\frac{m-k}{(1-c)n}\right) $$

So if for large $n$ we have: $$ -H\left(\frac{m}{n}\right) + cH\left(\frac{k}{cn}\right) + (1-c) H\left(\frac{m-k}{(1-c)n}\right) > 0 $$ then our probability will go to $0$ superpolynomially quickly and we are done.

For $k \ll m$ it should be provable by checking that it holds at $k=0$, $k=m'$ and calculating the derivative - then by monotonicity we have our bound everywhere. Rough calculations show this should hold, but you need to check it yourself.

I think it can be done by standard but very tedious calculations, at least if you do it by brute force (if anyone knows a more clever approach, I'd be happy to hear about it). It's of course possible I messed things up somewhere. I don't know if that counts a simple.

Let $m = n^{d}$, $m' = n^{d'}$, $|B| = cn$. We want to show that: $$ \mathbb{P}(|B \cap R| \leq m') \to 0 $$

First we do the union bound: $$ \mathbb{P}(|B \cap R| \leq m') = \sum\limits_{k=0}^{m'} \mathbb{P}(|B \cap R| = k) $$ so it's enough to show that each term in the sum goes to $0$ faster than polynomially.

Fix $k$ between $0$ and $m'$. To get a random $R$, we first choose exactly $k$ elements from $B$ and then the remaining $|R|-k = m-k$ elements from the complement of $B$, which has size $(1-c)n$. So: $$ \mathbb{P}(|B \cap R| = k) = \frac{1}{\binom{n}{m}}\binom{cn}{k}\binom{(1-c)n}{m-k} $$

Now you have to use Stirling approximation for each term and carefully collect exponents together. I did the calculation and it seemed to work, but I'll spare you the details unless you insist. A possibly easier way to proceed (I haven't checked it very carefully though) is to use the asymptotic formula: $$ \log \binom{n}{k} \approx nH\left(\frac{k}{n}\right) $$ where $H$ is the binary entropy (valid for $n,k \gg 1$)

Taking the log of our probability gives: $$ -\log \binom{n}{m} + \log\binom{cn}{k} + \log \binom{(1-c)n}{m-k} \approx -nH\left(\frac{m}{n}\right) + cnH\left(\frac{k}{cn}\right) + (1-c)n H\left(\frac{m-k}{(1-c)n}\right) $$

So if for large $n$ we have: $$ -H\left(\frac{m}{n}\right) + cH\left(\frac{k}{cn}\right) + (1-c) H\left(\frac{m-k}{(1-c)n}\right) < 0 $$ then our probability will go to $0$ superpolynomially quickly and we are done.

For $k \ll m$ it should be provable by checking that it holds at $k=0$, $k=m'$ and calculating the derivative - then by monotonicity we have our bound everywhere. Rough calculations show this should hold, but you need to check it yourself.