  We give a poly-time construction for a combinatorial classic known as Sparse
Incomparability Lemma, studied by Erdos, Lovasz, Nesetril, Rodl and others: We
show that every Constraint Satisfaction Problem is poly-time equivalent to its
restriction to structures with large girth. This implies that the complexity
classes CSP and Monotone Monadic Strict NP introduced by Feder and Vardi are
computationally equivalent. The technical novelty of the paper is a concept of
expander relations and a new type of product for relational structures: a
generalization of the zig-zag product, the twisted product.

Combinatorics