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.
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.