Ordered biclique partitions and communication complexity problems

An ordered biclique partition   of the complete graph KnKn on nn vertices is a collection of bicliques (i.e., complete bipartite graphs) such that (i) every edge of KnKn is covered by at least one and at most two bicliques in the collection, and (ii) if an edge ee is covered by two bicliques then each endpoint of ee is in the first class in one of these bicliques and in the second class in other one. In this note, we give an explicit construction of such a collection of size n1/2+o(1)n1/2+o(1), which improves the O(n2/3)O(n2/3) bound shown in the previous work (Amano, 2014).As the immediate consequences of this result, we show (i) a construction of n×nn×n 0/1 matrices of rank n1/2+o(1)n1/2+o(1) which have a fooling set of size nn, i.e., the gap between rank and fooling set size can be at least almost quadratic, and (ii) an improved lower bound (2−o(1))logN(2−o(1))logN on the nondeterministic communication complexity of the clique vs. independent set problem, which matches the best known lower bound on the deterministic version of the problem shown by Kushilevitz et al. (1999).