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