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 |
MARC
| LEADER | 00000caa a2200000 c 4500 | ||
|---|---|---|---|
| 001 | 1725598132 | ||
| 003 | DE-627 | ||
| 005 | 20220818161802.0 | ||
| 007 | cr uuu---uuuuu | ||
| 008 | 200727s2020 xx |||||o 00| ||eng c | ||
| 024 | 7 | |a 10.1002/rsa.20907 |2 doi | |
| 035 | |a (DE-627)1725598132 | ||
| 035 | |a (DE-599)KXP1725598132 | ||
| 035 | |a (OCoLC)1341348009 | ||
| 040 | |a DE-627 |b ger |c DE-627 |e rda | ||
| 041 | |a eng | ||
| 084 | |a 27 |2 sdnb | ||
| 100 | 1 | |a Glock, Stefan |e VerfasserIn |0 (DE-588)1058404121 |0 (DE-627)796847827 |0 (DE-576)414583949 |4 aut | |
| 245 | 1 | 2 | |a A rainbow blow-up lemma |c Stefan Glock, Felix Joos |
| 264 | 1 | |c 20 February 2020 | |
| 300 | |a 39 | ||
| 336 | |a Text |b txt |2 rdacontent | ||
| 337 | |a Computermedien |b c |2 rdamedia | ||
| 338 | |a Online-Ressource |b cr |2 rdacarrier | ||
| 500 | |a Gesehen am 27.07.2020 | ||
| 520 | |a 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. | ||
| 650 | 4 | |a bandwidth theorem | |
| 650 | 4 | |a blow-up lemma | |
| 650 | 4 | |a graph embedding | |
| 650 | 4 | |a rainbow colorings | |
| 700 | 1 | |a Joos, Felix |d 1989- |e VerfasserIn |0 (DE-588)1075006171 |0 (DE-627)832846244 |0 (DE-576)442747438 |4 aut | |
| 773 | 0 | 8 | |i Enthalten in |t Random structures & algorithms |d New York, NY [u.a.] : Wiley, 1990 |g 56(2020), 4, Seite 1031-1069 |h Online-Ressource |w (DE-627)306711141 |w (DE-600)1500812-5 |w (DE-576)082436185 |x 1098-2418 |7 nnas |a A rainbow blow-up lemma |
| 773 | 1 | 8 | |g volume:56 |g year:2020 |g number:4 |g pages:1031-1069 |g extent:39 |a A rainbow blow-up lemma |
| 856 | 4 | 0 | |u https://doi.org/10.1002/rsa.20907 |x Verlag |x Resolving-System |z lizenzpflichtig |3 Volltext |
| 856 | 4 | 0 | |u https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.20907 |x Verlag |z lizenzpflichtig |3 Volltext |
| 951 | |a AR | ||
| 992 | |a 20200727 | ||
| 993 | |a Article | ||
| 994 | |a 2020 | ||
| 998 | |g 1075006171 |a Joos, Felix |m 1075006171:Joos, Felix |d 110000 |d 110300 |e 110000PJ1075006171 |e 110300PJ1075006171 |k 0/110000/ |k 1/110000/110300/ |p 2 |y j | ||
| 999 | |a KXP-PPN1725598132 |e 3729502239 | ||
| BIB | |a Y | ||
| SER | |a journal | ||
| JSO | |a {"relHost":[{"note":["Gesehen am 17.02.05"],"pubHistory":["1.1990 -"],"language":["eng"],"part":{"extent":"39","pages":"1031-1069","issue":"4","text":"56(2020), 4, Seite 1031-1069","year":"2020","volume":"56"},"titleAlt":[{"title":"Random structures and algorithms"}],"disp":"A rainbow blow-up lemmaRandom structures & algorithms","type":{"bibl":"periodical","media":"Online-Ressource"},"recId":"306711141","origin":[{"dateIssuedKey":"1990","publisherPlace":"New York, NY [u.a.]","publisher":"Wiley","dateIssuedDisp":"1990-"}],"title":[{"title_sort":"Random structures & algorithms","title":"Random structures & algorithms"}],"id":{"zdb":["1500812-5"],"doi":["10.1002/(ISSN)1098-2418"],"issn":["1098-2418"],"eki":["306711141"]},"physDesc":[{"extent":"Online-Ressource"}]}],"origin":[{"dateIssuedDisp":"20 February 2020","dateIssuedKey":"2020"}],"title":[{"title_sort":"rainbow blow-up lemma","title":"A rainbow blow-up lemma"}],"type":{"media":"Online-Ressource","bibl":"article-journal"},"id":{"eki":["1725598132"],"doi":["10.1002/rsa.20907"]},"physDesc":[{"extent":"39 S."}],"person":[{"family":"Glock","role":"aut","given":"Stefan","display":"Glock, Stefan"},{"role":"aut","family":"Joos","display":"Joos, Felix","given":"Felix"}],"recId":"1725598132","note":["Gesehen am 27.07.2020"],"language":["eng"],"name":{"displayForm":["Stefan Glock, Felix Joos"]}} | ||
| SRT | |a GLOCKSTEFARAINBOWBLO2020 | ||