Expander graphs play an important role in graph theory and computer science. Innumerable constructions of expander graphs have been found since the pioneering work by Margulis. However, for hypergraphs, no such construction is known.

In the talk we construct so-called ”expander relations” that even generalize hypergraphs. The construction uses a type of semidirect product (a generalization of the so-called zig zag product) of relational structures. Our approach is more algorithmic than the known graph expander constructions.

We will use these tools to derandomize Erdos’ classical random construction for graphs with large girth and chromatic number and also Nesetril and Rodl’s socalled girth machine. As a complexity theoretical application of this combinatorial result we show that the following two complexity classes are equivalent. One is the class of Constraint Satisfaction Problems (CSP for short). This class essentially contains hypergraph coloring problems. The class MMSNP (Monotone Monadic Strict NP) introduced by Feder and Vardi can also be defined in terms of colorings. A typical language in MMSNP is the language of loopless, undirected graphs which are 2-colorable without monochromatic triangles. Feder and Vardi proved that in a random sense these classes are equivalent. We derandomize this proof.