On random betweenness constraints

Ordering constraints are analogous to instances of the satisfiability problem in conjunctive normalform, but instead of a boolean assignment we consider a linear ordering of the variables in question. A clause becomes true given a linear ordering iff the relative ordering of its variables obeys the constraint considered. The naturally arising satisfiability problems are NP-complete formany types of constraints. We look at random ordering constraints. Previous work of the author shows that there is a sharp unsatisfiability threshold for certain types of constraints. The value of the threshold however is essentially undetermined. We pursue the problem to approximate the precise value of the threshold. We show that random instances of the betweenness constraint (definition see Subsection 1.1) are satisfiable with high probability iff the number of randomly picked clauses is < 0.9 ċ n, where n is the number of variables considered. This improves the previous bound which is < 0.82 ċ n random clauses.