Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma (Q1964595): Difference between revisions

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.