Let $(S,mathcal{L})$ be a linear space and $q$ be a prime power such that
- Every point in $S$ lies on at most $q+1$ lines, and
- Every line in $mathcal{L}$ contains at most $q+1$ points, and at least 2 points (edited).
then for every point $e in S$, there are at most $q^2$ lines in $mathcal{L}$ not containing $e$.
edit - 'How do I prove the above?' is my question.
By 'linear space', I mean a pair $(S,mathcal{L})$ such that $S$ is a finite set of points, and $mathcal{L}$ is a set of subsets of $S$, or 'lines', so that any two points lie on a unique line, and any two distinct lines intersect in at most one point.
I arrived at this problem from matroid theory, but it's essentially a combinatorial problem about incidence structures, so I have phrased it as such.
The $q^2$ here is best possible - equality will hold when the linear space is a projective plane over a $q$-element field.
The De Bruijn-Erdos theorem, as well as various results from the literature on linear spaces, give lower bounds for numbers of lines, but I can't find upper bounds anywhere.
No comments:
Post a Comment