# Upper bound on number of lines in a linear space given degree bounds

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.

-
What is the question? – Felipe Voloch Aug 16 '10 at 20:53
I see nothing in the definition to disallow for any q the case of each line consisting of just 2 points. Then given n points there are $C(n,2)-(n-1)$ lines not containing a given point, and you can always take n large enough to make this exceed $q^2$. What am I missing? – Hugo van der Sanden Aug 17 '10 at 9:02
For $n > q+2$, that would violate the first condition (since every point would lie on $n-1 > q+1$ lines) – Klaus Draeger Aug 17 '10 at 9:36
Oops, I misread it, my apologies. – Hugo van der Sanden Aug 17 '10 at 10:21

I think the problem needs an additional non-degeneracy condition to prevent counterexamples like the following. Start with the Fano plane $F$ (i.e., the projective plane over the 2-element field --- it has 7 points and 7 lines) and define a new linear space having the same points as $F$ but having two sorts of lines: (1) all the lines of $F$ and (2) all the one-point subsets of $F$. Take $q=3$. Check that (a) every two points lie on a unique line (true in $F$ and the new lines don't affect it), (b) every two lines meet in at most one point (follows in general from (a)), (c) every point lies on at most $q+1=4$ lines (in fact exactly 4 --- 3 from $F$ plus one singleton), (d) every line contains at most 4 points (in fact, exactly 3 or 1), and (e) the number of lines not containing a given point $e$ is $10 > q^2$ (namely 4 lines of $F$ plus 6 of the 7 singletons).
For the sake of completeness (well, as much completeness as I can manage at the moment, since I can't answer the question when singleton lines are prohibited), let me mention that, if some line $L$ through $e$ meets all the other lines, then there are at most $q^2$ lines not through $e$. The reason is that each line $M$ not through $e$ must, by assumption, contain one of the points $p\in L-\{e\}$; there are only at most $q$ such points $p$, and each is on only at most $q$ lines other than $L$, by the hypotheses of the question. That makes at most $q^2$ possibilities for $M$ (since $M$, not passing through $e$, is certainly distinct from $L$).