Reducts of the random bipartite graph

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 $Aut(\Gamma {)}^{\ast }$, where $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-Rödl and a strong finite submodel property for $\Gamma$.