A rainbow blow-up lemma
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 t...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article (Journal) |
| Language: | English |
| Published: |
20 February 2020
|
| In: |
Random structures & algorithms
Year: 2020, Volume: 56, Issue: 4, Pages: 1031-1069 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.20907 |
| Online Access: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.20907 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20907 
|
| Author Notes: | Stefan Glock, Felix Joos |
| Summary: | 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. |
|---|---|
| Item Description: | Gesehen am 27.07.2020 |
| Physical Description: | Online Resource |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.20907 |