The number of matchings in random regular graphs and bipartite graphs

DOI10.1016/0095-8956(86)90029-8zbMath0602.05050OpenAlexW2093881947MaRDI QIDQ1081621

Béla Bollobás, Brendan D. McKay

Publication date: 1986

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(86)90029-8

zbMATH Keywords

random graphs1-factorsrandom bipartite graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (42)

Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems ⋮ An exact threshold theorem for random graphs and the node-packing problem ⋮ Random hypergraphs and topological gelation criterion for crosslinked polymer systems ⋮ Enumeration problems for classes of self-similar graphs ⋮ Almost all regular graphs are hamiltonian ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ \(1/n\) expansion for the number of matchings on regular graphs and Monomer-Dimer entropy ⋮ Enumeration of matchings in families of self-similar graphs ⋮ Perfect matchings in inhomogeneous random bipartite graphs in random environment ⋮ Asymptotic enumeration of digraphs and bipartite graphs by degree sequence ⋮ Complex Contagions on Configuration Model Graphs with a Power-Law Degree Distribution ⋮ Induced subgraphs in sparse random graphs with given degree sequences ⋮ Convergence of graphs with intermediate density ⋮ Random Regular Graphs: Asymptotic Distributions and Contiguity ⋮ Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums ⋮ Problems and results in extremal combinatorics. I. ⋮ Random-link matching problems on random regular graphs ⋮ Holes in random graphs ⋮ Statistical Matching Theory ⋮ Subgraphs of Dense Random Graphs with Specified Degrees ⋮ Subgraphs of Randomk-Edge-Colouredk-Regular Graphs ⋮ Cycles in random graphs ⋮ Expansion of random graphs: new proofs, new results ⋮ Hamilton cycles containing randomly selected edges in random regular graphs ⋮ On cycle lengths in claw-free graphs with complete closure ⋮ The size of the largest hole in a random graph ⋮ Asymptotic enumeration of Latin rectangles ⋮ Random dense bipartite graphs and directed graphs with specified degrees ⋮ Matchings in Benjamini–Schramm convergent graph sequences ⋮ Injective edge-coloring of graphs with given maximum degree ⋮ Non-abelian free group actions: Markov processes, the Abramov–Rohlin formula and Yuzvinskii’s formula ⋮ Asymptotic enumeration by degree sequence of graphs of high degree ⋮ Automorphisms of random graphs with specified vertices ⋮ On the expected number of perfect matchings in cubic planar graphs ⋮ The number of matchings in random graphs ⋮ An asymptotic independence theorem for the number of matchings in graphs ⋮ Almost all regular graphs are Hamiltonian ⋮ A survey of the asymptotic behaviour of maps ⋮ Hamiltonian cycles in random regular graphs ⋮ Random near-regular graphs and the node packing problem ⋮ A note on approximating Max-Bisection on regular graphs ⋮ Asymptotic enumeration of sparse 0--1 matrices with irregular row and column sums

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• On the number of edge-colourings of regular bipartite graphs
• The asymptotic number of labeled graphs with given degree sequences
• Asymptotics and random matrices with row-sum and column sum-restrictions
• The Asymptotic Number of Latin Rectangles
• Asymptotic enumeration of Latin rectangles
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The number of matchings in random regular graphs and bipartite graphs