Counting the number of biregular bipartite graph What is the number of biregular bipartite graphs on $m+n$ vertices and biregular with degree $s$ and $t$ (obviously $ms=nt$). 
I do understand it’s a very difficult problem and right asymptotics may not be known. But, I just want the order as $m,n \rightarrow \infty$?
 A: We can imagine constructing a bipartite multigraph with the required vertex degrees as follows:


*

*Put $ms$ half-edges out of the $m$ vertices with degree $s$.

*Put $nt$ half-edges out of the $n$ vertices with degree $t$.

*Match them together in one of $(ms)! = (nt)!$ ways.


This generally overcounts by a factor of $(s!)^m (t!)^n$, because "the third half-edge out of $v$ connects to the fifth half-edge out of $w$" is the same as "the first half-edge out of $v$ connects to the first half-edge out of $w$".
That's not quite precise in cases where two half-edges out of $v$ are joined to two half-edges out of $w$. We should estimate, and get rid of, such cases anyway, because we want a graph, not a multigraph.

In a random matching, the probability that all half-edges out of a degree-$s$ vertex go to different vertices is
$$\frac{nt (n-1)t (n-2)t \dotsm (n-s+1)t}{nt (nt-1)(nt-2) \dotsm (nt-s+1)}$$
which is where we start caring about how big $s,t$ are compared to $m,n$.
Very roughly speaking, the denominator is approximately $(nt)^s$, so the $t$'s cancel and the product is roughly $1 - \frac{s^2}{2n}$. If probabilities are approximately independent for different vertices, then the overall probability is $(1 - \frac{s^2}{2n})^m = (1 - \frac{s^2}{2n})^{nt/s} \approx e^{-s^2/2n \cdot nt/s} = e^{-st/2}$.
This gives us the first guess about the number of biregular graphs:
$$
    e^{-st/2} \cdot \frac{(ms)!}{(s!)^m (t!)^n}.
$$
The assumption of independence is going to be close to correct when $s,t$ are very small compared to $m,n$. It's definitely asymptotically true when they're constant. By the birthday paradox, two vertices are unlikely to share any neighbors when $s^2 \ll n$, which gets us asymptotic pairwise independence; I think that's the point at which we can get some factor depending on $s,t$ alone in the front (if we use Chebyshev's inequality instead of the naive product $p^m$). People who study random regular graphs think a lot about what we can do here, but I'm a bit out of my depth.
Aside from that, rounding the denominator to $(nt)^s$ loses us some precision. Assuming $s \le t$, the denominator isn't going to get smaller than $((n-1)t)^s$, but this gives us a $1-\frac sn$ factor, or so, in the probability. So even if the assumption of independence doesn't come back to bite us, the exponential factor should really be $e^{-st/2 + O(s+t)}$. 
