Average diameter of a bounded cell of a simple arrangement

Importance: Medium ✭✭
Subject: Geometry
Recomm. for undergrads: no
Posted by: deza
on: September 30th, 2007

\begin{conjecture} The average diameter of a bounded cell of a simple arrangement defined by $n$ hyperplanes in dimension $d$ is not greater than $d$. \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Let $\mathcal{A}$ be a simple arrangement formed by $n$ hyperplanes in dimension $d$. The number of bounded cells of $\mathcal{A}$ is $I={n-1\choose d}$. Let $\delta(\mathcal{A})$ denote the average diameter of a bounded cell $P_i$ of $\mathcal{A}$; that is, $$ \delta(\mathcal{A})=\frac{\sum_{i=1}^{i=I}\delta(P_i)}{I}. $$ Let $\Delta_{\mathcal{A}}({d,n})$ denote the largest possible average diameter of a bounded cell of a simple arrangement defined by $n$ inequalities in dimension $d$.

We have [DTZ,DX]:

If the conjecture of Hirsch holds, then $\Delta_{\mathcal{A}}(d,n)\leq d+\frac{2d}{n-1}$.

$\Delta_{\mathcal{A}}({2,n})=2-\frac{2\lceil\frac{n}{2}\rceil}{(n-1)(n-2)}$ for $n\geq 4$.

$3-\frac{6}{n-1}+\frac{6(\lfloor\frac{n}{2}\rfloor-2)}{(n-1)(n-2)(n-3)}\leq \Delta_{{\mathcal A}}(3,n)\leq 3 + \frac{4(2n^2-16n+21)}{3(n-1)(n-2)(n-3)}$ for $n\geq 5$.

$\Delta_{{\mathcal A}}(d,n)\geq d{n-d \choose d}/{n-1 \choose d}$ for $n\geq 2d$.

% The conjecture can be regarded a discrete analogue of a result of % Dedieu, Malajovich and Shub [DMS] on the average total curvature % of the central path associated to a bounded cell of a simple arrangement.

% Haimovich's probabilistic analysis of the shadow-vertex simplex algorithm, see Section 0.7 % [B], showed that the expected number of pivots is bounded by $d$. % Note that while Dedieu, Malajovich and Shub consider only the bounded % cells (the central path may not be defined over some unbounded ones), % Haimovich considers the average over bounded and unbounded cells. % While the result of Haimovich and Conjecture~\ref{dShub} are similar % in nature, they differ in some aspects: % Conjecture~\ref{dShub} considers the average over bounded cells, and % the number of pivots could be smaller than the diameter for some cells.

Bibliography

% [B] K. H. Borgwardt: The Simplex Method -- A Probabilistic Analysis. Springer-Verlag (1987).

% [D] G. B. Dantzig: Linear Programming and Extensions. Princeton University Press (1963).

% [DMS] J.-P. Dedieu, G. Malajovich and M. Shub: On the curvature of the central path of linear programming % theory. Foundations of Computational Mathematics. 5 (2005) 145--171.

*[DTZ] A. Deza, T. Terlaky and Y. Zinchenko: Polytopes and arrangements : diameter and curvature. Operations Research Letters (to appear).

[DX] A. Deza and F. Xie: Hyperplane arrangements with large average diameter. Centre de Recherches Mathematiques and American Mathematical Society series (to appear).


* indicates original appearance(s) of problem.