A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination [DeFord-Duchin-Solomon'21]-a popular Markov chain to sample redistricting plans-is exponentially slow mixing on simple subgraph of $\mathbb{Z}_2.$ We show an alternative way to sample balance, compact and contiguous redistricting plans using a "relaxed" version of ReCom and rejection sampling.

翻译：政治重新划分问题的一个关键任务是对重新划分地区计划进行取样,即将人口普查区块图分割到各区。我们显示,重新组合[DeFord-Duchin-Solomon'21]-一个受欢迎的重新划分计划链 — — 以抽样方式重新划分地区计划 — — 在$\mathbb ⁇ 2.$($)的简单子图上快速缓慢混合。 我们展示了另一种方法,即使用ReCom和拒绝抽样的“放松”版本来抽样平衡、紧凑和毗连的重新划分计划。