##
**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 A^{k} = **{**B | B \subseteq A, |B| = k **}**. A coloring of A is given by a map g_{k}: A^{k} ––> **{**+1,-1 **}**. For B \subseteq A, define g_{k}(B) = **sum** g_{k}(W), where the sum is taken over all subsets W of B for which |W| = k. Let H_{k}(n) = **max** **max** |g_{k}(B)|, where the maximum is taken over all subsets B of A and the minimum is taken over all functions g_{k}, defined above. The authors prove for k \geq 1 and n sufficiently large that H_{k}(n) is bounded below by C_{k} · n^{(k+1)/2} and bounded above by C'_{k} · n^{(k+1)/2}, where C_{k} 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