OpenFrontiers
Join
← Back to the index
OP-11175Partially solvedProbability

#33 ReCom transition function complexity

Mathematical foundations of sampling connected balanced graph partitions · AIMPL workshop record

MSC 60 · Probability theory and stochastic processes

Editorial mapping of AIMPL source category: Probability. http://aimpl.org/connectedbalanced/ Not an author-supplied MSC code.

Source reports partially-solvedAs of 2026-09-10 source snapshot; not a current-status certificationSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Does the ReCom transition function run in polynomial time? Or can it get stuck in configurations where it is very unlikely a random tree will be splittable? Can we at least show that such configurations are exponentially unlikely?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Workshop introduction

This is a list of open research problems compiled during the June 2025 AIM workshop, maintained by Jamie Tucker-Foltz.

Last updated: May 2026

If you have questions, comments, or updates on the status of any problem, please email: j.tuckerfoltz@yale.edu

Section context

These questions concern the probability that a random spanning tree is kk-spittable, meaning that the removal of (k−1)(k - 1) edges disconnects the tree into kk subtrees with (approximately) equal numbers of vertices, or population weight.

Progress & source assessment

Dated source record, inspected 2026-09-10. Source reports a negative answer to the first question and explicitly leaves the likelihood question open. Source-reported results have not been independently verified.

Status note in the source

Micah Gold has answered the first question in the negative, constructing a family of partitions where random spanning trees on any merged pair of parts are exponentially unlikely to be splittable. See: https://arxiv.org/abs/2606.01333 The likelihood of such configurations is still an open question.

References
  1. [1]Mathematical foundations of sampling connected balanced graph partitions · Original question link
  2. [2]AIMPL source bibliography link
  3. [3]AIMPL text license · CC BY-SA 3.0 linkAIM Problem Lists (AIMPL), original contributors; CC BY-SA 3.0. Adaptation: structural TeX converted to Markdown, documented source macros expanded, and source bibliography links added. Mathematical wording retained. These adapted source texts remain under CC BY-SA 3.0.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.