Annals of Combinatorics 1 (1997) 245-252
On a Problem of Erdös and Rado
Jean A. Larson and William J. Mitchell
Department of Mathematics, University of Florida, Gainesville, FL 32611, USA
Received March 25, 1997
AMS Subject Classification: 05C55, 05C20, 03E10
Abstract. We give some improved estimates for the digraph Ramsey
numbers r(K*n, Lm),
the smallest number p such that any digraph of order p either
has an independent set of n vertices or contains a transitive tournament
of order m.
Keywords: digraph, Ramsey, partition, ordinal, graph, transitive tournament
1. J. Baumgartner, Improvement of a partition theorem of erdos and Hajnal, J. Combin. Theory Ser. A 17 (1974) 134–137.
2. J.-C. Bermond, Some Ramsey numbers for directed graphs, Discrete Math. 9 (1974), 313–321.
3. B. Dushnik and E.W. Miller, Partially ordered sets, Amer. J. Math. 63 605 (1941).
4. R.L. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, Addison-Wesley Publishing Co., New York, 1989.
5. R.L. Graham, B. Rothschild, and J. Spencer, Ramsey Theory, 2nd Ed., Wiley, New York, 1990.
6. P. ErdHos, A. Hajnal, A. Màtè, and R. Rado, Combinatorial Set Theory: Partition Relations for Cardinals, Akadèmiai Kiadò, Budapest and North-Holland, Amsterdam, New York/Oxford, 1984.
7. P. ErdHos and L. Moser, On the representation of a directed graph as unions of orderings, Publ. Math. Inst. Hungar. Acad. Sci. 9 (1964) 125–132.
8. P. ErdHos and R. Rado, A partition calculus in set theory, Bull. Amer. Math. Soc. 62 (1956) 427–489.
9. P. ErdHos and R. Rado, Partition relations and transitivity domains of binary relations, J. London Math. Soc. 42 (1967) 624–633.
10. F. Harary and P. Hell, Generalized Ramsey theory for graphs V: the Ramsey number of a digraph, Bull. London Math. Soc. 6 (1974) 175–182.
11. R. Laver, Partition relations for uncountable cardinals ≤ 2α0, In: Infinite and Finite Sets, (Keszthely, Hungary) Colloquia Mathematics Socitatis Janos Bolyai, Vol. 10, 1973, pp. 1029–1042.
12. F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. (2) 30 (1930) 364–286.
13. K.B. Reid and E.T. Parker, Disproof of a conjecture of ErdHos and Moser on tournaments, J. Combin. Theory 9 (1970) 225–238.
14. R. Stearns, The voting problem, Amer. Math. Monthly 66 (1959) 761–763.