Cover-free sets: tropical version of Schnorr's bound

• $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 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.

1. If $B$ is cover-free inside $A$, then $\MMin{A}\geq |B|/2$.
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$.

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⁽¹⁾ in the book (with "$C$" instead of "$B$") gives us set $C\subseteq\NN^n$ of vectors such that $A\subseteq C$ and

1. $\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
2. $\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$.

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⁽²⁾ 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⁽²⁾ 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$

^{(1)   Jump back ☝}

(2)   Jump back ☝

Page last modified on:  1.11.2023