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 lemmaLet $\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 that

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

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$

- $\mes_0$ and $\mes_1$ are some length measures;
- $\factor{0}$ and $\factor{1}$ are the shrinking factors of $\mes_0$ and $\mes_1$;
- $\max\{2,\factor{0}\}\leq s\leq n$ and $\max\{2,\factor{1}\}\leq r\leq n$ are arbitrary integers.

Switching CNF to DNF:For every short CNF $\CC{f}$, there is a short DNF $\DD{f}$ and a long DNF $D$ such that:

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

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)Switching DNF to CNF:For every short DNF $\DD{f}$, there is a short CNF $\CC{f}$ and a long CNF $D$ such that:

- 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\,. \]

S. Jukna January 2018