Random graph contains no $C_4$ a.a.s.

Question

Let $\epsilon>0$ as well as $n \in \mathbf{N}$ and $p=n^{-(1+\epsilon)}$. I want to show that a random graph in $G(n,p)$ a.a.s. does not contain a $C_4$ (I hope this is true?). My attempt was the following. Let $a,b,c,d$ be $4$ vertices and define $$X_{a,b,c,d}:=\begin{cases} 1, a,b,c,d \text{ form a cycle }\\ 0, \text{else}. \end{cases}$$ Then we have that $X:=\sum_{a,b,c,d} X_{a,b,c,d}$ satisfies: $$P(G \ \text{contains} \ C_4)=P(X \geq 1) \leq \sum_{a,b,c,d} P(X_{a,b,c,d}=1)=\binom{n}{4}p^4 \leq n^4 (n^{-4-4\epsilon})=n^{-4\epsilon} \to 0.$$

Are my calculations correct? I am really bad at probability theory, hence I fear that my probability might not be correct, but I am not sure. Thanks in advance for any comment!

Answer 1

The result $\binom n4 p^4$ is not quite right - but it is right up to a constant factor, so you still get the same idea.

There are two ways to correct it.

1. If you keep the definition of $X_{a,b,c,d}$ then the probability that $X_{a,b,c,d}=1$ is not $p^4$. That's because we can form three different (overlapping) cycles with the vertices $a,b,c,d$. The overall probability is $$\Pr[X_{a,b,c,d}=1] = 3p^4(1-p)^2 + 4 p^5(1-p) + p^6.$$ Out of the graphs with vertex set $\{a,b,c,d\}$, there are $3$ graphs with $4$ edges, $4$ graphs with $5$ edges, and $1$ graph with $6$ edges that contain a cycle. This can simplify to $3p^4 -2 p^5$.
2. We can also keep the probability as $p^4$ but change the random variables we consider. Let $\mathcal C$ be the set of all $4$-cycles found in $K_n$; for each $C \in \mathcal C$, let $X_C=1$ if $C$ is also present in $G(n,p)$. In this case, $\Pr[X_C=1] = p^4$ exactly: we need all four edges of $C$ to be present. However, $|\mathcal C|$ is not $\binom n4$ but $3 \binom n4$: once we choose the vertices of a $4$-cycle, there are $3$ ways to form the cycle.

The second method gives us $3\binom n4 p^4$ for the expected value; the first gives us $3 \binom n4 p^4 - 2 \binom n4 p^5$, which is the same up to a lower-order term. (The difference is because they are counting slightly different things, though either one being $0$ is still enough to conclude that $G(n,p)$ has no $4$-cycles.) When $p = n^{-1-\epsilon}$, both of these still go to $0$ as $n \to \infty$.

Answer 2

It seems we are using the intermediate step $P(X_{a,b,c,d}=1) = p^4$, this is because there are four edges that need to belong to the graph.

After this the number of summands is in fact something less than $n^4$ but I don't think that it is $\binom{n}{4}$ exactly, in any case I think the proof is mostly correct.

Finally you probably should mention that if $X$ is $0$ then the graph has no $C_4$.