Recall that a length measure of sets is any non-negative measure $\mes:2^X\to\NN$ such that $\mes(\emptyset)=0$, $\mes(S)\leq |S|$, and $S\subseteq T$ implies $\mes(S)\leq \mes(T)$. The defect of $\mes$ is the smallest number $\factor{}\geq 1$ such that $|S|\leq \mes(S)^{\factor{}}$ holds for every subset $S\subseteq X$.
A set $S\subseteq X$ respects a length measure $\mes$ if for every subset $T\subseteq S$ and every element $x\in X$, $\mes(T\cup\{x\})=\mes(T)$ implies $x\in S$.
For example, in the case of a trivial measure $\mes(F)=|F|$ (the cardinality of $F$), we have $\factor{}=1$, and any set respects this measure: then $\mes(T\cup\{x\})=\mes(T)$ implies $x\in T$. A less trivial example is the length measure $\mes(S)$ for graphs (viewed as sets of their edges): $\mes(S)$ = the number of vertices touched by edges of $S$. Then $\factor{}\leq 2$, and only cliques respect this measure.
Transversal lemma Let $\mes:2^X\to\NN$ be any length measure, and $\A\subseteq 2^X$ a finite family of sets. Then for every integer $\param\geq 1$, there is a family $\f\subseteq 2^X$ of sets such thatProof: Fix the order $\A=\{A_1,\ldots,A_l\}$ of sets in $\A$, and construct the following "transversal" tree $T$ of out-degree at most $a$. Every edge of $T$ will be labeled by some element $x\in X$. So, for a node $u$, let $\lab{u}$ denote the set of labels of edges of the unique path from the root of $T$ to $u$. If $u$ is the root, then we set $\lab{u}=\emptyset$. We will keep the following invariant for every node $u$ and every transversal $B$ of $\A$ respecting the length measure $\mes$:
- every $F\in\f$ with $\mes(F)<\param$ is a transversal of $\A$;
- every transversal of $\A$ respecting $\mes$ contains at least one set of $\f$, and
- $|\{F\in\f\colon \mes(F)\geq \param\}|\leq a^{\param}$.
$(\ast)$ If $\lab{u}\subseteq B$, and if $u$ is not a leaf, then there is an edge $(u,v)$ leaving $u$ such that $\lab{v}\subseteq B$.
The first node (the root) of $T$ corresponds to the first set $A_1$, and the outgoing $|A_1|$ edges are labeled by the elements of $A_1$. Suppose we have reached a node $u$. If $\lab{u}$ intersects all the sets of $\A$, then $u$ is a leaf. Otherwise, let $A_i$ be the first set in $\A$ for which $\lab{u}\cap A_i=\emptyset$.
Case 1: $\mes(\lab{u}\cup\{x\})=\mes(\lab{u})$ holds for some $x\in A_i$. In this case, we put one outgoing edge $(u,v)$ labeled by the element $x$ (if there are several such elements $x\in A_i$, then we take any one of them). So, $\lab{v}=\lab{u}\cup\{x\}$ and, hence, $\lab{v}\cap A_i\neq\emptyset$. Now let $B\subset X$ be any set respecting the measure $\mes$, and suppose that $\lab{u}\subseteq B$ holds. Held $x\not\in B$, then the fact that $B$ respects $\mes$ would yield $\mes(\lab{u}\cup\{x\}) > \mes(\lab{u})$, a contradiction. So, $\lab{v}=\lab{u}\cup\{x\}\subseteq B$, that is, the invariant $(\ast)$ holds in this case.
Case 2: $\mes(\lab{u}\cup\{x\})>\mes(\lab{u})$ holds for all $x\in A_i$. In this case, we put $|A_i|$ outgoing edges labeled by elements of $A_i$. Hence, $\lab{v}\cap A_i\neq\emptyset$ holds for every son $v$ of $u$. Let $B$ be any transversal of $\A$ (not necessarily respecting the measure $\mes$). Since $B$ must intersect also the set $A_i$, $x\in B$ and, hence, also $\lab{v}=\lab{u}\cup\{x\}\subseteq B$ must hold for some element $x\in A_i$. Thus, the invariant $(\ast)$ holds also in this case (even for transversals $B$ not respecting the measure $\mes$).
Now let $L_{\param}$ be the set of all leaves $v$ of $T$ such that $\mes(\lab{v}) < \param$, and $V_{\param}$ be the set of all nodes $v$ such that $\mes(\lab{v}) \geq \param$ but $\mes(\lab{u}) < \param$, where $u$ is the immediate predecessor of $v$. We are going to show that the family $\f=\{\lab{v}\colon v\in L_{\param}\cup V_{\param}\}$ has the desired properties (1)-(3). The first property (1) is obvious because $\lab{v}\in\f$ and $\mes(\lab{v})< \param$ means that $v$ is a leaf and, hence, $\lab{v}$ must intersect all sets of $\A$.
To show property (2), take an arbitrary transversal $B$ of $\A$ respecting $\mes$. Since the invariant $(\ast)$ holds, and since, after each step, we intersect one of the not-intersected-yet sets $A_i$, there is a finite path $p=(u_0,u_1,\ldots,u_r)$ from the root $u_0$ to a leaf $v=u_r$ such that $\lab{u_i}\subseteq B$ holds for all $i$. Since $v=u_r$ is a leaf, the set $\lab{v}$ is a transversal of $\A$. If $\mes(\lab{v}) <\param$, then $v\in L_{\param}$ and, hence, $\lab{v}\in\f$. So, assume that $\mes(\lab{v}) \geq \param$. Since $\mes(\lab{u_0})=\mes(\emptyset)=0$ and $\mes$ is monotone, there must be some $i$ for which $\mes(\lab{u_{i-1}}) < \param$ and $\mes(\lab{u_{i}})\geq \param$. So, the node $u_i$ belongs to $V_{\param}$, meaning that the set $\lab{u_{i}}$ belongs to our family $\f$, as desired.
To show property (3), it is enough to show that $|V_{\param}|\leq a^{\param}$.
Claim: Every path from the root to a node $v\in V_{\param}$ has at most $\param$ nodes of out-degree larger than $1$.Proof: Take a node $v\in V_{\param}$, and let $p=(u_0,u_1,\ldots,u_r)$ be the path from the root $u_0$ to this node $u_r=v$. We have a sequence $0=\param_0\leq \param_1\leq \ldots\leq \param_{r-1}\leq\param_r$ of integers $\param_i:=\mes(\lab{u_i})$ such that $\param_{r-1}\leq \param-1$ and $\param_{r}\geq \param$. Let $I$ be the set of positions $0\leq i \leq r-2$ such that $\param_i < \param_{i+1}$ (strong inequality). Since the $\param_i$s are integers, and $\param_{r-1}\leq \param-1$, we have $|I|\leq \param-1$. The positions $i\in I$ correspond to the Case 2 in our construction of the tree, and only they can lead to out-degree $>1$. So, the number of nodes of the path $p$ with out-degree larger than $1$ is at most $|I|+1\leq \param$, as desired. $\Box$
Since the out-degree of each node of $T$ is at most the maximum $a$ of the sizes of the sets $A_i$, Claim implies that there cannot be more than $a^{\param}$ paths to the nodes in $V_{\param}$. Hence, $|V_{\param}|\leq a^{\param}$, as desired. This completes the proof of the Transversal lemma. $\Box$
Switching CNF to DNF: For every short CNF $\CC{f}$, there is a short DNF $\DD{f}$ and a long DNF $D$ such that:Proof: Let $\A\subseteq 2^{[n]}$ be the family of clauses of $\CC{f}$. Since every clause of $\CC{f}$ has $\mes_0$-length at most $s-1$, every set $A\in\A$ has $|A|\leq a$ elements for $a=(s-1)^{\factor{0}}$. Apply the Transversal lemma with $m:=r$, and let $\f\subseteq 2^{X}$ be the family guaranteed by this lemma. If we take $\DD{f}:=\{f\in\f\colon \mes_1(F) < r\}$ and $D:=\{F\in\f\colon \mes_1(F)\geq r\}$, then the Transversal lemma automatically ensures all three properties. $\Box$
- every monomial of $\DD{f}$ intersects all clauses of $\CC{f}$;
- every monomial intersecting all clauses of $\CC{f}$ and respecting $\mes_1$ contains some monomial of $\DD{f}\lor D$;
- $D$ has at most $(s-1)^{\factor{0}\cdot r}$ monomials.
The proof of the following dual version is similar.
Switching DNF to CNF: For every short DNF $\DD{f}$, there is a short CNF $\CC{f}$ and a long CNF $D$ such that:With these switching lemmas, the proof of the lower bounds criterion remains almost the same. The only difference is that now we restrict our attention to special inputs ("positive" and "negative" inputs) respecting the chosen length measures for clauses and monomials. For completeness, here is the entire proof.
- every clause of $\CC{f}$ intersects al monomials of $\DD{f}$;
- every clause intersecting all monomials of $\DD{f}$ and respecting $\mes_0$ contains some clause of $\CC{f}\land C$;
- $C$ has at most $(r-1)^{\factor{1}\cdot s}$ clauses.
It is clear that every clique $Q\subseteq X$ respects $\mes_1$. Indeed, if $S\subset Q$ is some subset of its edges, and $\mes_1(S\cup\{e\})=\mes_1(S)$ for an edge $e$, then we can add this edge to $S$, and the resulting graph $S\cup\{e\}$ will still be contained in the clique $Q$.
Every coloring $h:[n]\to [r]$ defines a graph $G_h$ whose edges join all pairs of nodes of the same color. Any such graph is just disjoint union of at most $r$ cliques, covering all nodes. It can be shown that every such graph $G_h$ respects $\mes_0$. To show this, take an arbitrary subset $S\subseteq G_h$ of edges, and assume that $S\cup\{e\}\not\subseteq G_h$ holds for some edge $e=\{u,v\}$; hence, $h(u)\neq h(v)$. We have to show that then $\mes_0(S\cup\{e\}) > \mes_0(S)$ must hold.
Case 1: $\mes_1(S\cup\{e\})=\mes_1(S)$. Then the endpoints $u$ and $v$ of the edge $e$ must be already touched by some edges of $S$. Since $h(u)\neq h(v)$, these endpoints must belong to distinct connected components. So, the edge $e$ connects two disconnected components. This yields $\kappa(S\cup\{e\})\leq \kappa(S)-1$, and $\mes_0(S\cup\{e\})\geq \mes_0(S)+1$ follows.
Case 2: $\mes_1(S\cup\{e\})\geq \mes_1(S)+1$. Since we always have $\kappa(S\cup\{e\})\leq \kappa(S)$, the desired inequality $\mes_0(S\cup\{e\})\geq \mes_0(S)+1$ follows also in this case.
The deviation factors $\factor{1}$ and $\factor{0}$ of these two measures are both $\leq 2$. Indeed, $|S|\leq \binom{\mes_1(S)}{2}\leq \mes_1(S)^2$.
To show that $|S|\leq \mes_0(S)^2$ also holds, let $F\subseteq S$ be a spanning forest with $|F|=\mes_0(S)$ edges. Suppose that $F$ consists of $k$ connected components, the $i$-th of which has $m_i$ edges. Hence, $\mes_0(S)=|F|=\sum_{i=1}^k m_i$. So, \[ |S|\leq \sum_{i=1}^k\binom{m_i+1}{2}=\sum_{i=1}^k\binom{m_i}{2}+\sum_{i=1}^k\binom{m_i}{1} \leq \sum_{i=1}^k m_i^2 + \sum_{i=1}^k m_i\leq \left(\sum_{i=1}^k m_i\right)^2=|F|^2= \mes_0(S)^2\,. \]