A rainbow blow-up lemma

DOI10.1002/RSA.20907MaRDI QIDQ5128752zbMATHOpenAlexWikidataFDO

Authors Stefan Glock, Felix Joos

Publication date 26 October 2020

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

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

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)

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.

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

Cites work

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

Cited in

(10)

• The bandwidth theorem for locally dense graphs
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Graph Tilings in Incompatibility Systems
• Rainbow factors in hypergraphs
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• A rainbow Dirac's theorem
• Repeated patterns in proper colorings
• 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

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)