Matching-size conjecture for random geometric graphs

About 2 years old · traced to

Let X1,…,Xn∼iidPnX_1,\dots,X_n\stackrel{\mathrm{iid}}{\sim}\mathcal{P}_n, where rr and dd may scale with nn, and let G({X1,…,Xn},r,d,∥⋅∥)G(\{X_1,\dots,X_n\},r,d,\|\cdot\|) be the corresponding geometric graph. Let MrM_r be its largest matching, and suppose

E[∣E(G(n,r,d,∥⋅∥))∣]=(n2)P(∥X1−X2∥22<r2)⟶n→∞+∞.\mathbb{E}\left[|E(G(n,r,d,\|\cdot\|))|\right]=\binom{n}{2}\mathbb{P}\left(\|X_1-X_2\|_2^2<r^2\right)\underset{n\to\infty}{\longrightarrow}+\infty.

Matching-size conjecture. Under this assumption,

E[∣Mr∣]=Θ(E[∣E(G(n,r,d,∥⋅∥))∣]∧n),\mathbb{E}[|M_r|]=\Theta\left(\mathbb{E}[|E(G(n,r,d,\|\cdot\|))|]\wedge n\right),

and the same order holds with high probability for ∣Mr∣|M_r|. This would give the typical largest-matching size from the expected edge count, capped at the number of vertices, in a regime where the expected number of edges diverges.

References

Primary source

Lucas da Rocha Schwengber and Roberto Imbuzeiro Oliveira, “Geometric planted matchings beyond the Gaussian model”, arXiv:2403.17469 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.