A NOTE ON ORIENTATIONS OF THE INFINITE RANDOM GRAPH

Abstract. We answer a question of P. Cameron’s by giving ex-amples of 2ℵ0 many non-isomorphic acyclic orientations of the in-finite random graph with a topological ordering that do not have the pigeonhole property. Our examples also embed each countable linear ordering. A graph is n-existentially closed or n-e.c. if for each n-subset S of vertices, and each subset T of S (possibly empty), there is a vertex not in S, joined to each vertex of T and no vertex of S\T. The infinite random graph, written R, is the unique (up to isomorphism) countable graph that is n-e.c. for all n ≥ 1. For more on the infinite random graph, the reader is directed to [2, 3]. The infinite random graph is intimately related to a certain vertex partition property. A graph G has the pigeonhole property, written (P), if for every partition of the vertices of G into two nonempty parts, the subgraph induced by some one of the parts is isomorphic to G. This property was introduced by P. Cameron in [2], who in [3] classified the countable graphs with (P); there are only four up to isomorphism: the graph with one vertex, the countably infinite clique and its com-plement, and R. In particular, R is the unique countable 1-e.c. graph that has (P). The pigeonhole property may be easily generalized to any relational structure. The countable tournaments with (P) were classified in [1]; there are ℵ1 many: the countable ordinal powers of ω and their reversals, and the countably infinite random tournament. A problem of [1] that has resisted solution is the following. Problem 1: Classify the countable oriented graphs with (P). As proved in [1], a countable oriented graph with (P) that is neither a tournament nor the infinite random oriented graph O, must be an orientation of R. Cameron [4] was the first to notice that any suc