The Abstract

	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 {jal; mitchell}@math.ufl.edu Received March 25, 1997 AMS Subject Classification: 05C55, 05C20, 03E10 Abstract. We give some improved estimates for the digraph Ramsey numbers r(K^_n, L_m), 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. By results of Baumgartner and of Erdös and Rado, this is equivalent to the following infinite partition problem: for an infinite cardinal k and positive integers n and m, find the smallest number p such that k × p → (k × n, m)², that is, find the smallest number p so that any graph whose vertices are well ordered where order type k × p either has an independent subset of order type k × n or a complete subgraph of size m. Keywords: digraph, Ramsey, partition, ordinal, graph, transitive tournament References* 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. Get the LaTex \| DVI \| PS file of this abstract. back

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
{jal; mitchell}@math.ufl.edu

Received March 25, 1997

AMS Subject Classification: 05C55, 05C20, 03E10

Abstract. We give some improved estimates for the digraph Ramsey numbers r(K^*_n, L_m), 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.
By results of Baumgartner and of Erdös and Rado, this is equivalent to the following infinite partition problem: for an infinite cardinal k and positive integers n and m, find the smallest number p such that

k × p → (k × n, m)², that is, find the smallest number p so that any graph whose vertices are well ordered where order type k × p either has an independent subset of order type k × n or a complete subgraph of size m.

Keywords: digraph, Ramsey, partition, ordinal, graph, transitive tournament

References

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.

Get the LaTex | DVI | PS file of this abstract.

back