Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 248.05114
Autor: Erdös, Paul; Spencer, Joel
Title: Imbalances in k-colorations. (In English)
Source: Networks 1, 379-385 (1972).
Review: For the set A = {1,2, ... ,n }, let Ak = {B | B \subseteq A, |B| = k }. A coloring of A is given by a map gk: Ak ––> {+1,-1 }. For B \subseteq A, define gk(B) = sum gk(W), where the sum is taken over all subsets W of B for which |W| = k. Let Hk(n) = max max |gk(B)|, where the maximum is taken over all subsets B of A and the minimum is taken over all functions gk, defined above. The authors prove for k \geq 1 and n sufficiently large that Hk(n) is bounded below by Ck · n(k+1)/2 and bounded above by C'k · n(k+1)/2, where Ck and C'k are positive absolute constants.
Reviewer: G.Chartrand
Classif.: * 05C15 Chromatic theory of graphs and maps
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag