Perfect matchings in -regular graphs and the blow-up lemma
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.
- Matchings meeting quotas and their impact on the blow-up lemma
- An algorithmic version of the blow-up lemma
- scientific article; zbMATH DE number 1301962
- K5‐free subgraphs of random graphs
- Holes in graphs
- On the Bollobás–Eldridge Conjecture for Bipartite Graphs
- Matchings in random biregular bipartite graphs
- Small subsets inherit sparse \(\varepsilon\)-regularity
- scientific article; zbMATH DE number 1512672
- Ore-type versions of Brooks' theorem
- A fast parallel algorithm for finding Hamiltonian cycles in dense graphs
- Perfect matching for regular graphs is AC^ 0-hard for the general matching problem
- Perfect matchings in \(\varepsilon\)-regular graphs
- On the number of perfect matchings and Hamilton cycles in -regular non-bipartite graphs
- Sharpening an ore-type version of the Corrádi-Hajnal theorem
- Ramsey numbers for bipartite graphs with small bandwidth
- An Ore-type theorem on equitable coloring
- A Short proof of the blow-up lemma for approximate decompositions
- Matchings meeting quotas and their impact on the blow-up lemma
- Spanning embeddings of arrangeable graphs with sublinear bandwidth
- Triangle-tilings in graphs without large independent sets
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Regular pairs in sparse random graphs I
- Three-Color Bipartite Ramsey Number for Graphs with Small Bandwidth
- A blow-up lemma for approximate decompositions
- Decompositions of quasirandom hypergraphs into hypergraphs of bounded degree
- A rainbow blow-up lemma
- A rainbow blow-up lemma for almost optimally bounded edge-colourings
- A refinement of a result of Corrádi and Hajnal
- An extension of the blow-up lemma to arrangeable graphs
- A fast algorithm for equitable coloring
- Equitable versus nearly equitable coloring and the Chen-Lih-Wu Conjecture
- Random perfect matchings in regular graphs
- Global maker-breaker games on sparse graphs
- Sparse partition universal graphs for graphs of bounded degree
- A rainbow blow-up lemma for almost optimally bounded edge-colourings
- Transversals via regularity
- Perfect matchings in uniform hypergraphs with large minimum degree
- Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
- Spanning 3-colourable subgraphs of small bandwidth in dense graphs
- On 2-factors with \(k\) components
- Proof of the bandwidth conjecture of Bollobás and Komlós
- Distributing vertices along a Hamiltonian cycle in Dirac graphs
This page was built for publication: Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1964595)
