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...
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Dokumenttyp: | Article (Journal) |
| Sprache: | Englisch |
| Veröffentlicht: |
20 February 2020
|
| In: |
Random structures & algorithms
Year: 2020, Jahrgang: 56, Heft: 4, Pages: 1031-1069 |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.20907 |
| Online-Zugang: | Verlag, lizenzpflichtig, Volltext: https://doi.org/10.1002/rsa.20907 Verlag, lizenzpflichtig, Volltext: https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20907 
|
| Verfasserangaben: | Stefan Glock, Felix Joos |
| Zusammenfassung: | 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. |
|---|---|
| Beschreibung: | Gesehen am 27.07.2020 |
| Beschreibung: | Online Resource |
| ISSN: | 1098-2418 |
| DOI: | 10.1002/rsa.20907 |