Pseudo-dimension matching limit for dense graph sequences
Pseudo-dimension matching limit for dense graph sequences
Let be a sequence of graphs admitting a graphon limit , with edge weights following a distribution of pseudo-dimension . Suppose that there exists such that the measure on given by has density at least everywhere, and let denote the minimum total weight of a perfect matching. Dense graph matching conjecture. The quantity
converges in probability to a constant depending only on and . This is presented as a speculation extending the proved convergence result for complete bipartite graphs; the source does not provide a resolution, so the conjecture remains open.
Sources & referencesView supporting material
Primary source
Joel Larsson, “The Minimum Perfect Matching in Pseudo-dimension 0<q<1”, arXiv:1403.3635 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.