The Horn renamability, q-Horn and SLUR threshold for random kk-CNF formulas

We establish that a random kk-CNF formula with mm clauses having kk literals each, over a set of nn variables, is asymptotically almost surely renamable-Horn if m/n<2/(k(k−1))m/n<2/(k(k−1)). This lower bound on Horn non-renamability coincides with the upper bound established by Franco and Van Gelder in 2003 for a random kk-CNF formula to be q-Horn (Boros et al., 1994) or SLUR (Schlipf et al., 1995). Put together, these two results imply that the renamable-Horn, q-Horn and SLUR properties for random kk-CNFs share a common sharp threshold at 2/(k(k−1))2/(k(k−1)). An immediate consequence is that the number of kk-CNF formulas which are q-Horn or SLUR, but not renamable-Horn, is asymptotically negligible as n→∞n→∞.