{"id":"arxiv/2610.42067","url":"https://arxiv.org/abs/2610.42067","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\\geq 2$","domain":"cs.DM","source":"arxiv","authors":["Yanyu Chen","Yu Chen"],"reviews":0,"subject":"cs.DM","summary":"Given a simple undirected graph on $n$ vertices, random $k$-out sampling forms a spanning subgraph by having each vertex independently choose $k$ incident edges uniformly with replacement. We prove that, for every integer $k\\geq2$, the expected number of original edges joining distinct sampled components is $O(n/k)$. This resolves the conjecture of Holm, King, Thorup, Zamir, and Zwick in its full range, improving their logarithmic sampling requirement to the optimal threshold of two choices per vertex. The bound fails for $k=1$, and the dependence $O(n/k)$ is tight up to constant factors.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}