Partitia multimii submultimilor proprii ale lui {1,2,...,n}

[Mircea Cimpoeas]

Fie \( P_n \) multimea tuturor submultimilor proprii ale multimii \( \{1,2,\ldots,n\} \). Daca \( A\subset B\in P_n \), notez \( [A,B]=\{C\in P_n|A\subset C\subset B\} \). O partitie a lui \( P_n \) inseamna sa scriem \( P_n=\bigcup_{i=1}^r [C_i,D_i], \), unde \( C_i,D_i\in P_n \) si \( [C_i,D_i]\cap[C_j,D_j]=\emptyset \) pentru orice \( i\neq j \).
Sa se arate ca exista o partitie a lui \( P_n \) cu \( |D_i|\geq \left\lceil \frac{n}{2} \right\rceil \) pentru orice \( i \).

(Se defineste \( \left\lceil \frac{n}{2} \right\rceil = \frac{n}{2} \) daca e n este par si \( \left\lceil \frac{n}{2} \right\rceil = \frac{n+1}{2} \) daca n e impar.)

Exemplu: \( n=3 \). \( P_3=\{ \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \}. \)

\( P_3 = [\{1\},\{1,2\}]\cup [\{2\},\{2,3\}]\cup [\{3\},\{1,3\}]\cup [\{1,2,3\},\{1,2,3\}]. \)

[Mircea Cimpoeas]

Am aflat la ultimul seminar de algebra ca aceasta problema a fost rezolvata de curand de catre niste combinatoristi americani. Problema a aparut mentionata intr-un articol recent al lui J. Herzog, M. Vladoiu, X. Zheng, intitulat "How to compute the Stanley depth of a monomial ideal". In acel articol, problema a fost rezolvata pentru \( n\leq 9 \). Ca o consecinta imediata, se obtine \( sdepth((x_1,\ldots,x_n)) = \left\lceil \frac{n}{2} \right\rceil \). Pentru detalii, consultati articolul lui J. Herzog, M. Vladoiu, X. Zheng, pe care il puteti gasi aici: http://arxiv.org/pdf/0712.2308