Abstract

Let $\Gamma$ be the random bipartite graph, a countable graph with two infinite sides, edges randomly distributed between the sides, but no edges within a side. In this paper, we investigate the reducts of $\Gamma$ that preserve sides. We classify the closed permutation subgroups containing the group $\operatorname {Aut}(\Gamma)^{\ast}$ , where $\operatorname {Aut}(\Gamma)^{\ast}$ is the group of all isomorphisms and anti-isomorphisms of $\Gamma$ preserving the two sides. Our results rely on a combinatorial theorem of Nešetřil and Rödl and a strong finite submodel property for $\Gamma$