Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
type: Item
instance of: scholarly article
title: Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
zbMATH Open document ID: 0932.05080
published in: Combinatorica
publication date: 2000-02-21T00:00:00Z
review text: Let \(G\) be a graph with two disjoint subsets \(A\), \(B\) of its vertices, with cardinalities \(a\) and \(b\), respectively. The number of edges between \(A\) and \(B\) divided by \(ab\) is the density of the pair \(A\), \(B\). A bipartite graph with bipartition \(U\), \(V\), \(|U|=|V|=n\) is \(\varepsilon\)-regular if for any pair of sets \(A\subset U\) and \(B \subset V, |A|, |B|> \varepsilon n\), the densities of the pairs \(A\), \(B\) and \(U\), \(V\) differ by at most \(\varepsilon\). If all the vertices of such an \(\varepsilon\)-regular graph \(G\) with density \(d>2\varepsilon\) have degrees not too far from \(d\) then \(G\) is known to have about as many perfect matchings as the corresponding random bipartite graph, that is, about \(d^n n!\). In the paper this result is utilized to prove that with probability quickly approaching one, a perfect matching drawn randomly from \(G\) is spread evenly, in the sense that for any large subsets of vertices \(A\subset U\) and \(B \subset V\), the number of edges of the matching spanned between \(A\) and \(B\) is close to \(|A||B|/n\). As an application an alternative proof of the blow-up lemma of \textit{J. Komlós, G. N. Sárközy} and \textit{E. Szemerédi} [Combinatorica 17, No. 1, 109-123 (1997; Zbl 0880.05049)] is given.
reviewed by: András Recski
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 1404393
zbMATH Keywords: \(\varepsilon\)-regular graphs
zbMATH Keywords: blow-up lemma
zbMATH Keywords: perfect matching
Wikidata QID: Q105584593
author: Vojtěch Rödl
author: Andrzej Ruciński
MaRDI profile type: Publication
full work available at URL: s004930050063
OpenAlex ID: W2010512224
DOI: 10.1007/S004930050063
Recommended article: Matchings meeting quotas and their impact on the blow-up lemma
Recommended article: An algorithmic version of the blow-up lemma
Recommended article: Q4247195
Recommended article: K5‐free subgraphs of random graphs
Recommended article: Holes in graphs
Recommended article: On the Bollobás–Eldridge Conjecture for Bipartite Graphs
Recommended article: Matchings in random biregular bipartite graphs
Recommended article: Small subsets inherit sparse \(\varepsilon\)-regularity
Recommended article: Q4508359
description: scientific article; zbMATH DE number 1404393