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?
1
$\begingroup$
$\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 nonrandom 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$
$\endgroup$
See:
Constructing a perfect matching is in random NC
Matching is as easy as matrix inversion, which exploits a probabilistic lemma.