Lower Bound on the Volume of Certain Polytopes

2011-03-26T04:08:59Z

Given a partition $\rho\in\mathcal{P}(n)$ with $k$ blocks $$ \rho=\{B_1,B_2,\ldots,B_{k}\} $$ we can define the set of equations $$ E_{i}:\sum_{j \in B_{i}}{x_{j-1}}=\sum_{j \in B_{i}}{x_j}\quad\text{with}\quad i\in\{1,2,\ldots,k\} $$ where $0\leq x_j\leq 1$ for $j=1,2,\ldots,n$.

The solution to these equations has $n+1-k$ free variables. We define $K_{\rho}$ as $$ K_{\rho}=\text{volume of the solution set in $[0,1]^{n+1-k}$}. $$

For instance, for the partition $\rho=\{\{1,3\},\{2,4\}\}$ the equations are $E_1=E_2: x_{1}+x_{3}=x_{2}+x_{4}$.

Hence, $$ K_{\rho}=\mathrm{vol} \{(x_1,x_2,x_3)\in [0,1]^3: 0\leq x_1+x_3-x_2\leq 1\}=\frac{2}{3}. $$

It can be proved that these convex polytopes have volume in $(0,1]$ and that the volume is 1 iff the partition is non-crossing. These polytopes are important for random matrix theory (moments of random Toeplitz matrices [Dembo et all], random Vandermonde matrices, etc) and combinatorics (related with the Eulerian numbers).

My question: is it possible to get a lower bound for $K_{\rho}$ in terms of $n$ and the number of blocks $k$?

Update: I have the conjecture that for every $\rho\in\mathcal{P}(n)$ with $k$ blocks $$ K_{\rho}\geq \Bigg[\frac{6(k-1)}{\pi n}\Bigg]^{\frac{k-1}{2}} $$ and I proved it for $k=2$ and $k=3$ and arbitrary $n$.

Lower Bound on the Volume of Certain Polytopes - MathOverflow

Lower Bound on the Volume of Certain Polytopes