A rainbow blow‐up lemma. Issue 4 (20th February 2020)

• Record Type: Journal Article
• Authors: Glock, Stefan; Joos, Felix
• Is Part Of: Random structures & algorithms. Volume 56:Issue 4(2020)
• Page Start: 1031
• Page End: 1069
• Publication Date: 2020-02-20
• Subjects: bandwidth theorem -- blow‐up lemma -- graph embedding -- rainbow colorings; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20907
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We prove a rainbow version of the blow‐up lemma of Komlós, Sárközy, and Szemerédi for μn ‐bounded edge colorings. 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öttcher, Schacht, and Taraz to the rainbow setting. It can also be employed as a tool beyond the setting of μn ‐bounded edge colorings. Kim, Kühn, 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ödl and Ruciński, the switching method, and the partial resampling algorithm developed by Harris and Srinivasan.