A note on the largest bipartite subgraph in point-hyperplane incidence graphs

2018/10/03 by T. Thao, Do, Thao T.
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1810.01551

openalex publication_date 2018/10/03 · openalex created_date 2018/10/12 · openalex updated_date 2026/07/28

Abstract

Given m points and n hyperplanes in ℝ^d, if there are many incidences, we expect to find a big cluster K_r,s in their incidence graph. Apfelbaum and Sharir found lower and upper bounds for the largest size of rs, which only match in three dimensions. In this paper we close the gap in four and five dimensions, up to some logarithmic factors.

Citations

• Two theorems on point-flat incidences

Related

• Incidence bounds via extremal graph theory
• On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings
• Lower bounds for incidences with hypersurfaces
• On the extremal number of incidence graphs
• Incidences with curves in R^d