Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results:
We first show that by making small modifications to the nonzero coefficients of the degree-K, N-variate elementary symmetric polynomial \sigma_{N,K}, one obtains a polynomial that can be computed by a monotone formula of size K^{O(\log K)} \cdot N.
As a corollary, we show that a result of Raz [Raz13] concerning the homogenization of algebraic multilinear or monotone formulas is tight.
Another corollary is that the monotone bounded rigidity of the inclusion matrix between K-subsets and N-K subsets of a universe of size N is small.