Expectation conjecture for mandatory and blocking edges in Erdős–Rényi graphs

Let GnG_n be Erdős–Rényi graphs with parameters (n,c/n)(n,c/n), and let Mmax(Gn)\mathcal{M}_{\max}(G_n) be the set of maximum-size matchings of GnG_n. Let γ\underline{\gamma} be the smallest solution of

x=ececx,x=e^{-ce^{-cx}},

and set γ=ecγ\overline{\gamma}=e^{-c\underline{\gamma}}.

Mandatory and blocking edge expectation conjecture. The expected proportions of edges belonging to every maximum-size matching and of edges belonging to no maximum-size matching satisfy

limnE[1E(Gn)eE(Gn)\mathbbm1MMmax(Gn), eM]=γ2,\lim_{n\to\infty}\mathbb{E}\left[\frac{1}{|E(G_n)|}\sum_{e\in E(G_n)}\mathbbm{1}_{\forall M\in\mathcal{M}_{\max}(G_n),\ e\in M}\right]=\underline{\gamma}^{2}, limnE[1E(Gn)eE(Gn)\mathbbm1MMmax(Gn), eM]=(1γ)2.\lim_{n\to\infty}\mathbb{E}\left[\frac{1}{|E(G_n)|}\sum_{e\in E(G_n)}\mathbbm{1}_{\forall M\in\mathcal{M}_{\max}(G_n),\ e\notin M}\right]=(1-\overline{\gamma})^{2}.

This extends the corresponding law of large numbers from the subcritical regime to convergence in expectation, where concentration is not expected in general.

Sources & referencesView supporting material

Primary source

Nathanaël Enriquez, Mike Liu, Laurent Ménard and Vianney Perchet, “Optimal matching under size priority”, arXiv:2601.20502 (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.