A partial, chronologically ordered, list of talks I attended at RSA in Gniezno, Poland. Under construction until the set of things I can remember equals the set of things I’ve written about. Shagnik Das A family of subsets of that shatters a -set has at least elements. How many -sets can we shatter with a …
Author: babarber
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 is an grid of cells, each of which contains one of distinct symbols, such that no symbol appears twice in any row or column. There is a natural …
Matchings without Hall’s theorem
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 …
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 …