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

2010-08-16T19:35:53Z

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.

Answer by Andreas Blass for Upper bound on number of lines in a linear space given degree bounds

2010-08-17T13:50:52Z

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).

The obvious way to eliminate this and similar, larger counterexamples is to require that every line must contain at least two points.

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$).

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

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

Answer by Andreas Blass for Upper bound on number of lines in a linear space given degree bounds