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 …