Transactions of the American Mathematical Society

Author(s): Reinhard Diestel; Imre Leader; Alex Scott; Stéphan Thomassé
Journal: Trans. Amer. Math. Soc. 359 (2007), 2395-2405.
MSC (2000): Primary 05C20
Posted: November 22, 2006
Retrieve article in: PDF DVI PostScript

Abstract: We classify the countably infinite oriented graphs which, for every partition of their vertex set into two parts, induce an isomorphic copy of themselves on at least one of the parts. These graphs are the edgeless graph, the random tournament, the transitive tournaments of order type $\omega^\alpha$ , and two orientations of the Rado graph: the random oriented graph, and a newly found random acyclic oriented graph.

1.: A. Bonato, P.J. Cameron and D. Delic, Tournaments and orders with the pigeonhole property, Canad. Math. Bull. 43 (2000), 397-405. MR 1793941 (2001h:05044)
2.: A. Bonato, P.J. Cameron, D. Delic and S. Thomassé, Generalized pigeonhole properties of graphs and oriented graphs, European J. Combin. 23 (2002), 257-274. MR 1908649 (2003c:05099)
3.: A. Bonato and D. Delic, A note on orientations of the infinite random graphs, European J. Combin. 25 (2004), 921-926. MR 2083445 (2006a:05149)
4.: P.J. Cameron, Aspects of the random graph, Graph Theory and Combinatorics (Cambridge, 1983), 65-79, Academic Press, London, 1984. MR 0777165 (86j:05126)
5.: P.J. Cameron, Oligomorphic Permutation Groups, Cambridge University Press, Cambridge, 1990. MR 1066691 (92f:20002)
6.: P. Erdos, A. Hajnal and L. Pósa, Strong embeddings of graphs into colored graphs, in Infinite and Finite Sets (Colloq., Keszthely, 1973), Colloq. Math. Soc. Janos Bolyai 10 (1975), pp. 585-595. MR 0382049 (52:2937)
7.: R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331-340. MR 0172268 (30:2488)

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05C20

Reinhard Diestel
Affiliation: Mathematisches Seminar, Universität Hamburg, Bundesstraße 55, 20146 Hamburg, Germany

Imre Leader
Affiliation: DPMMS/CMS, University of Cambridge, Wilberforce Road, GB -- Cambridge CB3 0WB, England

Alex Scott
Affiliation: Mathematical Institute, 24-29 St. Giles', Oxford, OX1 3LB, England

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS