1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.