Near-uniform degree distribution in regular spanning subgraphs

Status partial high confidence

Conjecture 1.1 remains open for general d, but significant partial progress has been made. Fox, Luo, and Pham (2022) confirmed the asymptotic weaker version (Conjecture 1.2) for d = o(n/(log n)^12) via a probabilistic argument. Ma and Xie (2024) proved, via deterministic local adjustment techniques, that the conjecture holds exactly for d=3 (cubic graphs, in a strong form) and gave a general bound |m(H,k) - n/(d+1)| ≤ 2d² independent of n for all d-regular graphs — the first such n-independent bound.

Cited literature (2)

• partial On random irregular subgraphs (2022)
  Jacob Fox, Sammy Luo, Huy Tuan Pham · arXiv preprint (published in Random Structures & Algorithms, 2024) · arXiv:2207.13651

  Confirms the asymptotic version of Conjecture 1.1 (Conjecture 1.2) for all d-regular graphs with d = o(n/(log n)^12) by showing the irregular random subgraph H satisfies m(H,k) = (1+o(1))n/(d+1) for all 0 ≤ k ≤ d with high probability; does not resolve Conjecture 1.1 itself.

• partial Finding irregular subgraphs via local adjustments (2024)
  Jie Ma, Shengjie Xie · arXiv preprint · arXiv:2406.05675

  Fully proves Conjecture 1.1 for d=3 (cubic graphs) in a strong form and establishes a general n-independent bound |m(H,k) - n/(d+1)| ≤ 2d² for all d-regular graphs, using deterministic local adjustment techniques.

Reviewer notes. Conjecture 1.1 is open for d ≥ 4 in general. The Ma-Xie 2024 paper (arXiv:2406.05675) represents the strongest deterministic progress: it resolves d=3 completely and provides the first n-independent general bound. The Fox-Luo-Pham paper was published in Random Structures & Algorithms (2024) but the DOI link (Wiley) returned HTTP 402 and could not be verified directly.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).