A combinatorial problem involving monomial ideals (Q1903707): Difference between revisions

For an integer \(d\) define \(S(d)\) to be the set of all triples \((e_1, e_2, e_3)\in \mathbb{N}^3\) such that \(e_1+e_2+e_3=d\). If \(d\geq 1\), this set clearly can be covered by (i.e. written as the union of) 3-element sets \((e_1, e_2, e_3)+\{(1, 0, 0), (0, 1, 0), (0, 0, 1)\}\) originated by triples \((e_1, e_2, e_3)\in S(d- 1)\). Define \(\rho_3 (d)\) to be the minimal number of such sets needed to cover \(S(d)\). Theorem. \(\rho_3 (1)=1\), \(\rho_3 (2)=3\), \(\rho_3 (8)=18\), and, for \(d\neq 1, 2, 8\), \(\rho_3 (d)=\lfloor {1\over 3} {{d+4} \choose 2} \rfloor-3\). Via an obvious isomorphism the main theorem answers for \(n=3\) a question of \textit{A. V. Geramita}, \textit{D. Gregory} and \textit{L. Roberts} [J. Pure Appl. Algebra 40, 33-62 (1986; Zbl 0586.13015) and Rend. Semin. Mat., Torino 42, No. 2, 1-10 (1984; Zbl 0584.14001)] asking for the smallest number of monic monomials of degree \(d-1\) in \(k[ x_1, \dots, x_n]\) such that the ideal they generate contains all monomials of degree \(d\). The theorem is established by hard elementary combinatorial analysis (many case distinctions, etc.) yielding for all \(d\geq 12\) the estimate \(\rho_3 (d)\geq \rho_3 (d-3)+d+2\). The converse estimate then, following easily from the papers by \textit{A. V. Geramita}, \textit{D. Gregory} and \textit{L. Roberts} cited above, leads to a recursion with above solution. Reviewer's remarks: (a) The result reminds of essentially polynomial solutions to other enumerative problems involving \(S(d)\). The elegant ways in which these can be obtained -- see, e.g., in \textit{R. P. Stanley}'s book ``Enumerative combinatorics. I'' (Monterey 1986; Zbl 0608.05001) exc. 6, ch. 4 -- seem, however, inadaptable. (b) Be aware of possible typoes: e.g., line 5 of the proof of lemma 2.1 should begin with: \dots thus \((0, e_2+1, e_3+1)\not\in \dots\;\).