Hyperplane Arrangements with Large Average Diameter

Abstract

<p> This thesis deals with combinatorial properties of hyperplane arrangements. In particular, we address a conjecture of Deza, Terlaky and Zinchenko stating that the largest possible average diameter of a bounded cell of a simple hyperplane arrangement is not greater than the dimension. We prove that this conjecture is asymptotically tight in fixed dimension by constructing a family of hyperplane arrangements containing mostly cubical cells. The relationship with a result of Dedieu, Malajovich and Shub, the conjecture of Hirsch, and a result of Haimovich are presented.</p> <p> We give the exact value of the largest possible average diameter for all simple arrangements in dimension two, for arrangements having at most the dimension plus two hyperplanes, and for arrangements having six hyperplanes in dimension three. In dimension three, we strengthen the lower and upper bounds for the largest possible average diameter of a bounded cell of a simple hyperplane arrangements.</p> <p> Namely, let ΔA(n, d) denote the largest possible average diameter of a bounded cell of a simple arrangement defined by n hyperplanes in dimension d. We show that

• ΔA(n, 2) = 2[n/2] / (n-1)(n-2) for n ≥ 3, • ΔA(d + 2, d) = 2d/d+1, • ΔA(6, 3) = 2, • 3 - 6/n-1 + 6([n/2]-2) / (n-1)(n-2)(n-3) ≤ ΔA(n, 3) ≤ 3 + 4(2n^2-16n+21) / 3(n-1)(n-2)(n-3) • ΔA (n, d) ≥ 1 + (d-1)(n-d d)+(n-d)(n-d-1) for n ≥ 2d. We also address another conjecture of Deza, Terlaky and Zinchenko stating that the minimum number Φ0A~(n, d) of facets belonging to exactly one bounded cell of a simple arrangement defined by n hyperplanes in dimension d is at least d (n-2 d-1). We show that • Φ0A(n, 2) = 2(n - 1) for n ≥ 4, • Φ0A~(n, 3) ≥ n(n-2)/3 +2 for n ≥ 5. We present theoretical frameworks, including oriented matroids, and computational tools to check by complete enumeration the open conjectures for small instances. Preliminary computational results are given.</p>