Large incidence-free sets in geometries (Q1953330)

Summary: Let \(\Pi = (P,L,I)\) denote a rank two geometry. In this paper, we are interested in the largest value of \(|X||Y|\) where \(X \subset P\) and \(Y \subset L\) are sets such that \((X \times Y) \cap I = \emptyset\). Let \(\alpha(\Pi)\) denote this value. We concentrate on the case where \(P\) is the point set of \(\mathsf{PG}(n,q)\) and \(L\) is the set of \(k\)-spaces in \(\mathsf{PG}(n,q)\). In the case that \(\Pi\) is the projective plane \(\mathsf{PG}(2,q)\), where \(P\) is the set of points and \(L\) is the set of lines of the projective plane, Haemers proved that maximal arcs in projective planes together with the set of lines not intersecting the maximal arc determine \(\alpha(\mathsf{PG}(2,q))\) when \(q\) is an even power of 2. Therefore, in those cases, \[ \alpha(\Pi) = q(q - \sqrt{q} + 1)^2. \] We give both a short combinatorial proof and a linear algebraic proof of this result, and consider the analogous problem in generalized polygons. More generally, if \(P\) is the point set of \(\mathsf{PG}(n,q)\) and \(L\) is the set of \(k\)-spaces in \(\mathsf{PG}(n,q)\), where \(1 \leq k \leq n - 1\), and \(\Pi_q = (P,L,I)\), then we show as \(q \rightarrow \infty\) that \[ \frac{1}{4}q^{(k + 2)(n - k)} \lesssim \alpha(\Pi) \lesssim q^{(k + 2)(n - k)}. \] The upper bounds are proved by combinatorial and spectral techniques. This leaves the open question as to the smallest possible value of \(\alpha(\Pi)\) for each value of \(k\). We prove that if for each \(N \in \mathbb N, \Pi_N\) is a partial linear space with \(N\) points and \(N\) lines, then \(\alpha(\Pi_N) \gtrsim \frac{1}{e}N^{3/2}\) as \(N \rightarrow \infty\).