arXiv I’ve previously written about the Namer-Claimer game. I can now prove that the length of the game is with optimal play from each side, matching the greedy lower bound. The upper bound makes use of randomness, but in a very controlled way. Analysing a truly random strategy still seems like it will be very …

# Author: babarber

## Minimalist designs

Ben Barber, Stefan Glock, Daniela Kühn, Allan Lo, Richard Montgomery, Deryk Osthus In Edge decompositions of graphs with high minimum degree, Daniela Kühn, Allan Lo, Deryk Osthus and I proved that the edge sets of sufficiently dense graphs satisfying necessary divisibility conditions could be partitioned into copies of an arbitrary graph . This result has since …

## Chromatic number of the plane

The unit distance graph on has edges between those pairs of points at Euclidean distance . The chromatic number of this graph lies between (by exhibiting a small subgraph on vertices with chromatic number ) and (by an explicit colouring based on a hexagonal tiling of the plane). Aubrey de Grey has just posted a …

## Counting colourings with containers

On the maximum number of integer colourings with forbidden monochromatic sums, Hong Liu, Maryam Sharifzadeh and Katherine Staden Maryam spoke about this paper at this week’s combinatorics seminar. The problem is as follows. Let be the number of -colourings of a subset of with no monochromatic sum . What is the maximum of over all ? …

## Linear programming duality

The conventional statement of linear programming duality is completely inscrutable. Prime: maximise subject to and . Dual: minimise subject to and . If either problem has a finite optimum then so does the other, and the optima agree. I do understand concrete examples. Suppose we want to pack the maximum number vertex-disjoint copies of a graph …

## Random Structures and Algorithms 2017

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 …

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