On a generalization of Ramsey numbers

✍ Scribed by Paul Erdös; Patrik E. O'neil

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 685 KB
• Volume: 4
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(73)90112-x

✦ Synopsis

Given the integers I,

,

k,

,

I,

,

k,

,

r

, which satisfy the condition I,, I, >r> k,, k, > 0, we define m = N(Z,, k,;l,, k,;r) as the smallest integer with the following property: ifS is a set containing IS? points and the r-subsets of S are partitioned arbitrarily into two class~:s, then for i = 1 or 2 there exists an li subset of !I' each of whtist: ki-subsets lies in some r-subset of the ith class. The integers defined in this waq. form a coilection of which the usual Ramsey numbers are a special case: i.e., the Ramsey number N(Ii, Z,;r) is represented as N(I, , r;f 2, r; r). We derive two major results concerning the values of these generalized Ramsey numbers. If k, + k, = r + 1 then N( I,,k,;l,,k,;r) = I,+ 2,,+ 1, corresponding to the "pigeonhole principle". For k, +k, 5 r, we show that N(Z,, k,; I,, k,; r) = max (I,, I,). The next interesting case occurs for k, + k, = r + 2, where we show that there are constants c, and c2 such that for sufficiently large I, 2'1'< N(2, k,; 2, k,; r) < 2'2'.