On Random Betweenness Constraints
Andreas Goerdt
Abstract
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 for many
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.9n, where n is the number of variables considered. This
improves the previous bound which is < 0.82n random clauses.
Key words: Algorithms, logic, random structures, probabilistic analysis.