A rainbow blow-up lemma

DOI10.1002/RSA.20907zbMATH Open1458.05067arXiv1802.07700OpenAlexW3006754732WikidataQ124803180 ScholiaQ124803180MaRDI QIDQ5128752FDOQ5128752

Authors: Stefan Glock, Felix Joos 

Publication date: 26 October 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: We prove a rainbow version of the blow-up lemma of Koml'os, S'ark"ozy and Szemer'edi for $mun$-bounded edge colourings. This enables the systematic study of rainbow embeddings of bounded degree spanning subgraphs. As one application, we show how our blow-up lemma can be used to transfer the bandwidth theorem of B"ottcher, Schacht and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of $mun$-bounded edge colourings. Kim, K"uhn, Kupavskii and Osthus exploit this to prove several rainbow decomposition results. Our proof methods include the strategy of an alternative proof of the blow-up lemma given by R"odl and Ruci'nski, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan.

Full work available at URL: https://arxiv.org/abs/1802.07700

Recommendations

• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Rainbow structures in locally bounded colorings of graphs
• Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree
• Rainbow decompositions
• Long directed rainbow cycles and rainbow spanning trees

zbMATH Keywords

graph embeddingrainbow coloringsblow-up lemmabandwidth theorem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Title not available (Why is that?)
• Proof of the Seymour conjecture for large graphs
• The minimum degree threshold for perfect graph packings
• Title not available (Why is that?)
• A lower bound for the length of a partial transversal in a Latin square
• Proof of the Alon-Yuster conjecture
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Multicoloured Hamilton cycles
• Title not available (Why is that?)
• Rainbow matchings in Dirac bipartite graphs
• Polychromatic Hamilton cycles
• Blow-up lemma
• Optimal packings of bounded degree trees
• Proof of a Packing Conjecture of Bollobás
• On rainbow trees and cycles
• A constructive proof of the general Lovász local lemma
• Using Lovász local lemma in the space of random injections
• Covering with Latin transversals
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• Title not available (Why is that?)
• On the Bollobás–Eldridge Conjecture for Bipartite Graphs
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Hamilton circuits with many colours in properly edge-coloured complete graphs.
• Perfect matchings in \(\varepsilon\)-regular graphs and the blow-up lemma
• Rainbow matchings in properly colored multigraphs
• Properly colored and rainbow copies of graphs with few cherries
• Linearly many rainbow trees in properly edge-coloured complete graphs
• An approximate version of a conjecture of Aharoni and Berger
• Decompositions into spanning rainbow structures
• Constraint satisfaction, packet routing, and the lovasz local lemma
• Bounded colorings of multipartite graphs and hypergraphs
• Rainbow spanning trees in properly coloured complete graphs
• Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree
• A blow-up lemma for approximate decompositions
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• Embedding rainbow trees with applications to graph labelling and decomposition
• Long directed rainbow cycles and rainbow spanning trees

Cited In (9)

• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Repeated patterns in proper colorings
• A rainbow Dirac's theorem
• The bandwidth theorem for locally dense graphs
• Rainbow factors in hypergraphs
• A Short proof of the blow-up lemma for approximate decompositions
• Properly colored Hamilton cycles in Dirac-type hypergraphs
• On sufficient conditions for spanning structures in dense graphs
• Graph Tilings in Incompatibility Systems

This page was built for publication: A rainbow blow-up lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128752)