𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the random generation and counting of matchings in dense graphs

✍ Scribed by J. Diaz; M. Serna; P. Spirakis

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
628 KB
Volume
201
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

In this work we present a fully randomized approximation scheme for counting the number of perfect matchings in a dense bipartite graphs, that is equivalent to get a fully randomized approximation scheme to the permanent of a dense boolean matrix. We achieve this known solution, through novel extensions in the theory of suitable non-reversible, Markov chains which mix rapidly and have a near-uniform distribution.

πŸ“œ SIMILAR VOLUMES

On large matchings and cycles in sparse
On large matchings and cycles in sparse random graphs
✍ A.M Frieze πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 666 KB

Let k be a fixed positive integer. A graph H has property Mk if it contains [Β½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induce

Generating and Counting Hamilton Cycles
Generating and Counting Hamilton Cycles in Random Regular Graphs
✍ Alan Frieze; Mark Jerrum; Michael Molloy; Robert Robinson; Nicholas Wormald πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 216 KB

Let G be chosen uniformly at random from the set G G r, n of r-regular graphs w x Ε½ . with vertex set n . We describe polynomial time algorithms that whp i find a Ε½ . Hamilton cycle in G, and ii approximately count the number of Hamilton cycles in G.

Matching and covering the vertices of a
Matching and covering the vertices of a random graph by copies of a given graph
✍ Andrzej RuciΕ„ski πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 747 KB

## Rucidski, A., Matching and covering the vertices of a random graph by copies of a given graph, Discrete Mathematics 105 (1992) 185-197. In this paper we partially answer the question: how slowly must p(n) converge to 0 so that a random graph K(n, p) has property PM, almost surely, where PM, me