Connectivity of a family of bilateral preference random graphs

Abstract We study the bilateral preference graphs $\mathit{LK}(n, k)$ of La and Kabkab, obtained as follows. Put independent and uniform [0, 1] weights on the edges of the complete graph $K_n$ . Then, each edge ( i , j ) is included in $\mathit{LK}(n,k)$ if it is bilaterally preferred, in the sense that it is among the k edges of lowest weight incident to vertex i , and among the k edges of lowest weight incident to vertex j . We show that $k = \log(n)$ is the connectivity threshold, solving a conjecture of La and Kabkab, and obtaining finer results about the window. We also investigate the asymptotic behavior of the average degree of vertices in $\mathit{LK}(n, k)$ as $n\rightarrow\infty$ .