← All problems

Holm–King–Thorup–Zamir–Zwick k-out sampling conjecture

Let G=(V,E)G=(V,E) be a simple undirected graph with ∣V∣=n|V|=n. For each vertex independently, choose kk incident edges uniformly with replacement, and let HkH_k be the spanning subgraph consisting of all chosen edges. If Xk(G)X_k(G) denotes the number of edges of GG whose endpoints lie in distinct connected components of HkH_k, then there is an absolute constant C>0C>0 such that, for every integer k≥2k\ge 2 and every GG, E[Xk(G)]≤Cn/k\mathbb{E}[X_k(G)]\le Cn/k.

References

Progress summary

Refreshed
Open · solution reported

A new unrefereed preprint claims that two random choices per vertex suffice, but the claimed resolution has not been independently checked.

Holm, King, Thorup, Zamir, and Zwick conjectured that the expected number of edges between sampled-subgraph components is O(n/k)O(n/k) whenever k≥2k\ge2, improving the known logarithmic threshold. The conjecture is false for k=1k=1.

Known results

  • Holm, King, Thorup, Zamir, and Zwick (2019): the O(n/k)O(n/k) bound for arbitrary nn-vertex graphs when k≥clog⁡nk\ge c\log n.
  • Holm, King, Thorup, Zamir, and Zwick (2019): the bound is optimal and fails for k=1k=1.

October 2026 claimed resolution

Chen and Chen's preprint claims the bound for every integer k≥2k\ge2, proving 6n/(k−2)6n/(k-2) for k≥3k\ge3 and a separate 500n500n bound for k=2k=2; it also claims the result without replacement. The claim is supported only by this unrefereed preprint. OpenAI Codex is credited with assisting the authors, not with independently producing the result.

Current status (as of November 2026): The logarithmic-sampling theorem is established, while the extension to every k≥2k\ge2 is claimed but remains unverified.

Sources

Solutions 0

No solutions have been posted yet.