### Corrected proof of Lemma 16.26

In the proof we have set all variables outside the matching to $0$. This is, however, not
sufficient: we must consider *all* possible settings. Below is a detailed proof.
Fix an arbitrary balanced partition of the vertices of $G$ into two
parts. The partition corresponds to a partition $(x,y)$ of
the variables of $f_G$. Let $r=r_1(x)\land r_2(y)$
be an arbitrary rectangle function
with respect to this partition, and suppose that $r\leq f$.
Our goal is to show that $r$ can accept at most $2^{n-m(G)}$ vectors.
By the definition of $m(G)$, some set
$M=\{x_1y_1,\ldots,x_my_m\}$ of $m= m(G)$ crossing edges
$x_iy_i$ forms an induced
matching of $G$. We first show that every assignment of constants $0$ and $1$
to the vertices outside $M$ transforms the function $f_G$ to a ``shifted''
version of the inner product function
\[
IP_m(x,y)=\sum_{i=1}^m x_iy_i \mod{2}.
\]
Then we use Lindsey's Lemma implying that the Hadamard matrix $H$
with entries $H[x,y]=(-1)^{IP_m(x,y)}$ cannot have a monochomatic
submatrix with more than $2^m$ entries. This will imply that $|f^{-1}(1)|\leq 2^{n-m}$.

Given an assignment $\alpha$ of constants $0$ and $1$ to the variables
outside the matching $M$, define
vectors $a,b\in \{0,1\}^m$ as follows: let $a_i=1$ iff
an odd number of neighbors of $x_i$ get value $1$,
$b_i=1$ iff an odd number of neighbors of $y_i$ get value $1$.
Also, let $c\in\{0,1\}$ be a constant defined by:
$c=1$ iff the number of edges whose
both endpoints get value $1$ under $\alpha$ is odd. Then the subfunction
$f(x,y)=f_{\alpha}(x,y)$ of $f_G$
obtained after restriction $\alpha$ is
\begin{align*}
f(x,y)&=\sum_{i=1}^mx_iy_i + \sum_{i=1}^mx_ia_i + \sum_{i=1}^m b_iy_i + c \mod{2}\\
&=IP_m(x\oplus b,y\oplus a)\oplus IP_m(a,b)\oplus c
\end{align*}
Since $a,b$ and $c$ are *fixed*, the corresponding $2^m\times 2^m$
$\pm 1$ matrix $H$ with entries $H[x,y]=(-1)^{f(x,y)}$ is a Hadamard matrix.
Lindsey's Lemma implies that no all-$1$ submatrix of $H$ can have more than
$2^m$ $1$-entries.

Now, the obtained subfunction $r'=r_1'(x_1,\ldots,x_m) \land
r_2'(y_1,\ldots,y_m)$ of the rectangle function $r=r_1\land r_2$
is also a rectangle function such that $r'(a,b)\leq f(a,b)$
for all $a,b\in\{0,1\}^{m}$. Since the set of all pairs $(a,b)$ for which
$r'(a,b)=1$ forms a *submatrix* of $H$ (here ``rectangularity'' of $r'$ is important), this implies that $r'$
can accept at most $2^m$ such pairs.
Since this holds
for each of the $2^{n-2m}$ assignments $\alpha$, the desired upper bound
$|r^{-1}(1)|\leq 2^n\cdot 2^{n-2m}=2^{n-m}$ follows.
Q.E.D.

Return to
the
home page of the book