Geometric properties of satisfying assignments of random ε-1-in-k SAT

Abstract

We study the geometric structure of the set of solutions of a random ε-1-in-k SAT problem [D. Achlioptas, A. Chtcherba, G. Istrate, and C. Moore, The phase transition in 1-in-K SAT and NAE3SAT, in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 721–722; A. Percus, G. Istrate, and C. Moore (eds.), Computational Complexity and Statistical Physics, Oxford University Press, Oxford, UK, 2006]. For l≥1, two satisfying assignments A and B are l-connected if there exists a sequence of satisfying assignments connecting them by changing at most l bits at a time.

We first identify a subregion of the satisfiable phase where the set of solutions provably forms one cluster. Next, we provide a range of parameters (c, ε) such that w.h.p. (with high probability) two assignments of a random ε-1-in-k SAT instance with n variables and cn clauses are O(log n)-connected, conditional on being satisfying assignments. Also, for random instances of 1-in-k SAT in the satisfiable phase we show that there exists ν _k ∈(0, 1/(k−2)] such that w.h.p. no two satisfying assignments at distance at least ν _k ·n form a ‘hole’. We believe that this is true for all ν _k >0, and in fact solutions of a random 1-in-k SAT instance in the satisfiable phase form one cluster.

Keywords:

• ε-1-in-k SAT
• overlaps
• random graphs
• phase transition

2000 AMS Subject Classifications :

• Primary 68Q25
• Secondary 82B27

ACM Classifications :

• F.2.2
• G.2

Acknowledgements

I thank Romeo Negrea for useful discussions. This work has been supported by a Marie Curie International Reintegration Grant within the 6th European Community Framework Programme, by a PN-II/‘Parteneriate’ grant from the Romanian CNCSIS and a grant from the Austrian Government.

Notes

In 15, the result is only stated and proved for k=3, but the method outlined there works for any k≥3.