Probabilistic threshold conjecture for kk-SAT games

Let Cn(k)\mathcal{C}_n^{(k)} be the kk-uniform clause set on nn Boolean variables, and let FSAT\mathcal{F}_{SAT} be the family of satisfiable clause sets. Consider the (1:q)(1:q) Waiter–Client and Client–Waiter kk-SAT games, and denote their threshold biases by bFSATWCb_{\mathcal{F}_{SAT}}^{WC} and bFSATCWb_{\mathcal{F}_{SAT}}^{CW}, respectively.

kk-SAT threshold conjecture. The threshold biases satisfy

limk{limn1n(nk)(bFSATWC)1ln2}=limk{limn1n(nk)(bFSATCW)1ln2}=1.\lim_{k\rightarrow\infty}\left\{\lim_{n\rightarrow\infty}\frac{1}{n}\binom{n}{k}\frac{(b_{\mathcal{F}_{SAT}}^{WC})^{-1}}{\ln 2}\right\}=\lim_{k\rightarrow\infty}\left\{\lim_{n\rightarrow\infty}\frac{1}{n}\binom{n}{k}\frac{(b_{\mathcal{F}_{SAT}}^{CW})^{-1}}{\ln 2}\right\}=1.

The conjecture predicts the probabilistically suggested asymptotic threshold for both game orientations. The paper proves the threshold only up to exponential and polynomial factors in kk for the Waiter–Client and Client–Waiter versions, respectively, so the exact asymptotic remains open.

Sources & referencesView supporting material

Primary source

Wei En Tan, “Waiter-Client and Client-Waiter colourability games on a k-uniform hypergraph and the k-SAT game”, arXiv:1607.02258 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.