Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 577.05007
Autor: Brown, T.C.; Erdös, Paul; Chung, F.R.K.; Graham, Ronald L.
Title: Quantitative forms of a theorem of Hilbert. (In English)
Source: J. Comb. Theory, Ser. A 38, 210-216 (1985).
Review: For positive integers m, a and ak, 1 \leq k \leq m define an m-cube Qm to be the set {a+summk = 1\epsilonkak: \epsilonk = 0 or 1, 1 \leq k \leq m}. Hilbert proved that for any positive integers m and r there exists a least integer h(m,r) such that if the set { 1,2,...,h(m,r)} is arbitrarily partitioned into r classes Ck, 1 \leq k \leq r, some Ci must contain an m cube. Schur proved that for any r, there is an s(r) so that in any partition of { 1,2,...,s(r)} into r classes some class contains a projective 2- cube Q^*2(a,a1,a2)-{0} with a = 0. This was extended by Rado for projective m-cubes and further extended by Hindman to infinite projective cubes i.e. for {sumook = 1\epsilonkak: \epsilonk = 0 or 1 with 0 \leq sumook = 1\epsilonk < oo}.
In this article the authors have investigated the function h(m,r) and several related ones. For the first interesting case m = 2 it is proved that H(2,r) = (1+0(1))r2. This result is closely related to Ramsey numbers for 4-cycles. Bounds are also obtained for deleted 2-cubes.
Reviewer: M.Cheema
Classif.: * 05A17 Partitions of integres (combinatorics)
05C55 Generalized Ramsey theory
Keywords: deleted m-cube; m-cube; projective m-cubes; Ramsey numbers for 4-cycles
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag