Point-hyperplane incidences

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $d\ge2$ and $n,m,s,t\in\mathbb N$. Let $P$ be a set of $n$ distinct points and $\mathcal H$ a set of $m$ distinct affine hyperplanes in $\mathbb R^d$. Their incidence graph is the bipartite graph with parts $P,\mathcal H$ and an edge $(x,H)$ exactly when $x\in H$. Its incidence count is \[ I(P,\mathcal H)=\#\{(x,H)\in P\times\mathcal H:x\in H\}. \] The graph is $K_{s,t}$-free if there do not exist $s$ distinct points and $t$ distinct hyperplanes such that all $st$ incidences occur. Here the part of size $s$ is the point part. Put \[ F_d(n,m;s,t)=\max\{I(P,\mathcal H):|P|=n,\ |\mathcal H|=m,\ G(P,\mathcal H)\text{ is }K_{s,t}\text{-free}\}. \] The maximum is over actual real point--hyperplane configurations; $0\le I\le nm$ makes the range finite.

Statement recorded in the supplied source.

Determine the maximum $F_d(n,m;s,t)$, in particular its sharp dependence on $n,m$ for fixed $d,s,t$. The distinguished case is \[ F_d(n,n;d,d), \] with equal numbers of points and hyperplanes and no $d$ points simultaneously incident to $d$ hyperplanes. Bounds for arbitrary bipartite graphs or for configurations over other fields do not by themselves determine this real-geometric maximum. [S2]

Short English statement

Find the largest number of incidences between real points and hyperplanes when specified complete bipartite subgraphs are forbidden, especially the balanced case with forbidden $K_{d,d}$.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3800005 (AMR-037-0005). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Aleksa Milojević, Benny Sudakov and István Tomon, Incidence bounds via extremal graph theory (2024), Introduction and §1.1, pp.1–4. https://arxiv.org/abs/2401.06670.