Sharp thresholds for constraint satisfaction problems and homomorphisms
From MaRDI portal
Publication:3608298
DOI10.1002/rsa.20225zbMath1182.05110arXiv0903.2579OpenAlexW4234267841MaRDI 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 (19)
On the strong chromatic number of random hypergraphs ⋮ Estimating the \(r\)-colorability threshold for a random hypergraph ⋮ Panchromatic 3-coloring of a random hypergraph ⋮ Panchromatic 3-colorings of random hypergraphs ⋮ 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 ⋮ On Random Betweenness Constraints ⋮ Bounds on threshold probabilities for coloring properties of random hypergraphs ⋮ Estimating the strong \(r\)-colorability threshold in random hypergraphs ⋮ On panchromatic colourings of a random hypergraph ⋮ Two-Colorings of a Random Hypergraph ⋮ On the strong chromatic number of a random 3-uniform hypergraph ⋮ Panchromatic colorings of random hypergraphs ⋮ Branching Process Approach for 2-Sat Thresholds ⋮ On Random Ordering Constraints ⋮ On the weak chromatic number of random hypergraphs ⋮ When does the giant component bring unsatisfiability? ⋮ Threshold properties of random Boolean constraint satisfaction problems ⋮ On the chromatic number of a random hypergraph
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
This page was built for publication: Sharp thresholds for constraint satisfaction problems and homomorphisms
