Holm–King–Thorup–Zamir–Zwick k-out sampling conjecture
Let be a simple undirected graph with . For each vertex independently, choose incident edges uniformly with replacement, and let be the spanning subgraph consisting of all chosen edges. If denotes the number of edges of whose endpoints lie in distinct connected components of , then there is an absolute constant such that, for every integer and every , .
References
- Two choices suffice: k-out sampling leaves O(n/k) intercomponent edges for k≥2 — arXiv — Yanyu Chen, Yu Chen
Source: arXiv
Progress summary
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 whenever , improving the known logarithmic threshold. The conjecture is false for .
Known results
- Holm, King, Thorup, Zamir, and Zwick (2019): the bound for arbitrary -vertex graphs when .
- Holm, King, Thorup, Zamir, and Zwick (2019): the bound is optimal and fails for .
October 2026 claimed resolution
Chen and Chen's preprint claims the bound for every integer , proving for and a separate bound for ; 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 is claimed but remains unverified.
Solutions 0
No solutions have been posted yet.