Representation Complexity of Semi-algebraic Graphs

2017/09/24 by Thao Do, Do, Thao
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1709.08259

openalex publication_date 2017/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The representation complexity of a bipartite graph G=(P,Q) is the minimum size ∑_i=1^s (|A_i|+|B_i|) over all possible ways to write G as a (not necessarily disjoint) union of complete bipartite subgraphs G=∪_i=1^s A_i× B_i where A_i⊂ P, B_i⊂ Q for i=1,…, s. In this paper we prove that if G is semi-algebraic, i.e. when P is a set of m points in ℝ^d₁, Q is a set of n points in ℝ^d₂ and the edges are defined by some semi-algebraic relations, the representation complexity of G is O( m^{(d₁d₂-d₂)/(d₁d₂-1)+ε} n^{(d₁d₂-d₁)/(d₁d₂-1)+ε}+m^1+ε+n^1+ε) for arbitrarily small positive ε. This generalizes results by Apfelbaum-Sharir and Solomon-Sharir. As a consequence, when G is K_u,u-free for some positive integer u, its number of edges is O(u m^{(d₁d₂-d₂)/(d₁d₂-1)+ε} n^{(d₁d₂-d₁)/(d₁d₂-1)+ε}+ u m^1+ε+u n^1+ε). This bound is stronger than that 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 semi-algebraic graph when the number of edges is large. Similar results hold for semi-algebraic hypergraphs.

Citations

• On extremal problems of graphs and generalized graphs
• Incidences between points on a variety and planes in R³

Related

• Algorithmic Complexity of Weakly Semiregular Partitioning and the\n Representation Number
• A semi-algebraic version of Zarankiewicz's problem
• Some Quantitative Results in Real Algebraic Geometry
• On the Conjecture of the Representation Number of Bipartite Graphs
• Semi-algebraic colorings of complete graphs