Matching-size conjecture for random geometric graphs
Matching-size conjecture for random geometric graphs
Let , where and may scale with , and let be the corresponding geometric graph. Let be its largest matching, and suppose
Matching-size conjecture. Under this assumption,
and the same order holds with high probability for . 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
Sign in to submit a solution.
No solutions have been posted yet.