randommatching
Randommatching is a concept in combinatorics and computer science referring to a matching in a graph formed or selected by randomness. A matching is a set of edges with no shared endpoints. A randommatching can mean either: the result of a randomized process that builds a matching, often yielding a maximal (not necessarily maximum) matching, or a matching chosen uniformly at random from the set of all matchings of a graph. In the latter sense, one often studies the distribution of matching sizes and structure under the uniform model.
Construction methods include the random greedy algorithm: choose edges in random order, add an edge if it
Computational considerations note that uniformly sampling a matching, or counting all matchings, is generally difficult (#P-hard)
Applications of randommatching appear in randomized algorithms, testing and benchmarking of matching algorithms, modeling random pairings
---