Large incidence-free sets in geometries
type: Item
instance of: scholarly article
title: Large incidence-free sets in geometries
zbMATH Open document ID: 1266.51004
published in: The Electronic Journal of Combinatorics
publication date: 2013-06-07T00:00:00Z
full work available at URL: v19i4p24
review text: 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\).
Mathematics Subject Classification ID: 51E12
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 05D40
zbMATH DE Number: 6171807
zbMATH Keywords: eigenvalues
zbMATH Keywords: generalized polygons
zbMATH Keywords: probabilistic method
author: Stefaan De Winter
author: Jeroen Schillewaert
author: J. Verstraëte
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6171807