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 by , we can't possibly do better than a maximum difference of between blocks.  Is this achievable in general?

In today's combinatorics seminar Imre Bárány described joint work with Victor Grinberg which says that the answer is yes.

The proof is algorithmic.  Start with any partition of into parts.  If the difference in length between the smallest and largest parts is at most then we're done, so assume not.  Fix a longest block and let be a shortest block.  Suppose without loss of generality that is to the right of .  Increase the length of by stealing one piece from the part to the left of .  Repeat this process until either we find a good partition of , or we steal a piece from .  On each iteration a piece moves away from , so one of these must occur in finite time.

At each stage we add a piece of length at most to a block of length more than shorter than , so we never create new blocks of length at least that of .  So when is destroyed there are either fewer blocks of maximal length, or the number of blocks of maximal length has decreased.  There are only finitely many possible lengths for blocks, so by repeating with a new block of maximal length we are guaranteed to find a good partition in finite time.

Leave a Reply

Your email address will not be published.