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