ON THE SUM OF SQUARES OF CELL COMPLEXITIES IN HYPERPLANE ARRANGEMENTS

Let H be a collection of n hyperplanes in R(d), d greater-than-or-equal-to 2. For each cell c of the arrangement of H let f(i)(c) denote the number of faces of c of dimension i, and let f(c) = SIGMA(i = 0)d-1 f(i)(c). We prove that SIGMA(c) f(c)2 = O(n(d) log right perpendicular d/2 left perpendicular - 1 n), where the sum extends over all cells of the arrangement. Among other applications, we show that the total number of faces bounding any m distinct cells in an arrangement of n hyperplanes in R(d) is O(m1/2nd/2 log (right perpendicular d/2 left perpendicular - 1)/2n) and provide a lower bound on the maximum possible face count in m distinct cells, which is close to the upper bound, and for many values of m and n is OMEGA(m1/2n(d/2). (C) 1994 Academic Press, Inc.