Dismantlability, Connectedness, and Mixing in Relational Structures
DOI10.4230/LIPIcs.ICALP.2019.29zbMath1503.08001OpenAlexW2964105866MaRDI QIDQ5091178
Raimundo Briceño, Andrei A. Bulatov, Victor Dalmau, Benoit Larose
Publication date: 21 July 2022
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/10605/pdf/LIPIcs-ICALP-2019-29.pdf
Applications of graph theory (05C90) Combinatorial probability (60C05) Applications of universal algebra in computer science (08A70) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Enumerating homomorphisms
- Gibbs measures and phase transitions.
- On the complexity of reconfiguration problems
- Sequential cavity method for computing free energy and surface pressure
- For 2-D lattice spin systems weak mixing implies strong mixing
- Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
- Graph homomorphisms and phase transitions
- Gibbs measures and dismantlable graphs
- Conjunctive-query containment and constraint satisfaction
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- Vertex-to-vertex pursuit in a graph
- Introduction to reconfiguration
- Entropies realizable by block gluing \(\mathbb{Z}^{d}\) shifts of finite type
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Linear programming, width-1 CSPs, and robust satisfaction
- On the density of periodic configurations in strongly irreducible subshifts
- Counting independent sets up to the tree threshold
- The Complexity of Constraint Satisfaction Problems (Invited Talk)
- The topological strong spatial mixing property and new conditions for pressure approximation
- Crowns, Fences, and Dismantlable Lattices
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Information, Physics, and Computation
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Weak consistency notions for all the CSPs of bounded width
- Factoring onto ℤ^{𝕕} subshifts with the finite extension property
- Mixing in time and space for lattice spin systems: A combinatorial view
- An Introduction to Symbolic Dynamics and Coding
- Multidimensional sofic shifts without separation and their factors
- Strong spatial mixing in homomorphism spaces
- Tree-shifts: Irreducibility, mixing, and the chaos of tree-shifts
- Gibbs states and the set of solutions of random constraint satisfaction problems
- A Characterisation of First-Order Constraint Satisfaction Problems
- Dualities for Constraint Satisfaction Problems
This page was built for publication: Dismantlability, Connectedness, and Mixing in Relational Structures
