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?
$\begingroup$
$\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 DevlinCommented 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 NoelCommented May 8, 2019 at 21:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
See:
Constructing a perfect matching is in random NC
Matching is as easy as matrix inversion, which exploits a probabilistic lemma.
answered May 9, 2019 at 6:15
$\begingroup$
$\endgroup$
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.
answered May 22, 2019 at 17:09