Pseudo-dimension matching limit for dense graph sequences

Let GnG_n be a sequence of graphs admitting a graphon limit G\mathcal{G}, with edge weights following a distribution of pseudo-dimension qq. Suppose that there exists ε>0\varepsilon>0 such that the measure on [0,1]2[0,1]^2 given by G\mathcal{G} has density at least ε\varepsilon everywhere, and let M(Gn)M(G_n) denote the minimum total weight of a perfect matching. Dense graph matching conjecture. The quantity

n1+1/qM(Gn)n^{-1+1/q}M(G_n)

converges in probability to a constant depending only on qq and G\mathcal{G}. 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

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.