The pigeonhole property and orientations of the infinite random graph
by
Anthony Bonato
Wilfrid Laurier University, Waterloo, Canada
Coauthors: Dejan Delić (Vanderbilt University, Nashville, U.S.A.)

Infinite cliques and their complements have the property that when their vertices are coloured red or blue, then the subgraph induced by either the red or blue vertices is isomorphic to the original graph. We name this property (P). P. Cameron proved in 1996 that the only other nontrivial countable graph with (P) is the infinite random graph R. Together with Cameron, we recently classified the countable tournaments with (P) (there are uncountably many). The classification of the countable digraphs with (P) is open, and the problem reduces to considering orientations of a single graph: the infinite random graph!

At the 17th British Combinatorial Conference, Cameron asked if there are continuum many non-isomorphic, acyclic, topologically ordered orientations of R, none of which possess (P). If so, then apart from demonstrating how wild orientations of R may be, the existence of such orientations hint that the problem of finding all countable digraphs with (P) may be a difficult one.

In this talk we will describe a set of such orientations of R, thereby solving Cameron's problem in the affirmative.

Anthony Bonato's homepage

Date received: March 31, 2001