As mentioned in the book, strong lower bounds on the CNF complexity of graphs could imply
impressive lower bounds for depth-$3$ circuits, if we could prove such
bounds for graph *properties*.
Of particular interest is the following question: what monotone
properties of graphs force their large CNFs? A property of graphs is
*hereditary* if it is preserved under deletion of edges. For
example, the property of avoiding some fixed graph $H$ as a subgraph is a hereditary property.

Is there a graph $H$ such that $\AND{G}\geq d^{\Omega(1)}$ holds for every bipartite $H$-free graph $G$ of average degree $d$? In view of \eqref{eq:dim}, this question is equivalent to the following question about the biclique covering number of graphs.

Is there a graph $H$ such that $\bc{\bar{G}}\geq d^{\Omega(1)}$ holds for every bipartite $H$-free graph $G$ of average degree $d$?In 1988, Pudlak, Roedl and Savicky asked whether this holds for $K_{2,2}$-free graphs $G$ (that is, when $H=K_{2,2}$). This was stated as the Research Problem 1.33 in the book (with its equivalent reformulations as Research Problems 4.9 and 11.17). In 2011, a negative answer was given by Katz [2] using probabilistic arguments: there

In 2022,
Hambardzumyan, Hatami and Ndiaye [1] have found a cute and very simple *explicit* construction of a bipartite
$K_{2,2}$-free graphs $G$ of average degree $d\approx n^{1/3}$ for which $\bc{\bar{G}}=O(\log^4 n)$ holds.

By viewing these matrices $A$ as incidence matrices of complements $\bar{G}$ of bipartite graphs $G$, Theorem 1 gives us bipartite $K_{2,2}$-free graphs $G$ of average degree $d\approx n^{1/3}$ for which $\bc{\bar{G}}=O(\log^4 n)$ holds.Theorem 1:There are explicit $n \times n$ Boolean matrices $A$ with $\Omega(n^{4/3})$ zero-entries and no $2 \times 2$ all-zero submatrices such that the $1$-entries of $A$ are covered by only $O(\log^4 n)$ all-$1$ submatrices of $A$.

**Proof**
Let $n=2m^3$ for
a positive integer $m$, and define the sets
$ \cP = \cL := [m] \times [2m^2]$. We think of the elements $\ell=(a,b) \in \cL$ as lines $y=ax + b$ in $\RR^2$, and the elements $p=(x,y) \in \cP$ as points in $\RR^2$.
A point $(x,y)$ *lies* on a line $(a,b)$ if $ax+b=y$.
Define the Boolean matrix $A$ according to point line incidences: $A[(x,y),(a,b)]=0$ iff the point $(x,y)$ lies on a line $(a,b)$.
Observe that $A$ is an $n \times n$ matrix for $n=2m^3$ that satisfies the conditions of Theorem 1:

- $A$ has no $2 \times 2$ all-zero submatrices since there is at most one line in $\cL$ that passes through any two distinct points in $\cP$.
- $A$ has at least $m^4$ zero-entries: for any fixed $a,x\in [m]$, and $b\in [m^2]$, the point $p=(x,y)= (x,a x+b) \in \cP$ lies on the line $\ell=(a,b) \in \cL$.

Let us now construct the desired the covering of $1$-entries of $A$ by all-$1$ submatrices. Let $q$ be a prime number. For every triple $(i,j,k)\in[q]^3$, consider the set $R^{q}_{i,j,k} = \cP^{q}_{i,j,k}\times \cL^{q}_{i,j,k}$ of entries of the matrix $A$ given by the following sets of rows and columns: \begin{align*} \cP^{q}_{i,j,k}&=\{(x,y)\in \cP \colon x \equiv i \ \text{ and } y \not\equiv i j+k \}\\ \cL^{q}_{i,j,k}&=\{(a,b)\in \cL\colon a \equiv j \ \text{ and } \ b \equiv k\}, \end{align*} where $\equiv$ means equality modulo $q$. It is clear that for any choice of $q$ and for any $(i,j,k) \in [q]^3$, the set $R^q_{i,j,k}$ is a $1$-monochromatic rectangle of $A$ because any $[(x,y),(a,b)] \in R^q_{i,j,k}$ satisfies $ax+b \neq y \mod q$ (and, hence, also $ax+b \neq y$). Next, fix $r = \lceil \log_2 (2m^2) \rceil$ and let $Q$ be the set of all prime numbers $q$ smaller than $r$. We claim that the $O(r^4)=O(\log^4 m)=O(\log^4 n)$ all-$1$ submatrices $\{R^{q}_{i,j,k}\colon q\in Q,\ (i,j,k)\in[q]^3\}$ of the matrix $A$ cover all its $1$-entries.

Indeed, if a $1$-entry $A[(x,y),(a,b)]$ is not covered by $S$, then for all $q\in Q$, we have $y=(ax+b)\mod q$. Consequently, $y=(ax+b) \mod \prod_{q\in Q} q$. However, since both $y$ and $ax+b$ are at most $2m^2 \lt \prod_{q\in Q} q$, they can only be equal modulo $\prod_{q\in Q} q$ if they are equal. This implies that $A[(x,y),(a,b)]=0$, so all the $1$-entries of $A$ are covered. $\Box$

**References:**

- L. Hambardzumyan, H. Hatami and N. Ndiaye (2022): On depth-3 circuits and covering number: an explicit counter-example, arxiv
- N.H. Katz, On the CNF-complexity of bipartite graphs containing no squares, Lithuanian Mathematical Journal 52(4) (2012), 385-389. Preliminary version: ArXiv. Local copy: manuscript