The largest complete bipartite subgraph in point-hyperplane incidence graphs (Q2288177): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Covering lattice points by subspaces and counting point-hyperplane incidences / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On counting point-hyperplane incidences / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Incidences of not-too-degenerate hyperplanes / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Two theorems on point-flat incidences / rank | |||
Normal rank | |||
Latest revision as of 11:17, 21 July 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The largest complete bipartite subgraph in point-hyperplane incidence graphs |
scientific article |
Statements
The largest complete bipartite subgraph in point-hyperplane incidence graphs (English)
0 references
17 January 2020
0 references
Summary: Given \(m\) points and \(n\) hyperplanes in \(\mathbb{R}^d\) \((d\geqslant 3)\), if there are many incidences, we expect to find a big cluster \(K_{r,s}\) in their incidence graph. \textit{R. Apfelbaum} and \textit{M. Sharir} [SIAM J. Discrete Math. 21, No. 3, 707--725 (2007; Zbl 1141.05040)] found lower and upper bounds for the largest size of \(rs\), which match (up to a constant) only in three dimensions. In this paper we close the gap in four and five dimensions, up to some polylogarithmic factors.
0 references
incidences
0 references
hyperplanes
0 references
incidence graph
0 references
