Geodesic
The largest complete bipartite subgraph in point-hyperplane incidence graphs
Thao Do1
1MIT
The electronic journal of combinatorics, Tome 27 (2020) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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. Apfelbaum and Sharir 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.
DOI : 10.37236/8253
Classification : 05C35, 52C10, 05D10
Mots-clés : incidences, hyperplanes, incidence graph

Thao Do  1

1 MIT 
@article{10_37236_8253,
     author = {Thao Do},
     title = {The largest complete bipartite subgraph in point-hyperplane incidence graphs},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {1},
     doi = {10.37236/8253},
     zbl = {1431.05087},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8253/}
}
TY  - JOUR
AU  - Thao Do
TI  - The largest complete bipartite subgraph in point-hyperplane incidence graphs
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8253/
DO  - 10.37236/8253
ID  - 10_37236_8253
ER  - 
%0 Journal Article
%A Thao Do
%T The largest complete bipartite subgraph in point-hyperplane incidence graphs
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8253/
%R 10.37236/8253
%F 10_37236_8253
Thao Do. The largest complete bipartite subgraph in point-hyperplane incidence graphs. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8253

Cité par Sources :