##
**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