Representation complexities of semialgebraic graphs

DOI10.1137/18M1221606MaRDI QIDQ5237912zbMATH OpenOpenAlexWikidataFDO

Authors Thao Do

Publication date 25 October 2019

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.08259

zbMATH Keywords

incidence geometryrepresentation complexitysemialgebraic graph and hypergraph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Abstract: The representation complexity of a bipartite graph $G=(P,Q)$ is the minimum size $su{m}_{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=cu{p}_{i=1}^s{A}_{i}imes{B}_i$ where $A_{i}subsetP,B_{i}subsetQ$ for $i=1,dots,s$. In this paper we prove that if $G$ is emph{semi-algebraic}, i.e. when $P$ is a set of $m$ points in $mathbb{R}^{d_1}$, $Q$ is a set of $n$ points in $mathbb{R}^{d_2}$ and the edges are defined by some semi-algebraic relations, the representation complexity of $G$ is $O(m^{frac{d}_1{d}_2-d_2{d}_1{d}_2-1+varepsilon}{n}^{frac{d}_1{d}_2-d_1{d}_1{d}_2-1+varepsilon}+m^{1+varepsilon}+n^{1+varepsilon})$ for arbitrarily small positive $varepsilon$. 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}^{frac{d}_1{d}_2-d_2{d}_1{d}_2-1+varepsilon}{n}^{frac{d}_1{d}_2-d_1{d}_1{d}_2-1+varepsilon}+u{m}^{1+varepsilon}+u{n}^{1+varepsilon})$. 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.

Recommendations

• A semi-algebraic version of Zarankiewicz's problem
• Zarankiewicz's problem for semilinear hypergraphs
• Ramsey-Turán numbers for semi-algebraic graphs
• Zarankiewicz's problem for semi-algebraic hypergraphs
• Ramsey properties of semilinear graphs

Cites work

• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• A semi-algebraic version of Zarankiewicz's problem
• An incidence theorem in higher dimensions
• Bisector energy and few distinct distances
• Can visibility graphs be represented compactly?
• Clique partitions, graph compression and speeding-up algorithms
• Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
• Cutting algebraic curves into pseudo-segments and applications
• Density and regularity theorems for semi-algebraic hypergraphs
• Efficient algorithms for approximating polygonal chains
• Extremal problems in discrete geometry
• scientific article; zbMATH DE number 3841905 (Why is no real title available?)
• scientific article; zbMATH DE number 3223507 (Why is no real title available?)
• Incidences of not-too-degenerate hyperplanes
• Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances
• Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
• Lower bounds for incidences with hypersurfaces
• On a problem of K. Zarankiewicz
• On counting point-hyperplane incidences
• On range searching with semialgebraic sets. II.
• On the Betti Numbers of Real Varieties
• On the Erdős distinct distances problem in the plane
• On the number of cells defined by a family of polynomials on a variety
• On the Number of Incidences Between Points and Curves
• Ramsey-type results for semi-algebraic relations
• Zarankiewicz's problem for semi-algebraic hypergraphs

Cited in

(11)

• Implicit representation conjecture for semi-algebraic graphs
• A semi-algebraic version of Zarankiewicz's problem
• Zarankiewicz's problem for semilinear hypergraphs
• scientific article; zbMATH DE number 7324138 (Why is no real title available?)
• Zarankiewicz's problem via -t-nets
• Semi-algebraic off-line range searching and biclique partitions in the plane
• On the number of incidences when avoiding an induced biclique in geometric settings
• Semi-algebraic off-line range searching and biclique partitions in the plane
• On Zarankiewicz's problem for intersection hypergraphs of geometric objects
• Compact representation of semilinear and terrain-like graphs
• On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers

This page was built for publication: Representation complexities of semialgebraic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5237912)