Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:
| Indexado |
|
||||
| DOI | 10.1016/J.JCTB.2020.10.001 | ||||
| Año | 2021 | ||||
| Tipo | artículo de investigación |
Citas Totales
Autores Afiliación Chile
Instituciones Chile
% Participación
Internacional
Autores
Afiliación Extranjera
Instituciones
Extranjeras
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 Briceno. 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. (c) 2020 Elsevier Inc. All rights reserved.
| Ord. | Autor | Género | Institución - País |
|---|---|---|---|
| 1 | BRICENO-DOMINGUEZ, RAIMUNDO JOSE | Hombre |
Pontificia Universidad Católica de Chile - Chile
Facultad de Matemáticas - Chile |
| 2 | Bulatov, Andrei | Hombre |
Simon Fraser Univ - Canadá
Simon Fraser University - Canadá |
| 3 | Dalmau, Victor | Hombre |
Univ Pompeu Fabra - España
Universitat Pompeu Fabra Barcelona - España |
| 4 | Larose, Benoit | - |
UNIV QUEBEC - Canadá
Université du Québec à Montréal - Canadá |
| Fuente |
|---|
| Fondo Nacional de Desarrollo Científico y Tecnológico |
| Comisión Nacional de Investigación Científica y Tecnológica |
| European Research Council |
| Natural Sciences and Engineering Research Council of Canada |
| ERC |
| NSERC |
| Horizon 2020 Framework Programme |
| CONICYT/FONDECYT POSTDOCTORADO |
| Fonds de recherche du Québec – Nature et technologies |
| FRQNT |
| MICCIN |
| Maria de Maeztu Unit of Excellence Programme |
| Agradecimiento |
|---|
| 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. |
| 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 . |