\( \def\<#1>{\left<#1\right>} \newcommand{\c}{\mathsf{c}} \newcommand{\rk}[1]{\mathrm{rk}(#1)} \)

How many linear inequalities do we need to represent monotone boolean functions?

Let $f:\{0,1\}^n\to\{0,1\}$ be a monotone boolean function. Say that $f$ is $m$-representable if there is an $m\times n$ matrix $A=(a_{ij})$ with nonnegative real entries, and a nonnegative vector $b$ such that $f(x)=0$ iff $Ax\leq b$. Let $m(f)$ denote the smallest number $m$ such that $f$ is $m$-representable.

A lower one of $f$ is a vector $x$ such that $f(x)=1$ but $f(x')=0$ for any vector $x'$ obtained from $x$ by switching any its $1$-entry to $0$. Let $L_f$ denote the set of all lower ones of $f$. The function $f$ is $k$-homogeneous if all vectors in $L_f$ have exactly $k$ ones.

Theorem (Zuev and Trishin [1]): If $f$ is homogeneous, and any two lower ones of $f$ differ in more than $2$ bits, then $m(f)\geq |L_f|$.
Proof: It is enough to show that any hyperplane $\sum_{i=1}^n a_ix_i=b$ can separate at most one lower one $x\in L_f$ from vectors in $f^{-1}(0)$. Assume contrariwise that the plane separates two lower ones $x\neq y\in L_f$ from vectors in $f^{-1}(0)$. That is \[ \sum_{i=1}^n a_ix_i > b\ \ \mbox{ and }\ \ \sum_{i=1}^n a_iy_i > b\ \ \mbox{ but }\ \ \sum_{i=1}^n a_iz_i \leq b \] for every vector $z$ such that $f(z)=0$. Let $r\neq s$ be positions where $x$ and $y$ differ: $x_r=1, y_r=0$ and $x_s=0, y_s=1$; such positions must exist since $x$ and $y$ must differ it at least two positions. If $a_r\geq a_s$, then replace the bits $y_r$ and $y_s$ of $y$ by bits $x_r$ and $x_s$, respectively, and let $y'$ be the resulting vector. \[ \begin{array}{lcccccccc} & & & & r & & s & & \\ x & = & x_1 & \cdots & 1 & \cdots & 0 & \cdots & x_n \\ y & = & y_1& \cdots & 0 & \cdots & 1 & \cdots & y_n \\ y' & = & y_1& \cdots & 1 & \cdots & 0 & \cdots & y_n \\ \end{array} \] Since $a_r\geq a_s$, we have that \[ \sum_{i\not\in\{r,s\}}a_i y_i > b - a_r\cdot 0 - a_s\cdot 1 \geq b - a_r\cdot 1 - a_s\cdot 0. \] implying that $f(y')=1$. Since $y'$ has the same number of bits as $y$, vector $y'$ is also a lower one of $f$. But $y$ and $y'$ differ in only 2 bits, a contradiction. If $a_r < a_s$, then just replace the roles of $x$ and $y$. $\Box$

Example: The triangle function is a monotone boolean function $f_{\Delta}$ of $\binom{n}{2}$ variables, one for each edge of $K_n$, and accepts an input $x$ iff the subgraph of $K_n$ specified by $x$ contains a triangle. By taking for each potential triangle $T=\{u,v,w\}$ one inequality $x_{u,v}+x_{v,w}+x_{u,w}\leq 2$, we have that $m(f_{\Delta}) \leq \binom{n}{3}$. On the other hand, since triangles are lower ones of $f_{\Delta}$, and since any two triangles can share at most one common edge, the distance between any two lower ones is at least $4$, and the theorem gives $m(f_{\Delta}) \geq \binom{n}{3}$.

Theorem (Graham and Sloane [2]): For every $4\leq k \leq n-4$, the $k$-th layer $\binom{n}{k}$ of the hypercube $\{0,1\}^n$ contains a set of at least $\binom{n}{k}n^{-1}$ vectors, each two of which differ in more than $2$ positions.
Proof: Consider the mapping $T:\binom{n}{k}\to\{0,1,\ldots,n-1\}$ given by \[ T(x)=\sum_{i:x_i=1} i \ \ \bmod{n} \] For $t\in\{0,1,\ldots,n-1\}$, consider the $k$-homogeneous set $A_t=T^{-1}(t)$. We claim that every two vectors in $A_t$ must differ in more than $2$ bits. Assume contrariwise that there are vectors $x\neq y$ in $A_t$ that differ in $2$ bits (they cannot differ in only one bit). Let $r\neq s$ be positions where $x$ and $y$ differ: $x_r=1, y_r=0$ and $x_s=0, y_s=1$. Since $T(x)=T(y)=t$, there is some number $a\in\{0,1,\ldots,n-1\}$ such that, modulo $n$, both $a+r$ and $a+s$ are equal to the same number $t$. But this is impossible, because $r,s < n$ and $r\neq s$. Thus, each set $A_t$ satisfies the required distance-condition. Since $|A_0|+|A_1|+\cdots+|A_{n-1}|=\binom{n}{k}$, on of the sets has the desired cardinality. $\Box$

Reference:

  1. [1] Ju.A. Zuev and V.N. Trishin, A lower bound on the number of linear inequalities representing a monotone boolean function of $n$ variables, J. of Computational Math. and Mathematical Physics 23(3) (1983), 754-756. English version in: USSR Computational Mathematics and Mathematical Physics 23(3) (1983), 155–156. Local copy (in Russian).
  2. [2] R.L. Graham and N.J.A. Sloane, Lower bounds for constant weight codes. IEEE Trans. of Inform. Theory 26(1) (1980) 37-43. Local copy

S. Jukna, December 2014