On an open problem related to the strict local minima ofmultilinear objective functions

This paper gives a combinatorial proof of a “yes” answer to an open question presented by Vidyasagar (ibid. vol.40, 1995), stated as follows: “Given a multilinear polynomial E(x): [0, 1] ⁿ→ℛ, is it true that E_b(x)=E(x)-b^t x has a strict local minimum over the discrete set {0, 1}ⁿ for almost all b of sufficiently small norm?” The given combinatorial proof is completed directly by providing a sufficient condition for a conjecture on the strict local minima of multilinear polynomials, also postulated in Vidyasagar, to hold. In addition, a simple counter-example is presented to demonstrate that the conjecture may be not true if the provided sufficient condition is not satisfied