John Truss (University of Leeds)

Countable homogeneous ordered bipartite graphs

Note: this seminar will take place in the MAGIC Room (10.03).

The classification of the countable homogeneous bipartite graphs is rather straightforward; they are empty or complete, perfect matching or its complement, and generic. Chernikov and Kruckmann asked what happens if a linear order is imposed on the structure. This is relevant (and required) in structural Ramsey theory: the Nesetril-Rodl Theorem requires the universe of the structure to be linearly ordered. I present a solution to this, which while not so very complicated, does require some tricks, and a rather longer list of structures. One would really like to address the same question for multipartite graphs. I shall briefly recall the classification of the countable homogeneous multipartite graphs (with a fixed finite number of parts), in joint work with Jenkinson and Seidel. The extension to linearly ordered multipartite graphs would require further work.