Decompositions into spanning rainbow structures

Research output: Contribution to journalArticlepeer-review

Standard

Decompositions into spanning rainbow structures. / Montgomery, Richard; Alexey, Pokrovskiy; Sudakov, Benny.

In: Proceedings of the London Mathematical Society, Vol. 119, No. 4, 10.2019, p. 899-959.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Montgomery, Richard ; Alexey, Pokrovskiy ; Sudakov, Benny. / Decompositions into spanning rainbow structures. In: Proceedings of the London Mathematical Society. 2019 ; Vol. 119, No. 4. pp. 899-959.

Bibtex

@article{91a2163038dc4e1cb28672d841a2c5fb,
title = "Decompositions into spanning rainbow structures",
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 200 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 Kn,n which can be decomposed into rainbow perfect matchings. While there are proper edge-colourings of Kn,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 Kn,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 Kn,n with quadratically many colours. The above result also has implications to some conjectures of Snevily about subsquares of multiplication tables of groups. Finally, 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.",
author = "Richard Montgomery and Pokrovskiy Alexey and Benny Sudakov",
year = "2019",
month = oct,
doi = "10.1112/plms.12245",
language = "English",
volume = "119",
pages = "899--959",
journal = "London Mathematical Society. Proceedings ",
issn = "0024-6115",
publisher = "London Mathematical Society",
number = "4",

}

RIS

TY - JOUR

T1 - Decompositions into spanning rainbow structures

AU - Montgomery, Richard

AU - Alexey, Pokrovskiy

AU - Sudakov, Benny

PY - 2019/10

Y1 - 2019/10

N2 - 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 200 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 Kn,n which can be decomposed into rainbow perfect matchings. While there are proper edge-colourings of Kn,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 Kn,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 Kn,n with quadratically many colours. The above result also has implications to some conjectures of Snevily about subsquares of multiplication tables of groups. Finally, 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.

AB - 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 200 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 Kn,n which can be decomposed into rainbow perfect matchings. While there are proper edge-colourings of Kn,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 Kn,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 Kn,n with quadratically many colours. The above result also has implications to some conjectures of Snevily about subsquares of multiplication tables of groups. Finally, 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.

UR - http://www.scopus.com/inward/record.url?scp=85064054474&partnerID=8YFLogxK

U2 - 10.1112/plms.12245

DO - 10.1112/plms.12245

M3 - Article

VL - 119

SP - 899

EP - 959

JO - London Mathematical Society. Proceedings

JF - London Mathematical Society. Proceedings

SN - 0024-6115

IS - 4

ER -