In practice matchings are found not by following the proof of Hall’s theorem but by starting with some matching and improving it by finding augmenting paths. Given a matching in a bipartite graph on vertex classes and , an augmenting path is a path from to such that ever other edge of is an edge of …

# Author: babarber

## Block partitions of sequences

Let be a line segment of length broken into pieces of length at most . It’s easy to break into blocks (using the preexisting breakpoints) that differ in length by at most (break at the nearest available point to , etc.). In the case where each piece has length and the number of pieces isn’t divisible …

## The Namer-Claimer game

Consider the following game played on the integers from to . In each round Namer names a forbidden distance , then Claimer claims a subset of that does not contain any two integers at distance . After finitely many rounds, Claimer will have claimed sets that cover the whole of , at which point the …

## 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 …

## 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, Volume 127, November 2017, Pages 148–186 PDF Together with Daniela Kühn, Allan Lo and Deryk Osthus I proved that for every graph there is a constant such that every “-divisible” graph on vertices with minimum degree at least has an …

## 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 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 …

## 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 but not over . Here we show that this separation is …

## 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 …