\( \def\<#1>{\left<#1\right>} \def\bar#1{\overline{#1}} \newcommand{\factor}[1]{c_{#1}} \newcommand{\mes}{\mu} \newcommand{\f}{{\cal F}} \newcommand{\A}{{\cal A}} \newcommand{\NN}{{\mathbb N}} \newcommand{\hh}{{\cal H}} \newcommand{\DD}[1]{{#1}_{\mathrm{dnf}}} \newcommand{\CC}[1]{{#1}_{\mathrm{cnf}}} \newcommand{\lab}[1]{F_{#1}} \newcommand{\param}{m} \DeclareDocumentCommand\setdef{mo}{\left\{#1\IfNoValueTF{#2}{}{ : #2}\right\}} \)

Notes on Theorem 9.26 (monotone circuits for graph properties)

On page 268, we only sketched the proof of the Monotone Switching Lemma. But I've forgot to mention one additional condition on the length measure $\mes$: selected inputs must "respect" this measure. The point is that, without that condition, the length of the path $p$ can be much larger than $2r$: even if $p\cap q=\emptyset$, the clause $q$ can contain a variable $x_i$ such that $\mes(p\cup\{x_i\})=\mes(p)$. That is, the $\mes$-length of the path needs not increase along every edge. So, the goal of this comment is to give a corrected proof. [I was just not carefull enough when translating the results of Jukna (1999) from the language of finite limits to the language of CNFs and DNFs.]

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.

1. Transversal lemma

A transversal of a family of sets is a set intersecting all members of the family.
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 that
  1. every $F\in\f$ with $\mes(F)<\param$ is a transversal of $\A$;
  2. every transversal of $\A$ respecting $\mes$ contains at least one set of $\f$, and
  3. $|\{F\in\f\colon \mes(F)\geq \param\}|\leq a^{\param}$.
Proof: 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$:

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

2. Switching lemmas

The deviation factor of a length measure $\mes:2^{X}\to\NN$ is the smallest number $\factor{}\geq 1$ such that $|S|\leq \mes(S)^{\factor{}}$ holds for every subset $S\subseteq X$, and $\mes(\{x\})\leq \factor{}$ holds for every single element $x\in X$. In the following, we will use the following parameters. We will identify clauses/monomials with sets of indices of their variables. Call a clause short if its $\mes_0$-length at most $s-1$, and long otherwise. A CNF is short if all its clauses are short, and is long if all its clauses are long (note: "long" $\neq$ "not short", some CNFs may be neither short nor long). In the case of monomials and DNFs we use the measure $\mes_1$ and the threshold $r$.
Switching CNF to DNF: For every short CNF $\CC{f}$, there is a short DNF $\DD{f}$ and a long DNF $D$ such that:
  1. every monomial of $\DD{f}$ intersects all clauses of $\CC{f}$;
  2. every monomial intersecting all clauses of $\CC{f}$ and respecting $\mes_1$ contains some monomial of $\DD{f}\lor D$;
  3. $D$ has at most $(s-1)^{\factor{0}\cdot r}$ monomials.
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$

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:
  1. every clause of $\CC{f}$ intersects al monomials of $\DD{f}$;
  2. every clause intersecting all monomials of $\DD{f}$ and respecting $\mes_0$ contains some clause of $\CC{f}\land C$;
  3. $C$ has at most $(r-1)^{\factor{1}\cdot s}$ clauses.
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.

3. Measures respected by cliques and cocliques

We have used nontrivial length measures only in the proof of Theorem 9.26 (for CLIQUE-like functions). Let $X$ be the set of all edges of $K_n$. For a graph $S\subseteq X$, define \[ \mes_1(S) := \mbox{number of vertices touched by at least one edge of $S$} \] and \[ \mes_0(S) := \mbox{minimum number of edges in a spanning forest of $S$.} \] Note that $\mes_0(S)= \mes_1(S)-\kappa(S)$, where $\kappa(S)$ is the number of connected components in $S$. Let us show that these used in the proof of Theorem 9.26 measures are respected by the used positive and negative inputs.

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