Ben Barber,\u00a0Daniela K\u00fchn, Allan Lo, Deryk Osthus and Amelia Taylor, Journal of Combinatorial Theory, Series A, Volume 151, October 2017, Pages 146\u2013201<\/a>\u00a0PDF<\/a><\/p>\n A Latin square of order is an grid of cells, each of which contains one of distinct symbols, such that no symbol appears twice in any row or column. \u00a0There is a natural correspondence between\u00a0Latin squares of order and partitions of into triangles. \u00a0We identify the three vertex classes of with the rows, columns and symbols of the Latin square. \u00a0A triangle corresponds to the symbol appearing in the intersection of row and column of the Latin square. \u00a0Since each cell contains exactly one symbol, and each symbol appears exactly once in each row and each column, the triangles corresponding to a Latin square do indeed partition\u00a0.<\/p>\n What about partitions of into ‘s? \u00a0Identify the vertex classes of with rows, columns, red symbols and \u00a0blue symbols. \u00a0Then a corresponds to a red symbol and a blue symbol in the intersection of row and column . \u00a0If we look at just the red symbols or just the blue symbols then we see a Latin square. \u00a0But we also have the extra property that each pair of red and blue symbol appears in exactly one cell of the grid. \u00a0Two Latin squares with this property are called\u00a0orthogonal<\/em>. \u00a0So pairs of orthgonal Latin squares of order correspond to decompositions of into ‘s. \u00a0More generally, a sequence of \u00a0mutually orthogonal<\/em> Latin squares of order \u00a0corresponds to a partition of the complete -partite graph on vertex classes of size into ‘s.<\/p>\n Suppose now that we have a\u00a0partial<\/em> Latin square of order , that is, a partially filled in grid of cells obeying the rules for a Latin square. \u00a0Can it be completed to a Latin square? \u00a0In the early 1980s several researchers proved that the answer is yes provided at most cells have been filled in total. \u00a0This is best possible, as if we place ‘s and a single on the main diagonal there is no legal cell in which to place the th . \u00a0The same example shows that it is not enough to ask only that each row and each column contains only a small number of non-empty cells. \u00a0But what if each row, column and symbol has been used at most times? \u00a0Can we then complete to a Latin square? \u00a0Daykin and H\u00e4ggkvist conjectured that we can, provided .<\/p>\n What does this mean on the graph side? \u00a0Let be a subgraph of obtained by deleting a set of edge-disjoint triangles such that no vertex is in more than triangles. \u00a0Then should have a triangle-decomposition if . \u00a0In this paper we prove that has a triangle-decomposition provided .<\/p>\n In fact we prove something more general. \u00a0The ‘s obtained in this way have the properties that (i) each vertex has the same number of neighbours in each other vertex class and (ii) each vertex sees at least a proportion of the vertices in each other class (a partite minimum degree condition). \u00a0We prove that all such graphs have triangle-decompositions when .<\/p>\n