Clique decompositions of multipartite graphs and completion of Latin squares

Ben Barber, Daniela Kühn, Allan Lo, Deryk Osthus and Amelia Taylor Journal of Combinatorial Theory, Series A, Volume 151, October 2017, Pages 146-201 PDF

A Latin square of order n is an n \times n grid of cells, each of which contains one of n distinct symbols, such that no symbol appears twice in any row or column.  There is a natural correspondence between Latin squares of order n and partitions of E(K_{n,n,n}) into triangles.  We identify the three vertex classes of K_{n,n,n} with the n rows, n columns and n symbols of the Latin square.  A triangle ijx corresponds to the symbol x appearing in the intersection of row i and column j of the Latin square.  Since 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 E(K_{n,n,n}).

What about partitions of K_{n,n,n,n} into K_4‘s?  Identify the vertex classes of K_{n,n,n,n} with n rows, n columns, n red symbols and n  blue symbols.  Then a K_4 ijxy corresponds to a red symbol x and a blue symbol y in the intersection of row i and column j.  If we look at just the red symbols or just the blue symbols then we see a Latin square.  But we also have the extra property that each pair xy of red and blue symbol appears in exactly one cell of the grid.  Two Latin squares with this property are called orthogonal.  So pairs of orthgonal Latin squares of order n correspond to decompositions of K_{n,n,n,n} into K_4‘s.  More generally, a sequence of r-2 mutually orthogonal Latin squares of order n  corresponds to a partition of the complete r-partite graph on vertex classes of size n into K_r‘s.

Suppose now that we have a partial Latin square of order n, that is, a partially filled in n \times n grid of cells obeying the rules for a Latin square.  Can it be completed to a Latin square?  In the early 1980s several researchers proved that the answer is yes provided at most n-1 cells have been filled in total.  This is best possible, as if we place n-1 x‘s and a single y on the main diagonal there is no legal cell in which to place the nth x.  The 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.  But what if each row, column and symbol has been used at most \epsilon n times?  Can we then complete to a Latin square?  Daykin and Häggkvist conjectured that we can, provided \epsilon \leq 1/4.

What does this mean on the graph side?  Let G be a subgraph of K_{n,n,n} obtained by deleting a set of edge-disjoint triangles such that no vertex is in more than \epsilon n triangles.  Then G should have a triangle-decomposition if \epsilon \leq 1/4.  In this paper we prove that G has a triangle-decomposition provided \epsilon \leq 3/104 - o(1).

In fact we prove something more general.  The G‘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 1-\epsilon proportion of the vertices in each other class (a partite minimum degree condition).  We prove that all such graphs have triangle-decompositions when \epsilon \leq 3/104 - o(1).

The proof is based on that of the similar result for non-partite graphs in Edge decompositions of graphs with high minimum degree.  However, it is not simply a translation of that proof to the partite setting.  In the partite case we not only have to ensure that all of our gadgets can be embedded in partite graphs, we must also take care to ensure a stronger notion of divisibility is preserved throughout our decomposition process.  This makes the proof extremely technical.

We also prove the analogous result for K_r-decompositions of complete r-partite graphs, with the less impressive bound \epsilon \leq 1/10^6r^3.  The connection to mutually orthogonal Latin squares is more complicated for r \geq 4, as the partially filled in cells only correspond to K_r‘s in the case where each non-empty cell contains one of each symbol, but we still show that there is some \epsilon such that if each row, column and coloured symbol is used at most \epsilon n times then partial mutually orthogonal Latin squares can be complete.

As for the non-partite case, the bounds on \epsilon are currently limited by available fractional or approximate decomposition results.  Improvements to these would lead automatically to improvements of the bounds in this paper.

Partition regularity and other combinatorial problems

This is the imaginative title of my PhD thesis.  It contains four unrelated pieces of work.  (I was warned off using this phrasing in the thesis itself, where the chapters are instead described as “self-contained”.)

The first and most substantial concerns partition regularity.  It is a coherent presentation of all of the material from Partition regularity in the rationals, Partition regularity with congruence conditions and Partition regularity of a system of De and Hindman.

The remaining three chapters are expanded versions of Maximum hitting for


sufficiently large, Random walks on quasirandom graphs and A note on balanced independent sets in the cube.1

1 “A note … ” was fairly described by one of my examiners as a “potboiler”.  It was also my first submitted paper, and completed in my second of three years.  Perhaps this will reassure anybody in the first year of a PhD who is worrying that they have yet to publish.

Fractional clique decompositions of dense graphs and hypergraphs

Ben Barber, Daniela Kühn, Allan Lo, Richard Montgomery and Deryk Osthus, Journal of Combinatorial Theory, Series B PDF

Together with Daniela Kühn, Allan Lo and Deryk Osthus I proved that for every graph F there is a constant c_F < 1 such that every “F-divisible” graph G on n vertices with minimum degree at least (c_F + o(1))n has an F-decomposition. In practice, the current obstacle to improving the bounds on c_F is usually our knowledge of another quantity, the fractional decomposition threshold for cliques.

A graph G has a fractional F-decomposition if we can assign a non-negative weight to each copy of F in G such that the total weight of the copies of F containing each fixed edge of G is exactly 1. We prove that every graph with minimum degree at least (1-1/10000r^{3/2})n has a fractional K_r-decomposition. This greatly improves the previous bound of (1-2/9r^4)n for large r. We also prove a similar result for hypergraphs.

The proof begins with an approximate fractional K_r-decomposition obtained by weighting every r-clique in our graph equally. We then use small gadgets to make local adjustments to the total weight over each edge until we end up with a genuine fractional K_r-decomposition.

Edge-decompositions of graphs with high minimum degree

Ben Barber, Daniela Kühn, Allan Lo and Deryk Osthus, Advances in Mathematics, Volume 288, 22 January 2016, Pages 337–385 PDF

When can the edge set of a graph G be partitioned into triangles? Two obvious necessary conditions are that the total number of edges is divisible by 3 and the degree of every vertex is even. We call these conditions triangle divisibility. Triangle divisibility is not a sufficient condition for triangle decomposition (consider C_6), but it is sufficient if G is complete. So we would like to know how far from complete G can be and triangle divisibility still remain sufficient for triangle decomposition. Nash-Williams conjectured that minimum degree 3n/4 (where n is the number of vertices of G) should suffice for large n. In this paper we prove that every triangle divisible graph with minimum degree 9n/10 + o(n) has a triangle decomposition. We also prove similar results with any graph F in place of triangles.

The proof uses the absorbing method. It is very easy to remove triangles at the beginning of the process, but very hard at the end. So we make use of the flexibility we have at the beginning to make a plan for dealing with a small remainder. The key idea is that given a possible remainder R we can find a graph A such that A and A \cup R both have triangle decompositions. By reserving sufficiently many such A at the start of the process we know that we will be able to solve our problems at the end.

Distinguishing subgroups of the rationals by their Ramsey properties

Ben Barber, , Neil Hindman, Imre Leader and Dona Strauss, Journal of Combinatorial Theory, Series A, Volume 129, January 2015, Pages 93–104 PDF

In Partition regularity in the rationals we (Barber, Hindman and Leader) showed that there are systems of equations that are partition regular over \mathbb Q but not over \mathbb Z. Here we show that this separation is very strong: there is an uncountable chain of subgroups from \mathbb Z to \mathbb Q such that each subgroup has a system that is partition regular over it but over no earlier subgroup. We use our new central sets approach, but this result could also have been proved using the original density method.

Most of the work in this paper is spent proving that the systems we construct are strongly partition regular, in the sense that the variables can be forced to take different values. If you only want to see the application then you can skip part of the argument without losing anything.

Partition regularity without the columns property

Ben Barber, Neil Hindman, Imre Leader and Dona Strauss, Proc. Amer. Math. Soc. 143 (2015), 3387-3399 PDF

Rado’s theorem states that a finite matrix is partition regular if and only if it has the “columns property”. It is easy to write down infinite matrices with the columns property that are not partition regular, but all known examples of partition regular matrices do have the columns property. In this paper we describe a matrix that is partition regular but fails to have the columns property in the strongest possible sense.

The main contribution of this paper is a translation of the key lemma of “Partition regularity in the rationals” to work with central, rather than dense, sets. Central sets have very strong combinatorial properties; for example, they contain solutions to all finite partition regular systems. As a result, our theorems are harder to prove but easier to apply—for the application above we could have proved the partition regularity of the systems using density methods, but the argument would have been more involved.

Partition regularity with congruence conditions

Ben Barber and Imre Leader, Journal of Combinatorics, Volume 4 (2013), Number 3 PDF

Does a partition regular system remain partition regular if we ask that each variable x_i is divisible by d_i? Not necessarily. This answers several open questions from Hindman, Leader and Strauss’s 2003 survey.

The proof of Proposition 5 in the journal version is not entirely clear; I recommend reading the updated pdf linked above. My thanks to Boaz Tsaban for pointing this out.

Partition regularity in the rationals

Ben Barber, Neil Hindman, Imre Leader, Journal of Combinatorial Theory, Series A, Volume 120, Issue 7, September 2013, Pages 1590–1599 PDF

A system of linear equations is partition regular if, whenever the natural numbers are finitely coloured, the system of equations has a monochromatic solution. Partition regularity can also be defined over the rationals, and if the system of equations is finite then these notions coincide. We construct an example of an infinite system which is partition regular over the rationals but not the naturals. The proof is based on examining what happens when you take iterated sumsets and difference sets of subsets of the integers with positive upper density.

Random walks on quasirandom graphs

Ben Barber and Eoin Long, The Electronic Journal of Combinatorics, 20(4) (2013), #P25 PDF

Take a long (proportional to n^2) random walk W in a quasirandom graph G. Must the subgraph of edges traversed by W be quasirandom? We’d like to say yes, for the following reason: W visits every vertex about the same number of times, so we pick up the same number of random edges at every vertex. In the case where the minimum degree of G is large, this argument is essentially correct. If G has some vertices of very low degree then it breaks down because the random walk can get stuck in clusters of low degree vertices. However, a more sophisticated argument can recover a result that is almost as strong.

The proofs both fall into two parts: first show that the random walk does not differ too much from a process that has much more independence, then exploit that independence by applying standard concentration results to show that things work with high probability. It turns out that our results can be tweaked to apply to the more general case of random homomorphisms of trees (rather than paths) provided the maximum degree of the tree isn’t too large, so we indicate the necessary changes at the end of the paper.