Decompositions into spanning rainbow structures

DOI10.1112/PLMS.12245MaRDI QIDQ4973646zbMATH OpenOpenAlexFDO

Authors Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov

Publication date 28 November 2019

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.07564, http://pure-oai.bham.ac.uk/ws/files/59119123/rainbow_decompositions.pdf

zbMATH Keywords

complete graphdecompositiongeneralized Latin squareHamiltonian cycleperfect matchingrainbow subgraphrandom subgraphspanning treetransversal

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Trees (05C05) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80) Transversal (matching) theory (05D15)

Abstract: A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back more than two hundred years to the work of Euler on Latin squares and has been the focus of extensive research ever since. Euler posed a problem equivalent to finding properly $n$-edge-coloured complete bipartite graphs $K_{n,n}$ which can be decomposed into rainbow perfect matchings. While there are proper edge-colourings of $K_{n,n}$ without even a single rainbow perfect matching, the theme of this paper is to show that with some very weak additional constraints one can find many disjoint rainbow perfect matchings. In particular, we prove that if some fraction of the colour classes have at most $(1-o(1))n$ edges then one can nearly-decompose the edges of $K_{n,n}$ into edge-disjoint perfect rainbow matchings. As an application of this, we establish in a very strong form a conjecture of Akbari and Alipour and asymptotically prove a conjecture of Barat and Nagy. Both these conjectures concern rainbow perfect matchings in edge-colourings of $K_{n,n}$ with quadratically many colours. Using our techniques, we also prove a number of results on near-decompositions of graphs into other rainbow structures like Hamiltonian cycles and spanning trees. Most notably, we prove that any properly coloured complete graph can be nearly-decomposed into spanning rainbow trees. This asymptotically proves the Brualdi-Hollingsworth and Kaneko-Kano-Suzuki conjectures which predict that a perfect decomposition should exist under the same assumptions.

Recommendations

• Decompositions into isomorphic rainbow spanning trees
• Rainbow decompositions
• Rainbow spanning structures in graph and hypergraph systems
• Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations
• Rainbow structures in a collection of graphs with degree conditions
• Rainbow spanning trees in properly coloured complete graphs
• Regular 1-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees
• Rainbow spanning trees in abelian groups
• Rainbow spanning trees in complete graphs colored by one‐factorizations
• Edge-disjoint rainbow spanning trees in complete graphs

Cited in

(35)

• Parity of transversals of Latin squares
• Rainbow connectivity and rainbow criticality on graph classes
• The \(n\)-queens completion problem
• Decompositions into isomorphic rainbow spanning trees
• A proof of Ringel's conjecture
• Rainbow matchings and cycle-free partial transversals of Latin squares
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• On the complexity of packing rainbow spanning trees
• Quaternionic 1-factorizations and complete sets of rainbow spanning trees
• On the number of symbols that forces a transversal
• Pseudorandom hypergraph matchings
• Regular 1-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees
• New bounds for Ryser’s conjecture and related problems
• Color isomorphic even cycles and a related Ramsey problem
• A rainbow blow-up lemma
• Rainbow structures in locally bounded colorings of graphs
• A rainbow Dirac's theorem
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Repeated patterns in proper colorings
• Transversals in generalized Latin squares
• A counterexample to Stein's equi-\(n\)-square conjecture
• Rainbow perfect matchings in complete bipartite graphs: existence and counting
• Rainbow decompositions
• Full rainbow matchings in graphs and hypergraphs
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• scientific article; zbMATH DE number 7731161 (Why is no real title available?)
• Rainbow Subgraphs and their Applications
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Graph and hypergraph packing
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Tangled paths: a random graph model from Mallows permutations
• A random Hall-Paige conjecture
• Ringel's tree packing conjecture in quasirandom graphs
• Graph theory. Abstracts from the workshop held January 6--12, 2019
• Maximum transversal in partial Latin squares and rainbow matchings

This page was built for publication: Decompositions into spanning rainbow structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4973646)