RANDOM 2‐SAT Does Not Depend on a Giant
David Kravitz · SIAM Journal on Discrete Mathematics · 2007
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.