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.

  • $\begingroup$ What is the question? $\endgroup$ – Felipe Voloch Aug 16 '10 at 20:53
  • $\begingroup$ 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? $\endgroup$ – Hugo van der Sanden Aug 17 '10 at 9:02
  • $\begingroup$ For $n > q+2$, that would violate the first condition (since every point would lie on $n-1 > q+1$ lines) $\endgroup$ – Klaus Draeger Aug 17 '10 at 9:36
  • $\begingroup$ Oops, I misread it, my apologies. $\endgroup$ – 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).

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

  • $\begingroup$ You're right. I have been thinking about this matroidally, and such conditions come for free in that setting so it didn't occur to me to include them. Your observation is right. In particular, any line L of length q+1 must meet all other lines (otherwise, any point on a line L' that does not meet L lies on q+2 lines - L' itself, and one line for each point on L), and by applying pigeonhole to points on L, we can find a point on L lying on at least q+1 lines not containing e, and therefore at least q+2 lines. So WMA that each line contains at most q points. I don't know how useful this is. $\endgroup$ – Peter Nelson Aug 18 '10 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.