3
$\begingroup$

Let $G=(n,p)$ with $p \ll n^{-1+\epsilon}$ for all $\epsilon >0$. Then for each $k\in \mathbb{N}$ there are a.a.s no $k$ vertices with at least $k+1$ edges.

Proof: We want to show $$\Pr(\exists S\subseteq V: |S|=k, |E_S|\geq k+1) \to 0\quad (n\to \infty).$$

Let $S\subseteq V$ with $|S|=k$. Then there are ${k}\choose{2}$$=\frac{k(k-1)}{2}$ possible subsets with 2 elements. Lets call them $A_i$, Define the random varibles $1_{A_i}$ such that $$1_{A_i}=1 \text{ when } A_i \subset{E_S},\quad 0 \text{ else}$$

We have $$\Pr(|S|=k, |E_S|\geq k+1)=\Pr(\sum_i 1_{A_i} \geq k+1)\leq \frac{E\sum_i 1_{A_i}}{k+1}$$

Then $E\sum_i 1_{A_i}=\frac{k(k-1)}{2}\Pr(1_{A_i}=1)=\frac{k(k-1)}{2}p$ since the probability of the edges is independent.

Now we have $$\Pr(|S|=k, |E_S|\geq k+1)=\Pr(\sum_i 1_{A_i} \geq k+1)\leq \frac{E\sum_i 1_{A_i}}{k-1}<\frac{k}{2}p \ll \frac{k}{2} \frac{1}{nn^{-\epsilon}}$$

Now pick: $n^{\epsilon}=k$. is this correct? does the result follow?

$\endgroup$
  • 1
    $\begingroup$ all I read was "pick $n^\epsilon = k$". this confuses me. what exactly are you picking? I don't think you are allowed to pick anything. $\epsilon$ and $k$ are given, and you want to show a result for arbitrarily large $n$. $\endgroup$ – mathworker21 Dec 5 '18 at 16:18
  • $\begingroup$ but it holds for all $\epsilon>0$. So we can pick epsilon so that $n^{\epsilon}=k$ since $n$ can be very large and $\epsilon$ small enough. $\endgroup$ – orange Dec 5 '18 at 16:20
  • $\begingroup$ You can't pick $\varepsilon.$ It is given to you. $\endgroup$ – zoidberg Dec 5 '18 at 19:50
  • $\begingroup$ so what do i do at the end? $\endgroup$ – orange Dec 5 '18 at 19:57
2
$\begingroup$

The approach you have taken is not strong enough to get the desired conclusion.

The use of $1_{A_i}$ is a bit strange, but everything you've done can be phrased in terms of the random variable $|E_S|$ (for a fixed $S$). You are applying Markov's inequality to $|E_S|$, saying that $$ \Pr[|E_S| \ge k+1] \le \frac{\mathbb E[|E_S|]}{k+1}. $$ By linearity of expectation, $\mathbb E[|E_S|] = \binom k2 p$. It is not quite correct that $\binom k2 = \frac{k(k+1)}{2}$; rather, $\binom k2 = \frac{k(k-1)}{2}$. But this is not important, since we still have $\frac{\binom k2 p}{k+1} < \frac {kp}{2} \ll \frac{k}{n^{1-\epsilon}}$.

Here, $k = |S| \le n$, and this inequality is potentially strong enough to prove that for any given $S$, we have $|E_S| \le |S|$ with high probability. But that's not what we want: we want a result that holds for all $S$.

Consider $k=4$, for example: then there are $\binom n4$ sets $S$ we could consider, and if the probability is $\ll \frac{4}{n^{1-\epsilon}}$ for each one, that only tells us that the expected number of sets $S$ with $5$ edges is $\ll \binom n4 \frac{4}{n^{1-\epsilon}}$ or in other words it is $\ll n^{3+\epsilon}$, which still could be very large.


We can improve on Markov's inequality for bounding the probability that a set $S$ induces a subgraph we don't like.

First of all: for any $k$, there is only a constant number of $k$-vertex graphs with $k+1$ edges. So if we show that for a fixed graph $H$ (on $k$ vertices and with $k+1$ edges) the random graph doesn't have an $H$-subgraph a.a.s., then we immediately conclude that the random graph doesn't have any such subgraphs with $k$ vertices and $k+1$ edges a.a.s. (Since the subgraphs are not necessarily induced, this also rules out subgraphs with $k$ vertices and more than $k+1$ edges.)

As an upper bound, the expected number of labeled $H$-subgraphs in $\mathcal G_{n,p}$ is less than $n^{|V(H)|}p^{|E(H)|}$. (The power of $n$ is actually at most $n(n-1)(n-2)\dotsb$ with $|V(H)|$ factors.) If $H$ has $k$ vertices and $k+1$ edges, this is $n^k p^{k+1}$.

We have $p \ll n^{-1+\epsilon}$ for all $\epsilon>0$, so in particular, $p \ll n^{-1 + \frac{1}{k+1}}$. Therefore $p^{k+1} \ll n^{-k}$, and $n^k p^{k+1} \to 0$ as $n \to \infty$. Therefore $\mathcal G_{n,p}$ has no copies of $H$ a.a.s., and by doing this for every $k$-vertex graph with $k+1$ edges we get the statement you want.


A subtle point here is that we are proving the statement "for each $k$, a.a.s., $\mathcal G_{n,p}$ contains no $k$-vertex subgraph with at least $k+1$ edges" not "a.a.s., $\mathcal G_{n,p}$ contains no $k$-vertex subgraph with at least $k+1$ edges for each $k$". That is, $k$ is a constant fixed outside the limit as $n \to \infty$.

If we didn't do this, then the statement would not be true, because $\mathcal G_{n,p}$ for $p \gg \frac1n$ does contain large subgraphs with more edges than vertices (in particular, the whole graph is such a subgraph).

$\endgroup$
  • 1
    $\begingroup$ Wait a second though. If $p=n^{-1+\epsilon}$ then a graph drawn according to $G(n,p)$ will have ${n \choose 2}p \approx n^{1+\epsilon} >> n$ edges. Then there would indeed be a $k$-vertex subgraph with more than $k+1$ edges, for some $k$. $\endgroup$ – Mike Dec 6 '18 at 18:40
  • 1
    $\begingroup$ @Mike See my reply to your answer :) $\endgroup$ – Misha Lavrov Dec 6 '18 at 18:41
  • 1
    $\begingroup$ Gotcha @MishaLavrov looking at it now :) $\endgroup$ – Mike Dec 6 '18 at 18:41
  • 1
    $\begingroup$ @MishaLavrov I see it now, if $k$ is fixed and $\epsilon < 1/k$ then $k^2{n \choose k}n^{(k+1)(-1+\epsilon)}$ goes to 0 as $n$ goes to infinity. Thanks I will delete my answer $\endgroup$ – Mike Dec 6 '18 at 18:48
  • 2
    $\begingroup$ @Mike I've edited my answer to address this point, because reading the question is tricky and this fine detail of wording matters. (If you look at the edit history of my answer, its first draft originally made the same mistake!) $\endgroup$ – Misha Lavrov Dec 6 '18 at 18:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.