Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

The minimum perfect matching in pseudo-dimension 0 < q < 1

Larsson, Joel LU orcid (2021) In Combinatorics Probability and Computing 30(3). p.374-397
Abstract

It is known that for Kn,n equipped with i.i.d. exp (1) edge costs, the minimum total cost of a perfect matching converges to <![CDATA[ $\zeta(2)=\pi^2/6$ ]]> in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension <![CDATA[ $q \geq 1$ ]]>. In this paper we extend those results to all real positive q, confirming the Mézard-Parisi conjecture in the last remaining applicable case.

Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
05C80, 2020 MSC Codes:, 60C05
in
Combinatorics Probability and Computing
volume
30
issue
3
pages
374 - 397
publisher
Cambridge University Press
external identifiers
  • scopus:85095689939
ISSN
0963-5483
DOI
10.1017/S0963548320000425
language
English
LU publication?
yes
id
0b80a905-afa8-45b2-a51a-7e73b426275c
date added to LUP
2020-11-25 07:33:41
date last changed
2022-04-26 22:05:15
@article{0b80a905-afa8-45b2-a51a-7e73b426275c,
  abstract     = {{<p>It is known that for Kn,n equipped with i.i.d. exp (1) edge costs, the minimum total cost of a perfect matching converges to &lt;![CDATA[ $\zeta(2)=\pi^2/6$ ]]&gt; in probability. Similar convergence has been established for all edge cost distributions of pseudo-dimension &lt;![CDATA[ $q \geq 1$ ]]&gt;. In this paper we extend those results to all real positive q, confirming the Mézard-Parisi conjecture in the last remaining applicable case. </p>}},
  author       = {{Larsson, Joel}},
  issn         = {{0963-5483}},
  keywords     = {{05C80; 2020 MSC Codes:; 60C05}},
  language     = {{eng}},
  number       = {{3}},
  pages        = {{374--397}},
  publisher    = {{Cambridge University Press}},
  series       = {{Combinatorics Probability and Computing}},
  title        = {{The minimum perfect matching in pseudo-dimension 0 < q < 1}},
  url          = {{http://dx.doi.org/10.1017/S0963548320000425}},
  doi          = {{10.1017/S0963548320000425}},
  volume       = {{30}},
  year         = {{2021}},
}