How many independent even cycles in $G(n,m)$

Question

In the random graph model $G(n,m)$, how many independent even cycles are there ?

More precisely, let $C$ be a random variable which counts the independent even cycles. What is $$P(C=c)$$ for $c=0,1,\ldots$ ?

For my purposes, it would be enough to calculate $$ \mathbb{E}(2^C) := \sum_{c=0}^\infty 2^c \cdot P(C=c) = \sum_{c=0}^{m/4} 2^c \cdot P(C=c) $$

Answer 1

This probably varies a lot depending on which kind of $m$ you're looking at.

Here's a partial answer. For any $n$-vertex, $m$-edge, $2$-connected graph $G$ with odd cycles, $C=m-n$. We also have:

Theorem 4.3, Frieze and Karonski's Random Graphs.

Let $m = \frac12 n(\log n + \log \log n + c_n)$. Then $$\lim_{n \to \infty} \Pr[G(n,m) \text{ is $2$-connected}] = \begin{cases}0 & \text{if } c_n \to -\infty \\ e^{-e^{-c}} & \text{if }c_n \to c \\ 1 & \text{if }c_n \to \infty.\end{cases}$$

This tells us when $G(n,m)$ is $2$-connected with high probability; odd cycles appear much earlier, and therefore $2^C = 2^{m-n}$ with high probability; since $C \le m-n-1$ always, this means $\mathbb E[2^C] \sim 2^{m-n}$ for such $m$.

For smaller $m$, we need to think about the number of blocks (maximal $2$-connected subgraphs) in $G(n,m)$, and about which of those blocks have odd cycles. I don't have a complete answer here, but we can observe that:

• In the subcritical regime, all components are simple: they contain at most one cycle. I expect that this cycle is even or odd with roughly equal probability.
• Once the giant component emerges (skipping over the critical window where it's hard to say anything), all other components are still simple.
• Eventually, all non-giant components are trees, and we can ignore them (except for needing to know how many there are).

The result about $2$-connected graphs also applies when the $2$-core of $G$ is $2$-connected, since we can delete vertices of degree $1$ without changing $m-n$ or anything about the cycle space. I expect that this is eventually true of the giant component, which simplifies the analysis.

---

The claim that $C \ge m-n$ when $G$ is $2$-connected might be well-known, but it's new to me, so I will prove it.

In this case, the cycle space is generated by $m-(n-1)$ cycles. To show that the even cycle space is generated by $m-n$ even cycles, it's enough to show that any odd cycle, together with all the even cycles, generates the cycle space.

Take any two odd cycles. Let $u_1, v_1$ be three vertices on one cycle, and $u_2, v_2$ be three vertices on another. The graph where we add a vertex $x_i$ adjacent to $u_i, v_i$ for $i=1,2$ is also $2$-connected, so there are $2$ disjoint paths from $x_1$ to $x_2$. Deleting $x_1$ and $x_2$ produces, without loss of generality, a path $P$ from $u_1$ to $u_2$ and a path $Q$ from $v_1$ to $v_2$.

If we follow $P$ from $u_1$ to $u_2$, then go from $u_2$ to $v_2$ in the second cycle (in some direction), then follow $Q$ back from $v_2$ to $v_1$, there is always some direction around the first cycle that will give us an even cycle as a result. If we do the same thing, but go from $u_2$ to $v_2$ in the other direction, we get a second even cycle. The sum of these two even cycles modulo $2$ is the same as the sum of the two odd cycles. This means that once we have one odd cycle and all even cycles, we can get all odd cycles.