A note on random 2-SAT with prescribed literal degrees

ABSTRACT

Two classic "phase transitions" in discrete mathematics are the emergence of a giant component in a random graph as the density of edges increases, and the transition of a random 2-SAT formula from satisfiable to unsatisfiable as the density of clauses increases. The random-graph result has been extended to the case of prescribed degree sequences, where the almost-sure nonexistence or existence of a giant component is related to a simple property of the degree sequence. We similarly extend the satisfiability result, by relating the almost-sure satisfiability or unsatisfiability of a random 2-SAT formula to an analogous property of a prescribed literal sequence.

REFERENCES

• 1: B. Aspvall, M. F. Plass and R. E. Tarjan, A linear time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters 8 (1979) 121-123.
• 2: B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European Journal of Combinatorics 1 (1980) 311-316.
• 3: Béla Bollobás , Christian Borgs , Jennifer T. Chayes , Jeong Han Kim , David B. Wilson, The scaling window of the 2-SAT transition, Random Structures & Algorithms, v.18 n.3, p.201-256, May 2001 [doi>10.1002/rsa.1006]
• 4: V. Chvatál and B. Reed, Mick gets some (the odds are on his side), Proceedings of the 33rd Annual IEEE Symposium on the Foundations of Computer Science (1992) 620-627.
• 5: C. Cooper, A. M. Frieze and B. Reed, Random regular graphs of non-constant degree: connectivity and Hamilton cycles, to appear.
• 6: C. Cooper, A. M. Frieze, B. Reed and O. Riordan, Random regular graphs of non-constant degree: independence and chromatic number, to appear.
• 7: W. Fernandez de la Vega, On random 2-SAT, manuscript 1992.
• 8: Andreas Goerdt, A threshold for unsatisfiability, Journal of Computer and System Sciences, v.53 n.3, p.469-486, Dec. 1996 [doi>10.1006/jcss.1996.0081]
• 9: Michael Molloy , Bruce Reed, The Size of the Giant Component of a Random Graph with a Given Degree Sequence, Combinatorics, Probability and Computing, v.7 n.3, p.295-305, September 1998 [doi>10.1017/S0963548398003526]
• 10: B. D. McKay, Asymptotics for symmetric 0-1 matrices with prescribed row sums, Ars Combinatoria 19A (1985) 15-26.
• 11: B. D. McKay and N. C. Wormald, Asymptotic enumeration by degree sequence of graphs with degree o(n1/2), Combinatorica 11 (1991) 369-382.
• 12: Yann Verhoeven, Random 2-SAT and unsatisfiability, Information Processing Letters, v.72 n.3-4, p.119-123, Nov. 1999 [doi>10.1016/S0020-0190(99)00128-3]