Welcome to the UPF Digital Repository

Dismantlability, connectedness, and mixing in relational structures

Show simple item record

dc.contributor.author Briceño, Raimundo
dc.contributor.author Bulatov, Andrei A.
dc.contributor.author Dalmau, Víctor
dc.contributor.author Larose, Benoit
dc.date.accessioned 2023-02-09T13:11:11Z
dc.date.available 2023-02-09T13:11:11Z
dc.date.issued 2021
dc.identifier.citation Briceño R, Bulatov A, Dalmau V, Larose B. Dismantlability, connectedness, and mixing in relational structures. J Comb Theory Ser B. 2021;147:37-70. DOI: 10.1016/j.jctb.2020.10.001
dc.identifier.issn 0095-8956
dc.identifier.uri http://hdl.handle.net/10230/55701
dc.description.abstract The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have been shown to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved—like, for example, dismantlability—and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Briceño. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.
dc.description.sponsorship The first author was supported by CONICYT/FONDECYT Postdoctorado 3190191 and ERC Starting Grants 678520 and 676970. The second author was supported by an NSERC Discovery grant. The third author was supported by MICCIN grants TIN2016-76573-C2-1P and PID2019-109137GB-C22, and Maria de Maeztu Unit of Excellence Programme MDM-2015-0502. The fourth author was supported by an NSERC Discovery grant and FRQNT.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Elsevier
dc.relation.ispartof Journal of Combinatorial Theory, Series B. 2021;147:37-70.
dc.rights © Elsevier http://dx.doi.org/10.1016/j.jctb.2020.10.001
dc.title Dismantlability, connectedness, and mixing in relational structures
dc.type info:eu-repo/semantics/article
dc.identifier.doi http://dx.doi.org/10.1016/j.jctb.2020.10.001
dc.subject.keyword Relational structure
dc.subject.keyword Constraint satisfaction problem
dc.subject.keyword Homomorphism
dc.subject.keyword Mixing properties
dc.subject.keyword Gibbs measure
dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/678520
dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/676970
dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TIN2016-76573-C2-1P
dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PID2019-109137GB-C22
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/acceptedVersion


This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account


Compliant to Partaking