Explicit bipartite graphs of high resistance (Jukna): construct $G_n$ with $\rho(G_n) \ge n^\varepsilon$

The resistance $\rho(G)$ of a bipartite graph $G$ is the smallest $r$ such that $G$ can be written as the intersection of $r$ graphs, each of which has biclique covering number at most $r$; Jukna also characterizes it by $r \times r$ Boolean matrices assigned to vertices. Introduced by Jukna (2009) as a graph-complexity measure that lower-bounds the CNF complexity of graphs and controls lower-bound prospects for boolean circuits, its central open problem is to exhibit an explicit family of $n \times n$ bipartite graphs with $\rho(G_n) \ge n^\varepsilon$ for a constant $\varepsilon > 0$, which would yield the first super-linear lower bounds for boolean circuits of logarithmic depth. Jukna also poses related but separate open questions — on an explicit separation between the resistance of a graph family and of its bipartite complements, and on explicit sets $U \subseteq \{0,1\}^n$ whose biclique-partition complexity $\kappa(U)$ grows faster than $n^2$ — which are distinct from the target of this problem. One originally proposed route toward such bounds — biclique-covering lower bounds for $K_{2,2}$-free graphs — has since been refuted by Katz (2012, probabilistic) and by Hambardzumyan, Hatami and Ndiaye (2022, explicit); the resistance problem itself remains open.

Background

A biclique of a bipartite graph $G$ is a complete bipartite subgraph $A \times B$ with $A, B$ nonempty vertex sets. The biclique covering number $bc(G)$ is the minimum number of bicliques whose union covers all edges of $G$; the biclique partition number additionally requires edge-disjointness. By the Graham–Pollak theorem, partitioning the edges of the complete $n$-vertex graph into complete bipartite graphs needs $n-1$ parts, and covering-based analogues of this phenomenon underlie many lower-bound arguments. Two standard lower bounds on $bc(G)$ are the fooling-set bound — a fooling set is a collection of edges $(x_i, y_i)$ such that for all $i \ne j$ at least one of $(x_i, y_j)$, $(x_j, y_i)$ is a non-edge, and a fooling set of size $m$ forces $bc(G) \ge \log_2 m$ — and the matching bound $bc(G) \ge \nu(G)^2/|E|$ for bipartite $G$ containing $\nu$ vertex-disjoint edges, proved by Jukna and Kulikov (2009). These covering numbers connect to circuit complexity through the CNF complexity of graphs: a bipartite graph $G \subseteq V \times W$ is represented by a conjunction of clauses $\bigcap_i CL(A_i, B_i)$ where $CL(A,B) = (A \times W) \cup (V \times B)$, and since the complement of a clause graph is a biclique, a CNF with $k$ clauses for $G$ exists exactly when the bipartite complement $\bar{G} = (V \times W) \setminus G$ is a union of at most $k$ bicliques. The resistance $\rho(G)$ refines this two-level picture: it is the smallest $r$ such that $G$ is the intersection (as edge sets) of $r$ bipartite graphs on the same vertex set, each having biclique covering number at most $r$; Jukna also characterizes it equivalently by $r \times r$ Boolean matrices assigned to vertices, with adjacency expressed by a matrix-product condition. Small resistance means $G$ admits a highly compressible layered representation, so explicit graphs of provably large resistance are natural candidates for circuit lower bounds: Jukna showed that such graphs imply super-linear size lower bounds for boolean circuits of logarithmic depth (depth $O(\log n)$), a frontier related to the still-open min-rank conjecture of Jukna and Schnitger — which asks whether a system of semi-linear equations over $GF(2)$ can have more than $2^{n - c \cdot \mathrm{mr}(A)}$ solutions, where $\mathrm{mr}(A)$ is the smallest $GF(2)$-rank of a completion of the pattern matrix $A$, and is motivated by exactly the problem of proving super-linear lower bounds for log-depth circuits computing linear operators. A separate asymmetric question of Jukna asks whether some explicit family satisfies $\ln \rho(G_n) \le (\ln \ln n)^c$ while $\ln \rho(\bar{G}_n) \ge (\ln \ln n)^\alpha$ with $\alpha \to \infty$, where $\bar{G}_n = (V_n \times W_n) \setminus G_n$ is the bipartite complement; Jukna relates this question to a longstanding separation problem in communication complexity, and it is not part of the target of this problem. A further related question posed by Jukna asks for explicit $U \subseteq \{0,1\}^n$ with biclique-partition complexity $\kappa(U) = \Omega(n^k)$ for $k > 2$; for $k \ge 3$ such a bound would improve the best known lower bounds on boolean formula size. This question is likewise separate from the target here. These problems appear as Research Problems in Jukna's monograph Boolean Function Complexity (2012) and in his 2009 paper on set intersection representations of graphs. Historically, one attractive route toward covering-number lower bounds was the conjecture that every $K_{2,2}$-free bipartite graph $H$ of average degree $d$ has $bc(\bar{H}) \ge d^\varepsilon$ (equivalently $n^\varepsilon$); this was refuted, so any attack on the resistance problem must go beyond covering number alone. Convex complexity measures (Hrubeš, Jukna, Kulikov and Pudlák) are known to be bounded by $O(n^2)$, delimiting another family of insufficient techniques.

Problem Statement

Construct an explicit family of bipartite graphs $G_n \subseteq V_n \times W_n$ with $|V_n| = |W_n| = n$, together with a proof, such that the resistance $\rho(G_n) \ge n^\varepsilon$ for some constant $\varepsilon > 0$ independent of $n$. Here $\rho(G)$ is the smallest $r$ such that $G$ is the intersection (as edge sets) of $r$ bipartite graphs $G_1, \dots, G_r \subseteq V_n \times W_n$ on the same vertex set $V_n \cup W_n$, each having biclique covering number at most $r$; Jukna gives an equivalent characterization via $r \times r$ Boolean matrices assigned to vertices, with adjacency expressed by a matrix-product condition. 'Explicit' means the graph family is defined by a deterministic rule computable in time polynomial in $n$. That such a family would yield super-linear size lower bounds for boolean circuits of logarithmic depth is an established implication of Jukna. The related asymmetric-resistance and biclique-partition-complexity questions described in the Background are separate open questions of Jukna. The $K_{2,2}$-free covering-number hypothesis is false (refuted 2012/2022) and does not bound $\rho$. The problem is a pure mathematical construction-and-proof question; no experiments are required, and completion is a construction together with a correct proof that $\rho(G_n) \ge n^\varepsilon$ for some constant $\varepsilon > 0$.

References

1. S. Jukna and A. S. Kulikov. On covering graphs by complete bipartite subgraphs. Discrete Mathematics 309 (2009) 3399–3403. DOI: 10.1016/j.disc.2008.09.036. https://doi.org/10.1016/j.disc.2008.09.036
2. S. Jukna. On set intersection representations of graphs. Journal of Graph Theory 61(1) (2009) 55–75. DOI: 10.1002/jgt.20367. https://doi.org/10.1002/jgt.20367
3. N. H. Katz. On the CNF-complexity of bipartite graphs containing no squares. Lithuanian Mathematical Journal 52(4) (2012) 385–389. DOI: 10.1007/s10986-012-9181-5. Preprint arXiv:1206.6068, https://arxiv.org/abs/1206.6068
4. L. Hambardzumyan, H. Hatami and N. Ndiaye. On depth-3 circuits and covering number: an explicit counter-example. Preprint arXiv:2210.08300 (2022). https://arxiv.org/abs/2210.08300
5. S. Jukna. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics 27, Springer, 2012. DOI: 10.1007/978-3-642-24508-4. https://doi.org/10.1007/978-3-642-24508-4
6. P. Hrubeš, S. Jukna, A. Kulikov and P. Pudlák. On convex complexity measures. Theoretical Computer Science 411 (2010) 1842–1854. DOI: 10.1016/j.tcs.2010.02.004. https://doi.org/10.1016/j.tcs.2010.02.004. Preliminary version: ECCC Technical Report TR09-040 (2009), https://eccc.weizmann.ac.il/report/2009/040/
7. S. Jukna and G. Schnitger. Min-rank conjecture for log-depth circuits. Journal of Computer and System Sciences 77(6) (2011) 1023–1038. DOI: 10.1016/j.jcss.2009.09.003. https://doi.org/10.1016/j.jcss.2009.09.003. Preprint arXiv:1005.1009, https://arxiv.org/abs/1005.1009
8. P. Scharpfenecker. Bounded-depth succinct encodings and the structure they imply on graphs. Theory of Computing Systems 62 (2018) 1125–1143. DOI: 10.1007/s00224-017-9787-4. https://doi.org/10.1007/s00224-017-9787-4
9. S. Jukna. Computational complexity of graphs. In: Advances in Network Complexity, Wiley-VCH (2013), pp. 99–153. DOI: 10.1002/9783527670468.ch05. https://doi.org/10.1002/9783527670468.ch05