REPRESENTATION COMPLEXITIES OF SEMIALGEBRAIC GRAPHS.

The representation complexity of a bipartite graph G = (P;Q) is the minimum size s i=1(jAij + jBij) over all possible ways to write G as a (not necessarily disjoint) union of complete bipartite subgraphs G = [si =1Ai = Bi where Ai = P;Bi = Q for i = 1;:::; s. In this paper we prove that if G is semialgebraic, i.e., when P is a set of m points in Rd1, Q is a set of n points in Rd2, and the edges are defined by some semialgebraic relations, the representation complexity of G is O(m d1d2-d2 d1d2-1 +" n d1d2-d1 d1d2-1 +" + m1+" + n1+") for arbitrarily small positive ". This generalizes results by Apfelbaum{Sharir and Solomon{Sharir. As a consequence, when G is Ku;u-free for some positive integer u, its number of edges is O(um d1d2-d2 d1d2-1 +" n d1d2-d1 d1d2-1 +" + um1+" + un1+"). This bound is stronger than a result of Fox, Pach, Sheffer, Suk, and Zahl when the first term dominates and u grows with m; n. Another consequence is that we can find a large complete bipartite subgraph in a semialgebraic graph when the number of edges is large. Similar results hold for semialgebraic hypergraphs. [ABSTRACT FROM AUTHOR]