TL;DR
This paper formally proves that "bilateral preference" random graphs—where edges only form if both endpoints rank each other in their top $k$ choices—become connected exactly when $k \approx \log(n)$. By settling a decade-old conjecture, the authors show that despite complex mutual dependencies, these graphs share the same fundamental connectivity threshold as simpler, independent random graph models.
What Problem Does This Paper Address?
In the study of networks, we often use the Erdős–Rényi (ER) model, where edges appear independently with some probability $p$. However, real-world networks—like social circles or economic partnerships—often rely on mutual preference.
Imagine a "dating" graph where every person has a ranked list of everyone else. In a unilateral model (like the Cooper–Frieze model), an edge forms if either person ranks the other in their top $k$. In a bilateral model (the $LK(n, k)$ model studied here), an edge only forms if both people rank each other in their respective top $k$.
Because the existence of an edge $(i, j)$ depends on both $i$'s and $j$'s preferences, the edges are no longer independent. This creates a "complicated dependence structure" that makes traditional proofs fail. Since 2015, researchers La and Kabkab conjectured that the threshold for the entire graph to become one connected piece was $k = \log(n)$, but a formal proof remained elusive until now.
Methods
The authors employ a mix of classical probabilistic methods and clever asymptotic approximations:
- The Second Moment Method: To prove the graph is disconnected for small $k$, they show that the expected number of isolated vertices (nodes with no edges) goes to infinity and that these vertices appear somewhat independently.
- ER Sub- and Super-graphs: To prove connectivity for large $k$, they sandwich the complex $LK(n, k)$ graph between two simpler Erdős–Rényi graphs. By showing that even the "weaker" ER sub-graph is connected, they prove the $LK$ graph must be too.
- Infinite Urn Models: To handle the math as the number of vertices $n$ goes to infinity, they map the discrete ranking problem onto a continuous "urn model." This allows them to use multinomial distributions to approximate the probability of mutual agreement.
- Stirling’s Approximation: Used to derive the fine-grained asymptotic behavior of the average degree.
Datasets
As a theoretical mathematics and probability paper, no empirical datasets were used. The work is based on mathematical proofs and simulations of the $LK(n, k)$ random graph model.
Key Insights and Ideas
- The Logarithmic Threshold: The most significant "aha" moment is that the connectivity threshold for bilateral graphs is essentially the same as for ER graphs ($mean\ degree > \log n$). Even though the bilateral requirement is much stricter than unilateral preference, the system scales in a familiar way.
- The "Agreement Tax": In a unilateral model, the average degree is roughly $2k$. In this bilateral model, the authors show the average degree is significantly lower: approximately $k - \sqrt{k/\pi}$. This "tax" represents the difficulty of finding mutual matches compared to one-sided interests.
- Dependency Resilience: The paper demonstrates that the global property of connectivity is surprisingly resilient to the local dependencies introduced by the bilateral agreement rule.
Key Results
- Connectivity Threshold (Theorem 1.1): The authors pinpoint the threshold with high precision. If $k$ is slightly below $\log(n)$ (specifically $k \le \log(n) - 0.5 \log \log(n) \sqrt{\log(n)}$), the graph is disconnected with high probability. If $k$ is slightly above that same window, it is connected.
- Average Degree Characterization (Theorem 6.2): For $k = o(n^{1/3})$, the expected degree $D$ of a vertex is: $$\mathbb{E}[D] = k - \sqrt{\frac{k}{\pi}} + \frac{1}{8\sqrt{\pi k}} + o\left(\frac{1}{\sqrt{k}}\right)$$ This provides a much-needed correction to previous affine conjectures that oversimplified the relationship.
Limitations and Future Work
- The "Gap": There is still a narrow window around the threshold—specifically $\log(n) \pm 0.5 \log \log(n) \sqrt{\log(n)}$—where it is not yet known if the graph is connected or not. Closing this gap requires even more "elaborate" sufficient conditions.
- Graph Diameter: While connectivity is now proven, the diameter (the longest shortest path) of the graph for this specific range of $k$ remains an open question.
- Degree Concentration: The authors suggest investigating whether the degrees of all nodes "concentrate" tightly around the mean, a property common in ER graphs but harder to prove here due to dependencies.
- Variance Calculation: Calculating the exact variance of the degree ($\text{Var}[D]$) remains difficult because the connectivity of different nodes is intertwined.
Summary updated