> Detailanzeige

Salez, Justin

Weighted enumeration of spanning subgraphs in locally tree‐like graphs

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: E-Artikel
  • Titel: Weighted enumeration of spanning subgraphs in locally tree‐like graphs
  • Beteiligte: Salez, Justin
  • Erschienen: Wiley, 2013
  • Erschienen in: Random Structures & Algorithms
  • Sprache: Englisch
  • DOI: 10.1002/rsa.20436
  • ISSN: 1042-9832; 1098-2418
  • Schlagwörter: Applied Mathematics ; Computer Graphics and Computer-Aided Design ; General Mathematics ; Software
  • Entstehung:
  • Anmerkungen:
  • Beschreibung: <jats:title>Abstract</jats:title><jats:p>Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree‐like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a <jats:italic>b</jats:italic>‐matching in the Erdős–Rényi random graph with fixed average degree and diverging size, for any <jats:styled-content>\documentclass{article}\usepackage{mathrsfs, amsmath, amssymb}\pagestyle{empty}\begin{document}$b\in\mathbb{N}$\end{document}<jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/tex2gif-ueqn-1.gif" xlink:title="equation image" /></jats:styled-content>. To the best of our knowledge, this is the first time that correlation inequalities and unimodularity are combined together to yield a general proof of uniqueness of Gibbs measures on infinite trees. We believe that a similar argument is applicable to other Gibbs measures than those over spanning subgraphs considered here. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013</jats:p>