On the sum of squares of cell complexities in hyperplane arrangements
For an arrangement \(A\) of \(n\) hyperplanes in \(\mathbb{R}^ d\) \((d \geq 2)\), let \(f_ i (c)\) denote the number of \(i\)-dimensional faces of a cell \(c\) of \(A\), and let \(f(c) = \sum^{d-1}_{i = 0} f_ i(c)\) be the complexity of the cell \(c\). The authors prove that \[ \sum_ c f(c)^ 2 = O \Bigl( n^ d \log^{\lfloor {d \over 2} \rfloor - 1}n \Bigr), \tag{*} \] where the sum extends over all cells of \(A\), and the constant of proportionality depends on \(d\). Moreover, it is shown that the total number of faces, bounding any \(m\) distinct cells of \(A\), is \(O(m^{{1 \over 2}} n^{{1 \over 2}} \log^{(\lfloor {1 \over 2} \rfloor - 1) \cdot {1 \over 2}} n)\), and several further applications regarding face count are added. Finally, in view of \((*)\) the authors conjecture that the correct bound is \(\Theta (n^ d)\).
scientific article; zbMATH DE number 554404