## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  655.05059
Autor:  Erdös, Paul; Goldberg, Mark; Pach, János; Spencer, Joel
Title:  Cutting a graph into two dissimilar halves. (In English)
Source:  J. Graph Theory 12, No.1, 121-131 (1988).
Review:  Given a graph G and a subset S of the vertex set of G, the discrepancy of S is defined as the difference between the actual and expected numbers of the edges in the subgraph induced on S. We show that for every graph with n verticesand e edges, u < e < n(n-1)/4, there is an n/2-element subset with the discrepancy of the order of magnitude of \sqrt{n}. For graphs with fewer than n edges, we calculate the asymptotics for the maximum guaranteed discrepancy of an n/2-element subset. We also introduce a new notion called bipartite discrepancy'' and discuss related results and open problems.
Classif.:  * 05C99 Graph theory
Keywords:  discrepancy; numbers of the edges

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag