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 …

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 …

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 …