Is a uniformly random $r$-regular bipartite graph $r$-edge connected with high probability?

Question

A graph is $r$-edge connected if the number of edges in a minimum cut is at least $r$.

It is known that a random $r$-regular graph is $r$- vertex connected (which implies $r$-edge connected) with high probability as the number of vertices grows. See Introduction To Random Graphs, Frieze & Karonski, pg. 214 for a proof.

Can the same be said for a uniformly random $r$-regular bipartite graph?

Answer 1

This, and your other related question, should be provable in more or less the same way as the theorem for random regular graphs.

The configuration model for random bipartite graphs is actually slightly simpler. In the case of random $r$-regular bipartite graphs on $2n$ vertices:

1. Take $2nr$ points partitioned into $2n$ cells $A_1 \cup \dots \cup A_n \cup B_1 \cup \dots \cup B_n$, each of size $r$.
2. Pick a uniformly random bijection $f : A_1 \cup \dots \cup A_n \to B_1 \cup \dots \cup B_n$.
3. Define a graph with vertices $a_1, \dots, a_n, b_1, \dots, b_n$; for each time $f(x) = y$ with $x \in A_i$ and $y \in B_j$, add an edge $a_i b_j$ to the graph.

This is not guaranteed to be a simple graph: we might have parallel edges. However, with positive probability (for constant $r$) it is a simple graph; conditioned on being simple, any $r$-regular bipartite graph on $2n$ vertices is equally likely to be the result.

I expect that the proof of Theorem 11.9 in Frieze and Karonski's textbook continues to work in this case, we just have to switch some binomial coefficients around slightly.