On the CNF-complexity of bipartite graphs containing no $K_{2,2}$'s
  By a probabilistic construction, we find a bipartite graph having average degree $d$ which can be expressed as a conjunctive normal form using $C \log d$ clauses. This contradicts research problem 1.33 of Jukna. 
Nets Hawk Katz
cs.CC cs.DM math.CA math.CO