\( \def\<#1>{\left<#1\right>} \let\geq\geqslant \let\leq\leqslant \def\bar#1{\overline{#1}} % an undirected version of \rightarrow: \newcommand{\mathdash}{\relbar\mkern-9mu\relbar} \newcommand{\AND}[1]{\mathrm{cnf}(#1)} \newcommand{\bc}[1]{\mathrm{bc}(#1)} \newcommand{\cL}{L} %{\mathcal L} \newcommand{\cP}{P} %{\mathcal P} \newcommand{\set}[1]{\{#1\}} \newcommand{\FF}{\mathbb{F}} \newcommand{\pRR}{\mathbb{R}_{\mbox{\tiny $+$}}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\gf}[1]{GF(#1)} \newcommand{\Norm}{\mathrm{N}} \newcommand{\const}[1]{c_{#1}} \newcommand{\cconst}[1]{\alpha_{#1}} \newcommand{\Exp}[1]{E_{#1}} \newcommand*{\ppr}{\mathbin{\ensuremath{\otimes}}} \newcommand*{\su}{\mathbin{\ensuremath{\oplus}}} \newcommand{\nulis}{\vmathbb{0}} %{\mathbf{0}} \newcommand{\vienas}{\vmathbb{1}} \newcommand{\Up}[1]{#1^{\uparrow}} %{#1^{\vartriangle}} \newcommand{\Down}[1]{#1^{\downarrow}} %{#1^{\triangledown}} \newcommand{\lant}[1]{#1_{\mathrm{la}}} % lower antichain \newcommand{\uant}[1]{#1_{\mathrm{ua}}} % upper antichain \newcommand{\skal}[1]{\langle #1\rangle} \newcommand{\NN}{\mathbb{N}} % natural numbers \newcommand{\RR}{\mathbb{R}} \newcommand{\minTrop}{\mathbb{T}_{\mbox{\rm\footnotesize min}}} \newcommand{\maxTrop}{\mathbb{T}_{\mbox{\rm\footnotesize max}}} \)

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 \begin{equation}\label{eq:depth2} G=\bigcap_{i=1}^r\bar{A_i\times B_i} \end{equation} 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 \begin{equation}\label{eq:dim} \AND{G}=\bc{\bar{G}}\,, \end{equation} 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:

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$


  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

⇦   Back to the comments page