The following question seems very natural.

It is a well known consequence of Hall's Theorem that every regular bipartite graph has a perfect matching. Another classical result states that the threshold for a random balanced bipartite graph on $2n$ vertices, in which we keep each vertex with probability $p$, to contain a perfect matching is $p=\frac{ln(n)}{n}$.

The question is, what happens in the intersection of these two cases?

Let $H$ be some $k$-regular balanced bipartite graph on $2n$ vertices, and let $G$ be a random subgraph of $H$ in which we keep each edge with probability $p$, independently of the other edges.

What is the threshold for $G$ to contain a perfect matching? It seems natural to conjecture that when $G$ has no isolated vertices, then with high probability $G$ contains a perfect matching. This happens at $p=\frac{\ln(n)}{k}$.

What I've tried so far is to generalize the proof that the threshold for containing a perfect matching in a random bipartite graph is $p=\frac{\ln(n)}{n}$, which is given here:


The idea is to show that with high probability, the resulting random graph satisfies Hall's condition. The proof relies heavily on the fact that for every set $A$ in the left side and $B$ in the right part, the number of edges between $A$ and $B$ is $|A||B|$. If we knew that our regular graph $H$ satisfied some sort of expander mixing lemma - that is, the number of edges between $A$ and $B$ is always approximately $|A||B|k/n$ - then the proof goes through. However, for a general regular graph $H$ I am still stumped.

  • 2
    $\begingroup$ Nice question. I don't know of its being solved, and it doesn't seem easy. But I guess that the place to start is to use the Kuehn-Osthus decomposition (or something closely related) of regular graphs into expanding pieces; the sets for Hall's condition that cause you problems (meaning: they are very likely to fail Hall's condition in the random subgraph, as compared to a generic set of the same size) should be close to unions of expanding pieces, there are few such and this might (with luck and probably a fair bit of work) let you push a union bound through. $\endgroup$
    – user36212
    Apr 22, 2017 at 21:03
  • $\begingroup$ These threshold results are normally stated as "if $p = ln(n)/n$ then with high probability ...". Here "with high probability" means the probability of certain event tends to 1 as $n$ tends to infinity. I am wondering how $k$ grows as $n$ goes to infinity in your problem. Linearly or something else? $\endgroup$
    – Zilin J.
    Apr 25, 2017 at 19:14
  • $\begingroup$ Anything from (a large constant times) log n up to n is interesting here; significantly larger than n/2 is easy (there is enough expansion guaranteed to push the usual complete graph proof through) and most likely standard methods can deal with any linear in n growth. Below this things start to get interesting. $\endgroup$
    – user36212
    Apr 25, 2017 at 19:17
  • $\begingroup$ @user36212 I'm curious: What "standard methods" do you have in mind? Regularity lemma style results? $\endgroup$
    – Micapps
    Apr 26, 2017 at 8:09
  • 2
    $\begingroup$ More simply the Kuehn-Osthus decomposition I mentioned really should work (this is a rather more elementary, very nice, approach than regularity). With regularity, you can very quickly check that the only potential problem sets have to be very close to unions of clusters (and these have to be a collection of clusters that don't expand in the reduced graph) and I guess from here it is not too hard to argue that in fact there are no problem sets. I didn't try to check this argument properly though. But I tend to feel that regularity for this problem is a big overkill, $\endgroup$
    – user36212
    Apr 26, 2017 at 19:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.