# Explicit dense $K_{2,2}$-free graphs with small CNF representation

As in the book, let $\AND{G}$ denote the minimum number of clauses in a monotone CNF representing a given bipartite graph $G$. A biclique covering of a graph $G$ is a collection of bicliques (complete bipartite subgraphs) of $G$ such that each edge of $G$ belongs to at least one of the bicliques. Let $\bc{G}$ denote the minimum number of bicliques in such a covering of $G$. Note that for a bipartite graph $G\subseteq L\times R$, $\AND{G}$ is just the smallest number $r$ such that $G$ can be written as an intersection $$\label{eq:depth2} G=\bigcap_{i=1}^r\bar{A_i\times B_i}$$ of bipartite complements $\bar{A_i\times B_i}=(L\times R)\setminus (A_i\times B_i)$ of bicliques (bipartite complete graphs) $A_i\times B_i$, where $A_i=L\setminus I_i$ and $B_i=R\setminus I_i$. Equivalently, $\AND{G}$ is just the smallest number $r$ such that the bipartite complement of $G$ can be written as a union $\bar{G}=\bigcup_{i=1}^r A_i\times B_i$ of $r$ bicliques. This implies that $$\label{eq:dim} \AND{G}=\bc{\bar{G}}\,,$$ where $\bar{G}$ is the bipartite complement of $G$.

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 exist bipartite $K_{2,2}$-free graphs $G$ of average degree $d\approx n^{1/10}$ for which $\bc{\bar{G}}=O(\log n)$ holds (see this my comment).

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.

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

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:

1. L. Hambardzumyan, H. Hatami and N. Ndiaye (2022): On depth-3 circuits and covering number: an explicit counter-example, arxiv
2. 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