Question on the proof of the upper bound of girth in dense graph.

Question

I have trouble understanding the proof of the following theorem from Upfal's Probability textbook pg 134

Theorem:

For any integer $k \geq 3$ there is a graph with n nodes, at least $\frac{1}{4}n^{1+\frac{1}{k}}$ edges, and girth at least k.

For which girth is the length of the smallest cycle

Proof:

We sample random graph $G \in G_{n, p}$ with $p = n^{\frac{1}{k} - 1}$ Let $X$ be the number of edges in the graph.

Then

$$E[X] = p {n \choose 2} = \frac{1}{2}(1-\frac{1}{n})n^{\frac{1}{k} + 1} $$

Let $Y$ be the number of cycles in the graph of length at most $k - 1$ . Any specific possible cycle of length $i$, where $ 3\leq i \leq k - 1 $ occurs with probability $p^i$ .

Hence

$$E[Y] = \sum_{i=3}^{k-1} {n \choose i}\frac{(i-1)!}{2} p^i$$

........

Now here is the part I don't understand

If I choose all possible combination of cycles of length $i$, it should be equal to the following

(all possible way of choosing i edges without order) * (modulate by number of edge that is not compatible to form a cycle of length i )

which is equal to

${n \choose i}$ * (modulate by number of edge that is not compatible to form a cycle of length i )

This is because if you have an edge that is more than $i$ step away, you cannot form a cycle of length $i$

I don't see how

(modulate by number of edge that is not compatible to form a cycle of length i ) = $\frac{(i-1)!}{2}$

Can someone help me out?

Thanks

Answer 1

I can't quite follow your thinking with "modulate by number of edge that is not compatible to form a cycle of length $i$". That seems to focus on the ways to not form a cycle but the expression is looking at the ways cycles can be formed.

$\binom{n}{i}$ is obviously the number of ways to select $i$ nodes from $n$ available.

Then, $\frac{(i-1)!}{2}$ is the number of ways to arrange those chosen $i$ nodes into a circle (ignoring the edges). To see this, begin with $i!$ as the number of permutations of $i$ nodes. Then forming a circle, there are $i$ permutations corresponding to each distinct circular arrangement (because you can rotate the circle by a "distance" of one node $i$ times and still have the same circle). So dividing by $i$ gives $(i-1)!$. Then allowing for "reflection" (or reversing the direction) of each circle, you have to divide by $2$ giving $\frac{(i-1)!}{2}$.

Finally, multiply by $p^i$ because that's the probability of all $i$ edges in each circle existing, so to actually form a cycle in the graph.