Sharp thresholds for constraint satisfaction problems and homomorphisms

DOI10.1002/RSA.20225MaRDI QIDQ3608298zbMATH OpenOpenAlexFDO

Authors

Publication date 4 March 2009

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random constraintrandom graphssatisfaction problemssatisfiability thresholds

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We determine under which conditions certain natural models of random constraint satisfaction problems have sharp thresholds of satisfiability. These models include graph and hypergraph homomorphism, the $(d,k,t)$-model, and binary constraint satisfaction problems with domain size three.

Recommendations

• A sharp threshold for a random constraint satisfaction problem
• Threshold properties of random Boolean constraint satisfaction problems
• Models for Random Constraint Satisfaction Problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Sharpness of the satisfiability threshold for non-uniform random \(k\)-SAT

Cites work

• A sharp threshold for a random constraint satisfaction problem
• A threshold for unsatisfiability
• Bounding the unsatisfiability threshold of random 3-SAT
• Combinatorial sharpness criterion and phase transition classification for random CSPs
• Generalized satisfiability problems: Minimal elements and phase transitions.
• Good and semi-strong colorings of oriented planar graphs
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• Hunting for sharp thresholds
• Many hard examples for resolution
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Sharp thresholds for certain Ramsey properties of random graphs
• Sharp thresholds of graph properties, and the k-sat problem
• Supersaturated graphs and hypergraphs
• The 3-XORSAT threshold.
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Threshold properties of random Boolean constraint satisfaction problems
• When does the giant component bring unsatisfiability?

Cited in

(24)

• When does the giant component bring unsatisfiability?
• Panchromatic 3-coloring of a random hypergraph
• A sharp threshold for a random constraint satisfaction problem
• Panchromatic colorings of random hypergraphs
• On the strong chromatic number of random hypergraphs
• Estimating the r-colorability threshold for a random hypergraph
• On the strong chromatic number of a random 3-uniform hypergraph
• On the weak chromatic number of random hypergraphs
• On the chromatic number of a random hypergraph
• Panchromatic 3-colorings of random hypergraphs
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
• Threshold properties of random Boolean constraint satisfaction problems
• Estimating the strong r-colorability threshold in random hypergraphs
• On sharp thresholds in random geometric graphs
• On Random Ordering Constraints
• On random betweenness constraints
• Branching process approach for 2-SAT thresholds
• On panchromatic colourings of a random hypergraph
• Two-colorings of a random hypergraph
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• On the concentration of values of j-chromatic numbers of random hypergraphs
• On the structure of the set of panchromatic colorings of a random hypergraph
• Bounds on threshold probabilities for coloring properties of random hypergraphs
• Threshold probabilities for colourings of random hypergraphs

This page was built for publication: Sharp thresholds for constraint satisfaction problems and homomorphisms

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