Projects per year
Abstract
Our main result essentially reduces the problem of finding an edge-decomposition of a balanced r -partite graph of large minimum degree
into r -cliques to the problem of finding a fractional r -clique decomposition or an approximate one. Together with very recent results of Bowditch and Dukes as well as Montgomery on fractional decompositions into triangles and cliques respectively, this gives the best known bounds on the minimum degree which ensures an edge-decomposition of an r -partite graph into r -cliques (subject to trivially necessary divisibility conditions). The case of triangles translates into the setting of partially completed Latin squares and more generally the case of r -cliques translates into the setting of partially completed mutually orthogonal Latin squares.
into r -cliques to the problem of finding a fractional r -clique decomposition or an approximate one. Together with very recent results of Bowditch and Dukes as well as Montgomery on fractional decompositions into triangles and cliques respectively, this gives the best known bounds on the minimum degree which ensures an edge-decomposition of an r -partite graph into r -cliques (subject to trivially necessary divisibility conditions). The case of triangles translates into the setting of partially completed Latin squares and more generally the case of r -cliques translates into the setting of partially completed mutually orthogonal Latin squares.
Original language | English |
---|---|
Pages (from-to) | 146-201 |
Number of pages | 55 |
Journal | Journal of Combinatorial Theory, Series A |
Volume | 151 |
Early online date | 10 May 2017 |
DOIs | |
Publication status | Published - Oct 2017 |
Keywords
- Edge-decompositions
- Mutually orthogonal Latin squares
Fingerprint
Dive into the research topics of 'Clique decompositions of multipartite graphs and completion of Latin squares'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Randomized approaches to combinatorIal packing and covering problems
Engineering & Physical Science Research Council
1/03/15 → 28/02/18
Project: Research Councils