• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems 
    •   QMRO Home
    • School of Mathematical Sciences
    • Applied Mathematics
    • Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems
    •   QMRO Home
    • School of Mathematical Sciences
    • Applied Mathematics
    • Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems
    ‌
    ‌

    Browse

    All of QMROCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    ‌
    ‌

    Administrators only

    Login
    ‌
    ‌

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Uniqueness, spatial mixing, and approximation for ferromagnetic 2-spin systems

    View/Open
    Published Version (645.3Kb)
    Volume
    60
    ISBN-13
    9783959770187
    DOI
    10.4230/LIPIcs.APPROX-RANDOM.2016.31
    ISSN
    1868-8969
    Metadata
    Show full item record
    Abstract
    For anti-ferromagnetic 2-spin systems, a beautiful connection has been established, namely that the following three notions align perfectly: The uniqueness of Gibbs measures in infinite regular trees, the decay of correlations (also known as spatial mixing), and the approximability of the partition function. The uniqueness condition implies spatial mixing, and an FPTAS for the partition function exists based on spatial mixing. On the other hand, non-uniqueness implies some long range correlation, based on which NP-hardness reductions are built. These connections for ferromagnetic 2-spin systems are much less clear, despite their similarities to anti-ferromagnetic systems. The celebrated Jerrum-Sinclair Markov chain [8] works even if spatial mixing fails. Also, for a fixed degree the uniqueness condition is non-monotone with respect to the external field, which seems to have no meaningful interpretation in terms of computational complexity. However, it is still intriguing whether there are some relationship underneath the apparent disparities among them. We provide some answers to this question. Let β,γbe the (0, 0) and (1, 1) edge interactions respectively (βγ > 1), and λ the external field for spin "0". For graphs with degree bound Δ ≤ Δc + 1 where Δc = √ βγ+1 √ βγ-1 , regardless of the field (even inconsistent fields are allowed), correlation decay always holds and FPTAS exists. If all fields satisfy λ < λc (assuming β≤ γ ), where λc = (γ/β)Δc+1 2 , then a weaker version of spatial mixing holds in all trees. Moreover, if β≤ 1, then λ < λc is sufficient to guarantee strong spatial mixing and FPTAS. This improves the best previous algorithm, a Markov chain based FPRAS for λ ≤ γ/β [13]. The bound λc is almost optimal and can be viewed as a variant of the uniqueness condition with the degree d relaxed to be a real number instead of an integer. When β ≤ 1, uniqueness holds in all infinite regular trees, if and only if λ ≤ λint c , where λint c = (γ/β) δd-ce+1 2 . If we allow fields λ > λint c 0, where λint c 0 = (γ/β) b-cc+2 2 , then approximating the partition function is #BIS-hard. Interestingly, unless λc is an integer, neither λc nor λint c is the tight bound in each own respect. We provide examples where correlation decay continues to hold in a small interval beyond λc, and irregular trees in which spatial mixing fails for some λ < λint c .
    Authors
    Guo, H; Lu, P; 20th International Workshop on Randomization and Computation (RANDOM'2016)
    URI
    http://qmro.qmul.ac.uk/xmlui/handle/123456789/18011
    Collections
    • Applied Mathematics [140]
    Licence information
    licensed under Creative Commons License CC-BY Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016).
    Copyright statements
    © Heng Guo and Pinyan Lu;
    Twitter iconFollow QMUL on Twitter
    Twitter iconFollow QM Research
    Online on twitter
    Facebook iconLike us on Facebook
    • Site Map
    • Privacy and cookies
    • Disclaimer
    • Accessibility
    • Contacts
    • Intranet
    • Current students

    Modern Slavery Statement

    Queen Mary University of London
    Mile End Road
    London E1 4NS
    Tel: +44 (0)20 7882 5555

    © Queen Mary University of London.