1
$\begingroup$

In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references to such examples?

$\endgroup$
  • 2
    $\begingroup$ There are lots of things you could mean, but perhaps look up “Rodl nibble” to get an idea of some of the more fancy stuff (and of course Keevash’s existence of designs for particularly fancy stuff). Less fancy stuff definitely exists, but at some point it becomes glorified counting. $\endgroup$ – Pat Devlin May 8 at 17:37
  • 2
    $\begingroup$ Also note that, if you want to find large matchings in a specific graph, or specific family of graphs, then you will probably be better off to apply one of the many non-random algorithms that exist, such as the Hungarian Algorithm (if your graph is bipartite) or Edmonds' Blossom Algorithm. $\endgroup$ – Jon Noel May 8 at 21:41
1
$\begingroup$

See:

Constructing a perfect matching is in random NC

Matching is as easy as matrix inversion, which exploits a probabilistic lemma.

$\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.