Geometric Structures: Session 6: Finite Planes and Trees
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
malkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
Session 6
Finite Geometries
Euclid laid down the ideas for axiomatic "synthetic" Euclidean geometry over 2000 years ago, and Fermat and Descartes showed how to think of Euclidean geometry in algebraic terms using what today we call analytical geometry.
Synthetic finite geometries did not really make an appearance until the late 1800's.(One pioneer was the mathematician Gino Fano, sons are the famous physicist and electrical engineer (MIT).) However, by the time finite geometries were developed, there was a way, using an historical point of view, to construct such geometries by analogy with what is done in analytical geometry. This approach makes a very nice hands on way to treat geometries with unique parallels (like Euclidean geometry- affine geometry) and geometries that have no parallels (like the real projective plane) while reinforcing ideas that come up in high school or undergraduate mathematics education.
Thus, we can construct a finite affine geometry of order n (e.g. n points on every line) as follows:
points: (a,b) where a and b are chosen as elements from an n element finite arithmetic, the integers mod p, or more generally the Galois Field of order pk where p is a prime and k a positive integer.
lines: equations of the form ax +by + c = 0 where a,b, are not both 0 and are chosen from a finite field as above.
A point P is on a line l, as "usual" if the coordinates of the point satisfy the equation of the line.
Now, we can construct a finite projective plane of order n, with n + 1 points on every line, in exactly the same way that we constructed the real projective plane from the Euclidean plane. We take each parallel class in the affine plane and add one point to each of the the lines in a parallel class. All these newly added points are placed on one line, which is referred to as the line at infinity. In the analytical version, we have points with coordinates (a, b, c ) where a, b, c are not all zero, and where two points are the same if they arise from each other by multiplying by a nonzero constant. Lines have the form ax +by +cz =0 and where a, b, and c are chosen from a Galois Field.
To find the line through a pair of points, where two lines intersect, the equation of a line through a point which is parallel to a given line, or if three lines are concurrent, we use the same ideas that we use in Calculus! (In particular we can use the determinant formula for the equation of a line, and in the projective plane we can use determinants to write down the equation of a point. This can be used to find the coordinates of the intersection of two projective lines.) The reason we can do this is that all the work in Calculus (analytical geometry more precisely) is based on the algebraic properties of the real numbers and the elements of a Galois Field share these properties, even though they lack the order properties of the real numbers.
Using some simple reasoning we can show that a finite affine plane of order n has:
n2 points
n2 + n lines
n points on every line
n + 1 lines through every point (if P is not on line l the lines through P will intersect some other line m in n points and there will be one extra line which is parallel to l)
Similarly, the finite projective plane of order n has:
n2 + n + 1 points
n2 + n + 1 lines
n + 1 points on a line
n + 1 lines through a point
Note, that in the projective plane case the roles of point and line are interchangeable. Thus, illustrating the elegant duality present in projective planes.
For the particular projective planes created in the way above (e.g. using elements from a finite field), Desargues Theorem holds. Note, however, that there are finite projective planes which also have prime power order for which Desargues Theorem fails. (The Moulton Plane is an example of such a plane in the infinite case.) This means that there is no way to introduce coordinates into such planes so that the coordinates form a field. However, algebraists have constructed interesting algebraic systems that can serve as coordinates for such planes. (Some of these steps were taken by the American mathematician Marshall Hall, who was most famous for his work in group theory.) This interaction between algebra and geometry has mutually benefited both of these branches of mathematics.
A major open problem in geometry is whether or not there can be finite affine (or projective planes) of nonprime power order. It is known via a theorem of Richard Bruck and Herbert Ryser that there are infinitely many nonprime powers which can not be the order of a finite plane but this theorem still leaves infinitely many nonprime power orders for which it is unknown whether or not a finite plane exists. Using a computer calculation it has been shown that there is no projective plane of order 10.
For the case of finite hyperbolic planes much less is known. In fact, the few examples of finite hyperbolic planes that are known are not known to have connections in any obvious way with either finite affine or projective planes. The theory of block designs, which are important in experimental design (statistics) includes questions of the existence of block designs with particular parameters. Interestingly, some of the small block designs whose existence is not yet known, where they to be found, would be new examples of finite hyperbolic planes.
Trees
If T is a tree with n vertices then T has (n-1) edges
can be proved using mathematical induction.
Before starting the proof, recall some basic graph theory definitions and facts:
1. Definition: A tree is a connected graph which has no circuits.
2. Theorem: If T is a tree different from K1 (i.e. not a single dot), then T has at least two vertices which have degree 1 (i.e. 1-valent).
Let s(n) be the statement: A tree with T with n vertices has (n-1) edges.
s(1) requires that a tree with 1 vertex has 0 edges. There is only one such graph, a graph with a single dot. This has no edges. Therefore, s(1) is a true statement
Note that s(2) also is true. S(2) states that a tree with two vertices has one 1 edge. There is only one such tree, K2 (a pair of vertices jointed by an edge) which has 1 edge.
We will now assume that s(k) is true.
Namely, if T is a tree with k vertices then T has k-1 edges.
Now, let T* be any tree with k+1 vertices (k greater than or equal to 1). We know that T*, since it has at least 2 vertices, has a vertex, call it w, of degree 1. (The one edge at w has another vertex v, which is part of the tree.)
(Although the argument being given does not depend on a diagram many of you may like to refer to the diagram below, which represents T*.)
Now let T=T*-w, the graph obtained from T* by deleting the vertex w. T has no circuits, is connected, and, thus, is a tree with one less vertex than T*, namely, k vertices. Now using the italicized statement above (known as the inductive or induction hypothesis) we conclude, since T has k vertices that it has k-1 edges. (Below is the picture of T for the case where T* is the tree above.)
What does this tell us about T*? To get from T back to T* we have to put back the edge we removed, the edge vw. Thus, T* has exactly one more edge than T, and since T has k-1 edges we conclude that T* must have k edges. Thus, we have shown (using the inductive hypothesis) that any tree of k+1 vertices has k edges. Thus s(k) was used to prove s(k+1).
Hence, we can conclude using the Principle of Mathematical Induction that s(n) is true for all values of n.
Remember what the Principle of Mathematical Induction says is:
a. if s(n0) is true
and
b. if s(k) implies s(k+1) (for k greater than or equal to n0)
then
s(n) is true for all n.
In order to show that a tree with at least two vertices has 1-valent vertices we can use the idea of graph distance:
Given two vertices u and v in a connected graph, the distance between u and v is the number edges in a path from u to v which has the smallest number of edges.
Distance problems in graphs lead to many interesting problems that are the analogues of problems from "continuous" geometry. One famous problem in Euclidean geometry asks for the point with a triangle such that the sum of the distances to the vertices of the triangle is a minimum. This point might be a good choice for a "facility" such a place to locate a flea market (hospital, etc.) F which could be walked to from the vertices of the triangle. (Of course such conceit is not likely to be practical since typically one could not walk or drive from the vertices of the triangle to F via straight line routes.)
In graph theory there are two natural facility location "models," for a connected graph.
Center of a graph: The center of a graph G consists of the subgraph of G induced by the set of vertices of G with minimal eccentricity. (The eccentricity of a vertex v is the distance v has from the vertices that are farthest (graph distance) from it.
Median of a graph: The median of a graph G consists of the subgraph of G induced by those vertices which minimize the sum of the distances to all the other vertices of the graph.
Theorem:
The center of a tree consists either of a single vertex or a single edge.
Theorem:
The median of a tree consists of either of a single vertex or a single edge.
Both of these theorems are due to the topologist Camille Jordan (1838-1922), for whom the Jordan Curve Theorem is named.