RANDOM 2‐SAT Does Not Depend on a Giant
| Autor: | David Kravitz |
|---|---|
| Rok vydání: | 2007 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics. 21:408-422 |
| ISSN: | 1095-7146 0895-4801 |
| Popis: | Here we introduce a new model for random 2-SAT. It is well known that on the standard model there is a sharp phase transition; the probability of satisfiability quickly drops as the number of clauses exceeds the number of variables. The location of this phase transition suggests that there is a direct connection between the appearance of a giant in the corresponding $2n$-vertex graph and satisfiability. Here we show that the giant has nothing to do with satisfiability and that in fact the expected degree of a randomly chosen vertex is the important thing. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|