2013/11/25 by Manami Shigeta, Shigeta, Manami, Kazuyuki Amano +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1311.6192
openalex publication_date 2013/11/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An ordered biclique partition of the complete graph Kn on n vertices is a collection of bicliques (i.e., complete bipartite graphs) such that (i) every edge of Kn is covered by at least one and at most two bicliques in the collection, and (ii) if an edge e is covered by two bicliques then each endpoint of e 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), which improves the O(n2/3) bound shown in the previous work [Disc. Appl. Math., 2014]. As the immediate consequences of this result, we show (i) a construction of n × n 0/1 matrices of rank n1/2+o(1) which have a fooling set of size n, 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)) log N 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, Linial and Ostrovsky [Combinatorica, 1999].