Probability of finding a cycle Let $n,k\in \mathbb{N}$ where $n\geq k\geq 4$ and they are even. Let's create a $K_{n,n}$ bipartite graph with $n$ random edges chosen uniformly. Take random $k$ edges $e_1, e_2, \dots, e_k$ from $K_{n,n}$.
What is the propability that $e_1, e_2, \dots, e_k$ form a $C_k$ cycle?
It's clear that in a $K_{n,n}$ there are at most ${n \choose k/2}^2$ cycles of length $k$. So I think I should find first the probability of having $C_k$ in $K_{n,n}$, because it doesn't necessarily exist.
 A: In a graph with $n$ edges and $x$ cycles of length $k$, the probability that $k$ randomly chosen edges will form a cycle is $x/\binom nk$.
In a random $n$-edge subgraph of $K_{n,n}$, the number of $k$-cycles is itself a random variable $\mathbf X$, so by the law of total probability, the probability that $k$ randomly chosen edges will form a cycle is $\mathbb E[\mathbf X]/\binom nk$.
We can compute $\mathbb E[\mathbf X]$ by linearity of expectation. First, we should find the number of $k$-cycles in $K_{n,n}$, which is I believe $\frac1k (\frac{n!}{(n-k/2)!})^2$ for even $k$. For each $k$-cycle, the probability that it appears in the random $n$-edge subgraph is $\binom{n^2-k}{n-k}/\binom{n^2}{n}$.
Multiply these together, and we have a somewhat terrifying expression for the probability you want.
A: I will follow the standard notation where $K_{n, n}$ denotes the complete bipartite graph on $n$ left and $n$ right vertices, rather than what you defined in the question. What you are asking is to fix $n$ and $k$, choose a subset of $n$ edges randomly, then choose a subset of $k$ of those randomly, and you ask, what is the probability they form a cycle?
The step of choosing $n$ edges is unnecessary as this is equivalent to choosing a subset of $k$ edges from $K_{n, n}$ direclty. If you do this, then what you are asking for is
$$
\frac{\# \text{ of $k$-cycles in } K_{n, n}}{\binom{n^2}{k}}, \tag{1}
$$
where the denominator is the number of ways of choosing $k$ edges out of the $n^2$ total edges.
So it remains to calculate the number of $k$-cycles in $K_{n, n}$ (for $k$ even). There are $2n$ ways to choose the first vertex, $n$ ways to choose the second, $n - 1$ to choose each of the third and fourth, $n - 2$ to choose each of the fifth and second, and so on. This gives $2n \cdot n \cdot \left(\frac{(n-1)!}{(n-(k/2))!}\right)^2$, but this overcounts: we count each cycle $k \cdot 2$ times, since for each cycle there are $k$ possible vertices to start from and $2$ directions to go around the cycle. Therefore dividing, we end up with the number of $k$-cycles in $K_{n, n}$ as
$$
\frac{n!^2}{k (n - (k/2))!^2},
$$
agreeing with Misha Lavrov's calculation for this number. Plugging in to (1), our answer is
$$
\frac{(n^2 - k)! \; n!^2 \; (k-1)!}{n^2 ! \; (n - (k/2))!^2}.
$$
