# Incidence geometry

• Feb 18th 2009, 09:13 PM
namelessguy
Incidence 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 PM
ThePerfectHacker
Quote:

Originally Posted by namelessguy
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.

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 PM
namelessguy
Quote:

Originally Posted by ThePerfectHacker
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\$.

Did you mean that the number pairs we can form is equal to \$\displaystyle {n\choose 2}\$ which is the number lines, while the number of points is only \$\displaystyle n\$? I did learn the axiom, and thanks a lot for your help TPH. It seems much easier.
• Feb 19th 2009, 10:23 PM
namelessguy
@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 PM
Plato
Quote:

Originally Posted by namelessguy
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.

That is truly the case.
Example: The Pappus finite geometry. In this geometry there are nine points and nine lines with 3 points on each line and 3 lines on each point.

Thus this problem depends on the set of axioms in use.
• Mar 13th 2009, 06:40 PM
George Jennings
Incidence 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