This seems like hard problem. Anyone has any suggestion how to tackle it?

Show that in a finite incidence geometry, the number of lines is greater than or equal to the number of points.

Printable View

- Feb 18th 2009, 09:13 PMnamelessguyIncidence geometry
This seems like hard problem. Anyone has any suggestion how to tackle it?

Show that in a finite incidence geometry, the number of lines is greater than or equal to the number of points. - Feb 18th 2009, 09:40 PMThePerfectHacker
Between any two distinct points there exists exactly one line. This is one of the axioms of incidence geometry. Now if there are $\displaystyle n$ points (and say $\displaystyle n\geq 2$) then the number of pairs that we can form is equal to $\displaystyle {n\choose 2}$ while the number of lines is $\displaystyle n$.

EDIT: Mistake - Feb 18th 2009, 09:58 PMnamelessguy
- Feb 19th 2009, 10:23 PMnamelessguy
@TPH, actually, I tried to draw some examples for some n points, but it appears that the number lines can be less that $\displaystyle {n\choose2}$. I guess it could be that $\displaystyle {n\choose2}$ is the maximum number of lines that we can get from n points. If this is the case, then I'm stuck again(Speechless)

- Feb 22nd 2009, 12:12 PMPlato
- Mar 13th 2009, 06:40 PMGeorge JenningsIncidence geometry: #lines >= #points
In an incidence geometry, two points are connected by exactly one line, there are (at least) three noncollinear points, and every line contains at least two points. In this context the de Bruijn-Erdos theorem (1948) says that there are at least as many lines as points. There's a proof in the text Combinatorics of Finite Geometries by Lynn Margaret Batten. One can also find proofs on the net by searching for "de Bruijn-Erdos theorem".

George