Upper bound on number of lines in a linear space given degree bounds - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:27:43Z http://mathoverflow.net/feeds/question/35787 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35787/upper-bound-on-number-of-lines-in-a-linear-space-given-degree-bounds Upper bound on number of lines in a linear space given degree bounds Peter Nelson 2010-08-16T19:35:53Z 2010-08-18T14:28:20Z <p>Let $(S,\mathcal{L})$ be a linear space and $q$ be a prime power such that </p> <ul> <li>Every point in $S$ lies on at most $q+1$ lines, and </li> <li>Every line in $\mathcal{L}$ contains at most $q+1$ points, and at least 2 points <strong>(edited)</strong>.</li> </ul> <p>then for every point $e \in S$, there are at most $q^2$ lines in $\mathcal{L}$ not containing $e$. </p> <p><strong>edit</strong> - 'How do I prove the above?' is my question. </p> <p>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. </p> <p>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. </p> <p>The $q^2$ here is best possible - equality will hold when the linear space is a projective plane over a $q$-element field. </p> <p>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. </p> http://mathoverflow.net/questions/35787/upper-bound-on-number-of-lines-in-a-linear-space-given-degree-bounds/35871#35871 Answer by Andreas Blass for Upper bound on number of lines in a linear space given degree bounds Andreas Blass 2010-08-17T13:50:52Z 2010-08-17T13:50:52Z <p>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). </p> <p>The obvious way to eliminate this and similar, larger counterexamples is to require that every line must contain at least two points. </p> <p>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 <code>$p\in L-\{e\}$</code>; 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$).</p>