A lower bound for Ramsey's theorem

✍ Scribed by Joram Hirschfeld

• Publisher: Elsevier Science
• Year: 1980
• Tongue: English
• Weight: 291 KB
• Volume: 32
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(80)90104-1

✦ Synopsis

For every integer tz we denote by n the set {O, 1, . . . , n -1). We denote by En]" the collection of subsets of with exactly k elements. We call the elements of [n]" k-tuples and write thein dlown as (a,, . . . , a,) in the natural order: a, < a, c l . l < ak < n. A colouting 04 [nlk by r colours is a map C:[nlk ---* (0,. . . , r-1). For every k-tuple u we call C(u) the colour of u. A subset A of n is holnogetzeous for a given colouring if all the k-tuples of A are coloured by the same colour. With this notation we have Ramsey's Theorem. For eruery I, k and r there is some n which is denoted by R(k, 1, r) such that every colouring of [nlk by r colours has homogeneous subset of n with I elements.