Vrftsjtryk

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

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

Let $Ssubseteq 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{Esum_i 1_{A_i}}{k+1}$$

Then $Esum_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{Esum_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?

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