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 does not conflict with already chosen ones, and continue. This yields a maximal matching and is fast, with relatively simple analysis in many graph classes. For complete graphs, there is a simple procedure to generate a uniform random perfect matching: repeatedly select a random unpaired vertex and pair it with a uniformly chosen other unpaired vertex.

Computational considerations note that uniformly sampling a matching, or counting all matchings, is generally difficult (#P-hard) in general graphs; exact sampling is intractable for large graphs. Nevertheless, approximate methods exist: Markov chain Monte Carlo approaches can be used to sample from distributions over matchings in certain restricted graph classes, and simple randomized greedy procedures are common and easy to implement as baselines.

Applications of randommatching appear in randomized algorithms, testing and benchmarking of matching algorithms, modeling random pairings in experiments, resource allocation problems, network routing, and scheduling. See also: matching (graph theory), randomized algorithm, Markov chain Monte Carlo.

---