Friday, 6 January 2012

co.combinatorics - Upper bound on number of lines in a linear space given degree bounds

Let (S,mathcalL) 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 mathcalL contains at most q+1 points, and at least 2 points (edited).

then for every point einS, there are at most q2 lines in mathcalL not containing e.



edit - 'How do I prove the above?' is my question.



By 'linear space', I mean a pair (S,mathcalL) such that S is a finite set of points, and mathcalL 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 q2 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