Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Partitions and orientations of the Rado graph


Authors: Reinhard Diestel, Imre Leader, Alex Scott and Stéphan Thomassé
Journal: Trans. Amer. Math. Soc. 359 (2007), 2395-2405
MSC (2000): Primary 05C20
DOI: https://doi.org/10.1090/S0002-9947-06-04086-4
Published electronically: November 22, 2006
MathSciNet review: 2276626
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)

  • 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)

Similar Articles

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

Retrieve articles in all journals with MSC (2000): 05C20


Additional Information

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

Stéphan Thomassé
Affiliation: LIRMM, 161 rue Ada, 34392 Montpellier Cedex 5, France

DOI: https://doi.org/10.1090/S0002-9947-06-04086-4
Received by editor(s): December 17, 2003
Received by editor(s) in revised form: May 31, 2005
Published electronically: November 22, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society