I am a postdoc in the School of Mathematics at the University of Birmingham working with Daniela Kühn and Deryk Osthus. I completed my PhD in the Department of Pure Mathematics and Mathematical Statistics at the University of Cambridge under the supervision of Imre Leader. My email address is b.a.[surname]@bham.ac.uk.
- Fractional clique decompositions of dense graphs and hypergraphs (with Daniela Kühn, Allan Lo, Richard Montgomery and Deryk Osthus) pdf
Together with Daniela Kühn, Allan Lo and Deryk Osthus I proved that for every graph F there is a constant cF < 1 such that every "F-divisible" graph G on n vertices with minimum degree at least (cF + o(1))n has an F-decomposition.
In practice, the current obstacle to improving the bounds on cF 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/10000r3/2)n has a fractional Kr-decomposition. This greatly improves the previous bound of (1-2/9r4)n for large r. We also prove a similar result for hypergraphs.
The proof begins with an approximate fractional Kr-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 Kr-decomposition.
- Edge-decompositions of graphs with high minimum degree (with Daniela Kühn, Allan Lo and Deryk Osthus) 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 C6), 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 ∪ 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 (with Neil Hindman, Imre Leader and Dona Strauss) JCTA pdf
In "Partition regularity in the rationals" we (Barber, Hindman and Leader) showed that there are systems of equations that are partition regular over Q but not over Z. Here we show that this separation is very strong: there is an uncountable chain of subgroups from Z to 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 (with Neil Hindman, Imre Leader and Dona Strauss) 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 of a system of De and Hindman INTEGERS pdf
- De and Hindman proposed that a particular system should be partition regular but not partition regular near zero. With Neil Hindman and Imre Leader I found a different example: in this paper I show that De and Hindman's original system also works.
- Partition regularity with congruence conditions (with Imre Leader) JoC 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 (with Neil Hindman and Imre Leader) JCTA 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 (with Eoin Long) ElecJC 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.
- Maximum hitting for n sufficiently large GCOM pdf
Borg asked what happens to the Erdős-Ko-Rado theorem if we only count sets meeting some fixed set X, and answered the question for |X| ≥ r, the size of the sets in the set family. This paper answers the question for |X| < r, provided n, the size of the ground set, is sufficiently large.
There is a typo in the proof of Theorem 4 in the published paper. The line beginning "By Lemma 9, F(2, n, G)( X) has size polynomial in n ..." should read "By Lemma 9, F( r, n, G)( X) ... ". (Thanks to Candida Bowtell for spotting this.)
- A note on balanced independent sets in the cube AusJC pdf
- How large can an independent set in the discrete cube be if it contains equal numbers of sets of even and odd size? Take odd sets starting from the bottom of the cube, and even sets starting from the top. Proving that this works uses an isoperimetric inequality: if you know the proof of Harper's theorem that uses codimension 1 compressions then you know how to prove the inequality that's quoted without proof in this paper.