[This is a supplementary material to Chapter 2, Section 2.4]
Cover-free sets: tropical version of Schnorr's bound
Recall that, for a finite set $A\subseteq\NN^n$ of vectors,
$\MMin{A}$ = min size of a tropical $(\min,+)$ circuit
computing, for all input weightings $x\in\RR_+^n$, the minimum of $\skal{a,x}$ over all vectors $a\in A$.
$\MMax{A}$ = min size of a tropical $(\max,+)$ circuit
computing, for all input weightings $x\in\RR_+^n$, the maximum of $\skal{a,x}$ over all vectors $a\in A$.
$\Un{A}$ = min size of a Minkowski $(\cup,+)$ circuit producing the set $A$ by starting from $n+1$ singleton sets $\{\vec{0}\},\{\vec{e}_1\},\ldots,\{\vec{e}_n\}$ of vectors.
A vector $a\in\NN^n$ covers a vector $b\in\NN^n$ if $a\geq b$, that is, $a_i\geq b_i$ for all $i=1,\ldots,n$ holds.
Recall (from the book) that a set $A\subseteq\NN^n$ is cover-free if the following holds for any vectors $a,b,c\in A$:
\begin{equation}\label{eq:cover-free}
\mbox{if $a + b \geq c$ then $c\in\{a, b\}$,}
\end{equation}
that is, if the sum of no two vectors of $A$ covers any other vector of $A$. A subset $B\subseteq A$ is cover-free inside $A$ if
Eq. \eqref{eq:cover-free} holds for
any vectors $a,b\in B$ and $c\in A$, and is non-coverable inside $A$
if Eq. \eqref{eq:cover-free} holds for
any vectors $a,b\in A$ and $c\in B$. That is,
$B$ is cover-free inside $A$ if $a+b\not\geq c$ holds for all
$a,b\in B$ and $c\in A\setminus\{a,b\}$;
$B$ is non-coverable inside $A$ if $a+b\not\geq c$ holds for all
$a,b\in A$ and $c\in B\setminus\{a,b\}$.
In particular, if a set $A\subseteq\NN^n$ is cover-free, then it is both
cover-free and non-coverable inside itself.
In the book, we stated Schnorr's theorem (Theorem 2.1) as
a lower bound $\Un{A}\geq |A|-1$ on the Minkowski circuit complexity $\Un{A}$ of any cover-free set $A\subseteq\NN^n$. In fact, Schnorr [2]
proved a more flexible lower bound: $\Un{A}\geq |B|-1$ holds for any set $B\subseteq A$ which is cover-free inside $A$.
Below we give a similar lower bound (shown in [1]) also for tropical circuit complexities $\MMin{A}$ and $\MMax{A}$ of the corresponding optimization problems on the set $A$ of feasible solutions.
Recall that a set $A$ of vectors is an antichain if $a\not\leq a'$ for all $a\neq a'\in A$.
Theorem A (Tropical Schnorr's bound): Let $A\subseteq\{0,1\}^n$ be an antichain, and $B\subseteq A$ be any its subset with
$|B|\geq 2$ vectors.
If $B$ is cover-free inside $A$, then
$\MMin{A}\geq |B|/2$.
If $B$ is non-coverable inside $A$, then
$\MMax{A}\geq |B|/2$.
In particular, if the set $A$ itself is cover-free, then
$\MMin{A}\geq |A|/2$ and $\MMax{A}\geq |A|/2$.
Remark: Important in Theorem A is that it holds for arbitrary (not necessarily homogeneous) antichains $A\subseteq\{0,1\}^n$ of feasible solutions. If $A$ is cover-free and homogeneous (all vectors of $A$ have the same number of $1$s), then Schnorr's bound $\Un{A}\geq |A|-1$ (Theorem 2.1 in the book), together with Lemma 1.34(2), yields even better lower bounds $\MMin{A}\geq |A|-1$ and
$\MMax{A}\geq |A|-1$. But for non-homogeneous antichains $A\subseteq\{0,1\}^n$, already the gap $\Un{A}/\MMin{A}$
(not only the gap $|A|/\MMin{A}$) can be even exponential.
Such a gap is achieved when $A$ is the set of characteristic $0$-$1$ vectors of the feasible solutions of the shortest $s$-$t$ path problem on $K_n$
(see Corollary 2.5 in the book). $\Box$
Proof of Theorem A:
The proof in both cases (minimization and maximization) is similar.
A subset
$B\subseteq C$ of a set $C\subseteq\NN^n$ of vectors is a
Sidon set inside $C$ if the following holds for
all vectors $a,b\in B$ and all vectors $c,d\in C$:
\[
\mbox{if $a+b=c+d$ then $\{c,d\}=\{a,b\}$.}
\]
That is, the sum of any two vectors of $B$ is unique within the
entire set $A$, is different from the sum of any two other vectors
of $A$.
Theorem A in this comment
gives a lower bound
\[
\Un{C}\geq |B|/2
\]
on the Minkowski $(\cup,+)$ circuit complexity $\Un{C}$ of the set $C$ for any its subset $B\subseteq C$ that is a Sidon set inside $C$.
On the other hand, Lemma 1.31(1) in the book
(with "$C$" instead of "$B$") gives us set $C\subseteq\NN^n$ of vectors such that $A\subseteq C$ and
$\MMin{A}=\Un{C}$ and $C$ lies above $A$, i.e., for every vector $c\in C$ there is a vector $a\in A$ such that $c\geq a$
or
$\MMax{A}=\Un{C}$ and $C$ lies below $A$, i.e., for every vector $c\in C$ there is a vector $a\in A$ such that $c\leq a$.
So, in both cases, it is enough to show that $B$
is a Sidon set inside $C$: then the desired lower bound
$\Un{C}\geq |B|/2$ and, hence, the lower bounds $\MMin{A}\geq |B|/2$ and $\MMax{A}\geq |B|/2$ follow.
For vectors $a,b\in\NN^n$,
we will write $a \lt b$ if $a_i\leq b_i$ holds for all positions $i$, and
$a_i \lt b_i$ (a proper inequality) holds for at least one position.
Case 1: $(\min,+)$ circuits. In this case, the set $B$ is cover-free inside $A$, and $C$ lies above $A$.
Suppose for a contradiction that the set $B$ is not a Sidon set
inside $C$. Then there are vectors $a,b\in B$ and $c,d\in C$ such
that $a+b=c+d$ but $\{a,b\}\neq\{c,d\}$, that is,
$c,d\not\in \{a,b\}$. Since $C$ lies above $A$, there must be
vectors $x,y\in A$ such that $c\geq x$ and $d\geq y$. As $B$ is
cover-free inside $A$, $a+b\geq c\geq x$ implies $x\in\{a,b\}$.
Assume w.l.o.g. that $x=a$; then $c\geq a$. Since
$c\not\in \{a,b\}$, we have that $c > a$.
Together with $a+b=c+d$, this yields $d \lt b$ and, hence, also
$y\leq d \lt b$. But then one vector $y$ of $A$ is contained in
another vector $b$ of $A$, a contradiction with $A$ being an
antichain.
Case 2: $(\max,+)$ circuits. In this case, the set $B$ is non-coverable inside $A$, and $C$ lies below $A$.
In this case, the proof is ``symmetric.''
Suppose contrariwise that $B$ is not a Sidon set inside $C$. Then
there are vectors $a,b\in B$ and $c,d\in C$ such that $a+b=c+d$ but
$c,d\not\in\{a,b\}$. Since $C$ lies below $A$, there must be vectors
$x,y\in A$ such that $c\leq x$ and $d\leq y$. As $B$ is
non-coverable inside $A$, $x+y\geq c+d\geq a$ implies
$a\in\{x,y\}$. Assume w.l.o.g. that $a=x$; then $a\geq c$. Since
$c\not\in\{a,b\}$, this yields a proper inequality $a > c$ and, hence,
also $b \lt d\leq y$. But then one vector $y$ of $A$ contains another
vector $b$ of $A$, a contradiction with $A$ being an antichain.
∎
Example 1: $(\min,+)$ circuits.
Let $2\sqrt{n}\leq k \lt n/2$ and consider the following minimization
problem: given an assignment of nonnegative weights to the edges of
$K_n$, find the minimum weight of a subgraph of $K_n$ which is either a
$k$-clique $K_k$ or a star $K_{1,n-1}$.
The set $A$ of characteristic $0$-$1$ vectors of feasible solutions
is the union $A=B\cup C$ of the set $B$ of characteristic $0$-$1$ vectors
of all $|B|=\binom{n}{k}$ $k$-cliques, and $C$ is the set of characteristic $0$-$1$ vectors of all
$|C|=n$ stars.
Since
$n-1 \lt \binom{k}{2}$, the lower envelope $\lenv{A}$ of $A$ is the set $C$ of $n$ stars. So, the lower bower bound $\MMin{A}\geq \Un{\lenv{A}}=\Un{C}$ given by Lemma 1.34(2)
in the book cannot yield any larger than $\Un{C}=O(n^2)$ lower bound on
$\MMin{A}$. But Theorem A already
yields an exponential lower bound
$\MMax{A}\geq |B|/2=\frac{1}{2}\binom{n}{k}$.
By Theorem A, it is enough to show that the set $B$ is
cover-free inside $A$.
To show this,
take a union of two $k$-cliques. Since
$2(k-1) \lt n-1$ and since no star in $K_k$ can have more than $k-1$ edges,
the union cannot contain a star $K_{1,n-1}$. So, it remains to show that the union of two $k$-cliques cannot contain some third $k$-clique.
For this, assume the opposite, i.e., that the union
of some two $k$-cliques contains some third $k$-clique. Since each
$k$-clique has the same number $k$ of nodes, the latter clique must
then have a node $u$ not in the first clique and a node $v$ not in
the second clique. If $u=v$ then the node $u$ is not covered, and
if $u\neq v$ then the edge $\{u,v\}$ is not covered by the union of
the first two cliques, a contradiction. Thus, the set $B$ is
cover-free inside $A$.
$\Box$
Example 2: $(\max,+)$ circuits.
Let $n \gt 4$ be a prime power, and $1\leq d\leq n/2$ be an integer.
Consider the complete bipartite
$n\times n$ graph $K_{n,n}$ with parts $U=V=\gf{n}$.
A double-star is a $K_{2,n}$
subgraph of $K_{n,n}$. The graph of a
univariate polynomial $g(x)$ over $\gf{n}$ is a subgraph of $K_{n,n}$ consisting of $n$ edges
$\{i,g(i)\}$ with $i\in U$ (see Fig. 1).
Fig. 1: A double-star (left) in the graph $U\times V$ with $U=V=\gf{5}$, and the graph of the polynomial $g(x)=x^2+1$ over $\gf{5}$ of degree $d=2$ (right).
Let $A=B\cup C\subseteq \{0,1\}^{n^2}$,
where $B$ is the set of all $|B|=n^d$ characteristic $0$-$1$ vectors of graphs
of polynomials of degree at most $d-1$ over $\gf{n}$, and $C$ is the
set of all $|C|=\binom{n}{2}$ characteristic vectors of double-stars.
We want to lower-bound $\MMax{A}$.
The upper envelope $\henv{A}$ of $A$ is the set $C$ of $\binom{n}{2}$ stars. So, the lower bower bound $\MMax{A}\geq \Un{\henv{A}}=\Un{C}$ given by Lemma 1.34(2)
in the book cannot yield any larger than $\Un{C}=O(n^3)$ lower bound on
$\MMax{A}$. But Theorem A already
yields an exponential lower bound
$\MMax{A}\geq |B|/2=n^d/2$.
By Theorem A, it is enough to show that the set $B$ is
non-coverable inside $A$.
To show this, suppose $a+b\geq c$ holds for some $a,b\in A$ and
$c\in B$. Hence, $c$ is the (graph of) some polynomial $g(x)$ of degree at most $d-1$ over $\gf{n}$. Since
vector $c$ has $n$ ones, it must share at least $n/2$ ones with at
least one of the vectors $a$ and $b$; let it be vector $a$. This
vector cannot be the characteristic vector a double-star because every
double-star has only $2\lt n/2$ non-isolated nodes in $U$,
while all $|U|=n$ nodes in $U$ of the graph $c$ of the polynomial $g$ are non-isolated. So, $a$ must
be a graph of some polynomial $h(x)$ of degree at most $d-1$ over $\gf{n}$. Since no two distinct
polynomials of degree at most $d-1$ can share $d$ or more values in
common, and since $n/2\geq d$, we have that $g=h$, and hence, also
$c=a$. Thus, the set $B$ is non-coverable inside $A$, and
Theorem A yields $\MMax{A}\geq |B|/2=n^d/2$, as desired.
$\Box$
Jump back ☝