Open Research Index

Optimal matching under size priority

Nathanaël Enriquez, Mike Liu, Laurent Ménard, Vianney Perchet

arXivarxiv/2601.20502Jan 28, 2026math.PRscore 0

Past studies on the local limit of maximal weight matchings in edge-weighted large random graphs rely fundamentally on the assumption that the weights are atomless, which ensures that the maximal weight matching is unique. This excludes de facto maximal size matchings that correspond to equal edge-weights. In this work, we overcome this difficulty by assigning i.i.d.~atomless weights to edges and choosing the maximal size matching that maximises the weight. We call these doubly constrained matchings \emph{optimal matchings}. The natural generalisation of optimal matchings for infinite…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2601.20502
curl -X POST /api/v1/records/arxiv/2601.20502/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.20502/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'