Partially Symmetric Functions

Recall that the Hamming weight of a bit string is the number of 1's it has.

Consider the special class of *N*-bit Boolean functions *f* such that
*f* (*x*) = 1 for all inputs *x* of Hamming weight *a*, and *f* (*x*) = 0
for all inputs *x* of Hamming weight *b*. Without loss of generality
assume *a* < *b*. We will attain a lower bound depending only on the
parameters *a* and *b*.

Like Lemma 2.2.1, this result allows us to easily attain lower
bounds for many functions. In general, the closer *a* and *b* are to
each other and to *N*/2 the better. We illustrate the particular
success of Theorem 2.5.1 in the case of symmetric functions
in the following two sections, and with relatively less success in the
case of non-trivial monotone graph properties in Section
3.2.