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 …

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 …

Matchings and minimum degree

A Tale of Two Halls (Philip) Hall’s theorem.  Let be a bipartite graph on vertex classes , .  Suppose that,  for every , .  Then there is a matching from to . This is traditionally called Hall’s marriage theorem.  The picture is that the people in are all prepared to marry some subset of the …

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 …

Nowhere zero 6-flows

A flow on a graph is an assignment to each edge of of a direction and a non-negative integer (the flow in that edge) such that the flows into and out of each vertex agree.  A flow is nowhere zero if every edge is carrying a positive flow and (confusingly) it is a -flow if the flows …