Stromquist–Woodall theorem

Proof sketch

1. . Proof: take .
2. If, then also. Proof: take. If is a union of intervals in a circle, then is also a union of intervals.
3. is a closed set. This is easy to prove, since the space of unions of intervals is a compact set under a suitable topology.
4. If, then also. This is the most interesting part of the proof; see below.

Proof sketch for part 4

• Assume that is a union of intervals and that all partners value it as exactly.
• Define the following function on the cake, :
• Define the following measures on :
• Note that. Hence, for every partner :.
• Hence, by the Stone–Tukey theorem, there is a hyper-plane that cuts to two half-spaces,, such that:
• Define and. Then, by the definition of the :
• The set has connected components. Hence, its image also has connected components.
• The hyperplane that forms the boundary between and intersects in at most points. Hence, the total number of connected components in and is. Hence, one of these must have at most components.
• Suppose it is that has at most components. Hence, has at most components.
• Hence, we can take. This proves that.

  Tightness proof

Proof sketch for $w=1/n$

• Choose equally-spaced points along the circle; call them.
• Define measures in the following way. Measure is concentrated in small neighbourhoods of the following points:. So, near each point, there is a fraction of the measure.
• Define the -th measure as proportional to the length measure.
• Every subset whose consensus value is, must touch at least two points for each of the first measures. Hence, it must touch at least points.
• On the other hand, every subset whose consensus value is, must have total length . The number of "gaps" between the points is ; hence the subset can contain at most gaps.
• The consensus subset must touch points but contain at most gaps; hence it must contain at least intervals.