#1 ReCom ergodicity
Statement
(a) Given a map, take the two districts with the largest shared perimeter, then redraw to minimize boundary. Does this process eventually terminate in a simple, Voronoi-like partition (for instance, possibly, the partition minimizing cut edges)? This would imply ergodicity. Or does it get stuck?
(b) Does this policy at least eventually give you a district that is -monotone (AKA "vertically convex," no gaps in any vertical slice)? If so, a theorem from the forthcoming paper says that a constant number of steps will suffice to get you to a simple canonical partition, like the Italian flag. This would also prove ergodicity.
(c) How do you efficiently compute the shortest boundary at each step in this process? This might be solved by a paper called. There is a paper that solves this in time without the requirement that districts are connected [Papadimitriou and Sideri, 1996].
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.