Answers are grounded in this paper and cite their sources.
In the bilateral preference random graph $LK(n,k)$ of La and Kabkab, independent uniform scores are placed on the edges of Kₙ, each vertex prefers its k incident edges of smallest score, and an edge is kept when both of its endpoints prefer it. Dabirian and Subramanian showed that $LK(n,k)$ is connected with high probability when k≥log n+tloglog n√log n with $t>1/2$ and disconnected when $t<-1/2$, and left the window between these two conditions open. We show that for every fixed C, uniformly over integers k with |k-log n|≤ C, the number of isolated vertices is asymptotically Poisson with mean ne⁻ᵏ in total variation and the probability that $LK(n,k)$ is connected is exp(-ne⁻ᵏ)+o(1). Consequently $LK(n,k)$ is connected with high probability if and only if k-log n→∞, and disconnected with high probability if and only if k-log n→-∞. The main estimate is that a fixed set of r vertices is isolated with probability e⁻ʳᵏ(1+o(1)); it comes from an exact integral formula for the rejections at one vertex and a direct count of the few edges through which the vertices of the set can interact.
No takes yet. Share an insight, caveat, or question.
Yitzchak Shmalo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: