Lower Bound on the Volume of Certain Polytopes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T18:14:58Z http://mathoverflow.net/feeds/question/59634 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59634/lower-bound-on-the-volume-of-certain-polytopes Lower Bound on the Volume of Certain Polytopes ght 2011-03-26T04:08:59Z 2011-04-04T19:53:19Z <p>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$.</p> <p>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}}.$$</p> <p>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}$.</p> <p>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}.$$</p> <p>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).</p> <blockquote> <p>My question: is it possible to get a lower bound for $K_{\rho}$ in terms of $n$ and the number of blocks $k$?</p> </blockquote> <p><strong>Update:</strong> 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$.</p>