Sharp thresholds for constraint satisfaction problems and homomorphisms
From MaRDI portal
Publication:3608298
DOI10.1002/rsa.20225zbMath1182.05110arXiv0903.2579MaRDI QIDQ3608298
No author found.
Publication date: 4 March 2009
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0903.2579
Related Items
On Random Betweenness Constraints, Branching Process Approach for 2-Sat Thresholds, On panchromatic colourings of a random hypergraph, Two-Colorings of a Random Hypergraph, On the concentration of values of \(j\)-chromatic numbers of random hypergraphs, Bounds on threshold probabilities for coloring properties of random hypergraphs, When does the giant component bring unsatisfiability?, Panchromatic 3-coloring of a random hypergraph, 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, Threshold properties of random Boolean constraint satisfaction problems, Estimating the strong \(r\)-colorability threshold in random hypergraphs, On Random Ordering Constraints
Cites Work
- Unnamed Item
- Combinatorial sharpness criterion and phase transition classification for random CSPs
- A threshold for unsatisfiability
- Supersaturated graphs and hypergraphs
- When does the giant component bring unsatisfiability?
- Good and semi-strong colorings of oriented planar graphs
- Generalized satisfiability problems: Minimal elements and phase transitions.
- The 3-XORSAT threshold.
- A sharp threshold for a random constraint satisfaction problem
- Threshold properties of random Boolean constraint satisfaction problems
- Many hard examples for resolution
- The Resolution Complexity of Random Constraint Satisfaction Problems
- Sharp thresholds of graph properties, and the $k$-sat problem
- Sharp thresholds for certain Ramsey properties of random graphs
- Bounding the unsatisfiability threshold of random 3-SAT
- The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
- Hunting for sharp thresholds
- Random constraint satisfaction: A more accurate picture
- Random constraint satisfaction: Flaws and structure
