\(
\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$