When does the giant component bring unsatisfiability? (Q1046740)

This is an important article about random constraint satisfaction problems. More precisely, a constraint satisfaction problem can be summarised by a set \({\mathcal D}=\{1,2,\dots d\}\) of possible values of the variables and a set of constraints of size \(k\), that is restrictions on the values of the \(k\)-tuple of variables \((x_{1},\dots x_{k})\). Here \(d\) and \(k\) are fixed positive integers. A more combinatorial way of saying the same thing is to have a constraint hypergraph, a \(k\)-uniform hypergraph whose vertices are variables and hyperedges are \(k\)-tuples of variables which have constraints. In that formulation, we can easily develop a random model. Specify \(n\) the total number of variables, \(M\) (typically \(M=cn\)) the number of hyperedges, and say that all \(k\)-uniform hypergraphs with \(n\) vertices and \(M\) edges are equally likely to be selected. Then a constraint is obtained by taking a random permutation from \(\{1,2,\dots n\}\) to \(\{X_{1},\dots X_{k}\}\) (a set of canonical variables describing the pattern) and then a random constraint is chosen according to some probabilty distribution \({\mathcal P}\) on the set of all \(2^{d^{k}}\) possible constraints over the \(k\) canonical variables (and lifted back to the original variables). We call this model \({\text{CSP}}_{n,M}({\mathcal P})\). The main result of this paper is for the case \(k=2\) (i.e., a constraint graph rather than hypergraph). It is difficult to state, we merely try to convey the idea. We focus on those \({\mathcal P}\) such that the support of \({\mathcal P}\), \({\text{supp}}({\mathcal P})\), is `very well-behaved': this means it satisfies three technically desirable properties. The author had earlier shown, using the theory of random graphs, that then, for every \(0<c<1/2\) \({\text{CSP}}_{n,M=cn}({\mathcal P})\) is satisfiable with probability tending to 1 as \(n\rightarrow\infty\) (hereafter `a.s. satisfiable\'), and for some \(c>1/2\) it is a.s. not satisfiable. However this is rather unsatisfactory since we would like to determine more precisely which distributions keep \({\text{CSP}}({\mathcal P})\) a.s. satisfiable. Theorem 2 of the paper determines exactly which \({\mathcal P}\) are such that \({\text{CSP}}({\mathcal P})\) remains a.s. satisfiable when \(C\) increases beyond the point where the constraint graph a.s. has a giant (linear in its number of vertices) component. In detail, if \({\text{supp}}({\mathcal P})\) has a very well-behaved component, then there is \(\epsilon>0\) such that for every \(c\leq 1/2+\epsilon\) \({\text{CSP}}_{n,M=cn}\) is a.s. satisfiable. If instead every component of \({\text{supp}}({\mathcal P})\) satisfies some technical conditions -- namely, that those with at least one `good value\'\, are `subpermutation sets\'\, then for every \(c>1/2\) \({\text{CSP}}_{n,M=cn}({\mathcal P})\) is a.s. unsatisfiable: that is, the probabilty of satisfiability drops abruptly from (close to) 1 to (close to) 0. In all other cases, the result implies that there is an \(\epsilon>0\) such that for \(1/2<c<1/2+\epsilon\) \({\text{CSP}}+_{n,M=cn}{\mathcal P}\) is neither a.s. satisfiable nor a.s. unsatisfiable. It is possible to find examples of choice of \({\text{supp}}({\mathcal P})\) for which all three possibilities arise, though the second case of abrupt jump is harder to find. Most of the work is in fact in dealing with the case that \({\text{supp}}({\mathcal P})\) is connected, which depends on arguments involving so-called `semi-null constraint paths'. Another key notion in the arguments is what are called `expanded permutations'. These important results leave open various follow up questions about when thresholds (when they exist) are sharp. This seems a very hard question -- the corresponding question for random 3-SAT is not known (in the stronger of the two senses of having a sharp threshold) and evidence is given that the problem is difficult in various other ways too. Other important questions include which models from this family exhibit high resolution complexity and which have continuous or discontinuous phase transitions.