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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page