Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I just read a very short paper on the De Bruijn-Erdos theorem. It essentially states that if we have $n$ points and $m$ lines, where any two points lie on a line, and each line has at least two points, then there are at least as many lines as points.

The proof is in this short paper. It is stated at the very top, and the proof I'm curious about begins in the middle of page 2 and ends at the top of page 3. I don't quite follow the inequalities $$ s_j\leq k_n\ \text{for}\ j>\nu $$ that are found at the very top of page 3. Why would that fact that an index $j$ being greater than the minimum number of lines passing through a given point require that the number of points on that indexed line is at most the number of lines passing through that point? Apart from that I follow the rest. Does it violate one of the assumptions about the space? Thanks.

share|cite|improve this question
I apologize for the lack of a direct link to the paper, the computer I'm on requires that pdfs be downloaded directly, and not in the browser. – user6644 Feb 5 '11 at 1:53

All the inequalities in (3) are derived from (2). The first $\nu$ inequalities, up to the semicolon, follow because $a_i$ is not on $A_j$ for $i\neq j$, $i \leq \nu$, $j \leq \nu$. The remaining inequalities, $s_k \leq k_n$ for $j > \nu$, follow because $A_1$, $A_2$, ..., $A_\nu$ are the lines through $a_n$, and hence $a_n$ is not on $A_j$ for $j > \nu$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.