Invariant probability measures and dynamics of exponential linear type maps

DOI10.1017/S014338570700106XMaRDI QIDQ3623581zbMATH OpenFDO

Authors David Gamarnik, Tomasz Nowicki, Grzegorz Świrszcz

Publication date 21 April 2009

Published in Ergodic Theory and Dynamical Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0402343

zbMATH Keywords

matchingsrandom graphunique invariant measure

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Dynamical systems and their relations with probability theory and stochastic processes (37A50)

Abstract: We consider the question of existence of a unique invariant probability distribution which satisfies some evolutionary property. The problem arises from the random graph theory but to answer it we treat it as a dynamical system in the functional space, where we look for a global attractor. We consider the following bifurcation problem: Given a probability measure $mu$, which corresponds to the weight distribution of a link of a random graph we form a positive linear operator $Phi$ (convolution) on distribution functions and then we analyze a family of its exponents with a parameter $lambda$ which corresponds to connectivity of a sparse random graph. We prove that for every measure $mu$ (emph{i.e.}, convolution $Phi$) and every $lambda<e$ there exists a unique globally attracting fixed point of the operator, which yields the existence and uniqueness of the limit probability distribution on the random graph. This estimate was established earlier cite{KarpSipser} for deterministic weight distributions (Dirac measures $mu$) and is known as $e$-cutoff phenomena, as for such distributions and $lambda>e$ there is no fixed point attractor. We thus establish this phenomenon in a much more general sense.

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• scientific article; zbMATH DE number 1139976
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• scientific article; zbMATH DE number 6469137

Cites work

• Asymptotics in the random assignment problem
• Linear phase transition in random linear constraint satisfaction problems
• Nonmonotonic behavior in hard-core and Widom-Rowlinson models
• Percolation and the hard-core lattice gas model
• The (2) limit in the random assignment problem

Cited in

(3)

• The planted matching problem: phase transitions and exact results
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Dynamics of linear maps of idempotent measures

This page was built for publication: Invariant probability measures and dynamics of exponential linear type maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3623581)