Matching-size conjecture for random geometric graphs

From papers

Let X1,,XniidPnX_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(X1X222<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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.