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
  • 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, 2019 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, 2019 at 21:41

2 Answers 2

1
$\begingroup$

See:

Constructing a perfect matching is in random NC

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

$\endgroup$
1
$\begingroup$

See Goel, A., Kapralov, M. and Khanna, S., 2013. Perfect Matchings in O(n\logn) Time in Regular Bipartite Graphs. SIAM Journal on Computing, 42(3), pp.1392-1404 and the references therein.

https://epubs.siam.org/doi/abs/10.1137/100812513?casa_token=UzJV63MtWu8AAAAA:NfcKyqZRgXBHnVbyDhhBz9-OBS_jJRgGykm1IYUL4VBd7fgJDficq3HpqwUlK_mHZzK2ubGCuiU

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.