Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.