Geometric Structures (Notes)

Prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

email:

web page:

The materials below were developed for both graduate and undergraduate courses taught under the title "Geometric Structures." The philosphy of these courses is to cover as broad a range of topics with a geometrical flavor as possible. It it generally easier to get a deeper knowledge of a subject X where one has seen the key ideas and some of the major results than it is to start off reading in a book devoted only to the content of topic X.

--------------------------------------------------------------------------------

Generic Syllabus

Syllabus

-------------------------------------------------------------------------------

Syllabus for Spring, 2012

2012 Syllabus for Geometric Structures

-------------------------------------------------------------------------------

Some new materials added for Spring, 2012.

-------------------------------------------------------------------------------

Here is a very brief treatment of the "classical" terms for convex quadrilaterals (rhombus, kite, square, rectangle, etc.) together with references for using a very different approach based on partitions of the integer 4.

Convex Quadrilaterals

-------------------------------------------------------------------------------

This "summary" of information about going between the Euclidean plane and the real projective plane shows a determinant approach to writing doing the equation of a line in the Euclidean plane and the real projective plane. It also shows, via duality, that in the real projective plane the roles of point and line can be interchanged, and how to use coordinates for lines and equations for points! This means that in practice the same calculations can be used to see if three points are collinear or three lines are concurrent in the real projective plane, as well as writing down the coordinates of the point where two lines intersect or the equation of the line which goes through two points.

A determinant approach to going between the Euclidean and real projective plane -equations for points and coorinates for lines

--------------------------------------------------------------------------------

One of the most lovely theorems of projective geometry is Desargues Theorem, due to Girard Desargues. Desargues Theorem holds in the real projective plane and in finite projective planes which arise using coordinates from finite fields. Material related to these finite fields or arithmetics, also know as Galois Fields, and the geometries that can be constructed using them can be found in the links below. The big idea here is to imitate the way points and lines were treated in Calculus in developing the analytical geometry of the Euclidean plane and the way we extended this to the real projective plane using homogenous coordinates. To get larger Galois fields than the ones obtained from the integers mod p, where p is a prime, one imitates the way that the complex numbers are obtained from the real numbers.

Finite Fields

More About Finite Fields

Finite Arithmetics

Desargues Theorem

Diagram Illustrating Desargues Theorem

Construction of a larger finite arithmetic from a smaller such arithmetic

Essay about finite geoemetres including a discussion of Pascal's and Desargues Theorems

Material about the "combinatorics" of finite geoemtries (and unconnected material about trees)

--------------------------------------------------------------------------------

It turns out that one can construct infinitely many finite affine and projective planes using the ideas you learned about in analysical geometry for the Euclidean plane, but transfered to the world of finite arithmetics or finite fields. These fields are also known as the Galois fields. Below there are materials related to this as well as practice problems that involve the real projective plane and finite planes as well.

Problems involving the real projective plane

Congruence Primer

--------------------------------------------------------------------------------

Here are some notes/articles that treat issues related to affine, projective, and hyperbolic planes. Both the finite and infinite cases are discussed. Finite planes have many applications including to the design of statistical experiments.

Notes on differents types of geometries 1

Notes on differents types of geometries 2

Notes on differents types of geometries 3

Notes on differents types of geometries 4

Notes on differents types of geometries 5

American Mathematical Society Feature Column article about Finite Geometries

--------------------------------------------------------------------------------

Here are a few more additional final examination review problems.

More Final Review Problems

--------------------------------------------------------------------------------

Here are practice problems for a "typical" final examination for a Geometric Structures course. To do all of these problems will take a lot of time but the goal is to give samples of the kinds of things that could be asked.

Review for a Final Examination

--------------------------------------------------------------------------------

Sheet N offers the chance to practice the skill of drawing the dual graph, medial graph, line graph, and replace an edge by a hexagon for some small plane connected graphs.

Medial and Line Graphs (Practice)

--------------------------------------------------------------------------------

Here is more information about Steintiz's Theorem (when is the graph the vertex-edge graph of a 3-dimensional convex polyhedron) and the symmetry of graphs (called automorphisms) and their geometrical realizations by metrical (distance preserving) objects (polygons or polyhedra).

Information about Steinitz's Theorem and Mani's Theorem

--------------------------------------------------------------------------------

Sheet M is a brief note about planar graphs and the maps they create when they are drawn in the plane. The issue being the distinction between graphs which are isormorphic or not, and the maps they give rise to.

Example: Graphs, Maps, and Isomorphism

--------------------------------------------------------------------------------

Sheet L has some practice problems involving the floor and ceiling functions and the use of the summation sign.

Ceiling and Floor Function and Summation

--------------------------------------------------------------------------------

Mathematical Induction is one of the most important tools that mathematicians have for proving statements that are parameterized by some positive integer variable n. While Mathematical Induction does not always seem satisfying, in many geometrical problems where it can be used, often one can see the geometric issue for going from the case of k to k + 1. Here are some links for notes and problems involving Mathematical induction:

Brief Essay on Mathematical Induction

Some Sample Induction Problems to practice on

Often theorems that can be proved by mathematical induction can also be proved using "proofs without words." In such proofs one substitutes some appropriate physical model such as area or arrays of dotes to see that certain statements are really true. Claudi Alsina and Roger Nelson have written a collection of wonderful books that exploit this approach to insight into mathematical statemeents. Happily Alsina and Nelson usually provide the words necessary to use the diagrams they call attention to that are needed to "see" the proof.

Proof Without Words

--------------------------------------------------------------------------------

Sheet K is a brief note about how to extend the Art Gallery Theorem to another special kind of polygon known as an orthogonal polygon.

Note About the Art Gallery Theorem

--------------------------------------------------------------------------------

This set of problems involves primarily coloring problems with some other graph theory ideas thrown in.

Problems involving plane graphs, visibility and distances

--------------------------------------------------------------------------------

Here is a discussion of coloring problems and their applications, with an emphasis on vertex coloring problems. This essay originally appeared as a web based Feature Column for the American Mathematical Society in 2003.

Applications of Vertex Coloring

--------------------------------------------------------------------------------

This essay contains information about the medians, altitudes, perpendicular bisectors, and angle bisectors of a triangle. Brief mention is made of the circumcircle and incirle of a triangle and of Ceva's Theorem which gives necessary and sufficient conditions for three lines through the vertices of a triangle to be concurrent (meet at a point).

Lines Which are Concurrent for a Triangle

--------------------------------------------------------------------------------

Here are some notes about the fact that plane graphs which have hamiltonian circuits can have their faces colored with 4 or fewer colors. The actual chromatic number of a specific plane graph will be 4 or less by the Haken-Appel 4-color theorem.

Coloring the faces of plane graphs with hamiltonian circuits

--------------------------------------------------------------------------------

Sheet J has notes about mathematical induction one of the most powerful and important tools for proving mathematical theorems. Here the emphasis is on using induction to prove results in graph theory.

Mathematical Inducation Especially as Applied to Graph Theory Results

--------------------------------------------------------------------------------

Sheet I has notes about obtaining graphs from other graphs. There is a discussion of line graphs and medial graphs. The emphasis is on obtaining a new plane graph from a plane graph as was done in computing the geometric dual of a graph.

Obtaining New Graphs from Old Graphs

--------------------------------------------------------------------------------

This set of problems involves doing problems involving valence and degree sequences, visibility for polygons, and distances (Euclidean and taxicab).

Problems involving plane graphs, visibility and distances

--------------------------------------------------------------------------------

Sheet H has some practice problems involving the ideas of verex coloring, face coloring, and edge coloring.

Vertex Coloring, Face Coloring, and Edge Coloring

--------------------------------------------------------------------------------

Sheet G has some practice problem and notes involving the interior angles of polygons, diagonals of polygons, triangulations, and near-triangulations.

Interior Angles of Polygons, Diagonals of Polygons, Triangulations, and Near Triangulations

--------------------------------------------------------------------------------

This essay is another in the series that emphasizes the mathematical importance of thinking of things as being the same or different. Here the comparison and contrast is between graph, plane graph, polygon, polyomino and net. Also some information about Alexandrov's Theorem is discussed.

Graphs, Polygons, Polyominoes and Nets

--------------------------------------------------------------------------------

I strongly believe that teaching using contexts, showing the applicability of mathematics, is extremely important. The essay below comments on this as well as making some comments on matters such as the difference between exercises, problem solving, modeling, etc. Showing contexts for geometry problems is no less important than finding contexts for other types of mathematical issues. Here the prime example is a "bankruptcy problem" a topic that comes up in the mathematical analysis of fairness questions.

Some thoughts on contexts, exercises, problem solving and mathematical modeling

--------------------------------------------------------------------------------

Sheet F has some practice problems involving the ideas of verex coloring, cut vertices and cut edges, and distance and eccentricity in a graph.

Vertex Coloring and Graph Distance

--------------------------------------------------------------------------------

Sheet E has notes about moving around in a graph in an operations research kind of context. Thus, it mentions Eulerian circuits and paths and Hamiltonian circuits and paths. There are a variety of practice problems to help one understand the differences between these kinds of "routes" and how to find them.

Getting Around in Graphs

--------------------------------------------------------------------------------

This item suggests an exploration involving the overlap of two rhombuses. It might serve for a course project for someone who finds it an interesting environment to investigate.

Overlapping polygons

--------------------------------------------------------------------------------

Sheet D has notes about the nature of geometry - being a branch of mathematics as well as physics, and some graph theory connections between polygons, polyhedra, and another geometric structure known as polyominoes. Some nets can be thought of as arising from a polyhedron by cutting edges but also one can adopt a folding point of view and ask about polyhedra that can be folded from polyominoes.

Polygons, Polyhedra, Nets and Graphs

--------------------------------------------------------------------------------

Sheet C has some practice problems involving basic ideas in graph theory, including including Euler circuits, and some material about the Chinese Postman. The Operations Research version of this problem can be applied to snow removal, garbage collection, mail delivery, and salt spreading.

Sheet C: Euler circuits and the Chinese Postman Problem

--------------------------------------------------------------------------------

This set of problems involves drawing the nets of a 3-cube and indicating the trees that give rise to the different nets. There are also problems about degree (valence) sequences of graphs to give practice with basic graph theory ideas and the idea of isomorphism of graphs.

Problems involving nets and graphs

--------------------------------------------------------------------------------

Given a set of points in the plane S the Voronoi diagram determined by S is the collection of lines and cells which show points closer (in Euclidean distance) to a specific point of S than to any other point in S. Here is a nice "applet" for doing experiments involving Vononoi diagrams. The points you start with can be dragged and additional points added (right click a point to remove it).

Applet for Experiments with Voronoi diagrams

--------------------------------------------------------------------------------

Sheet B has some practice problems involving basic ideas in graph theory, including the idea of a degree sequence or a valence sequence. There is also a very brief primer of graph theory.

Sheet B: Basic Graph Theory and Degree Sequences

--------------------------------------------------------------------------------

Sheet A has some remarks about nets in general and questions about the bipyramid and its nets.

Sheet A: Nets of the Bipyramid

--------------------------------------------------------------------------------

Here in an activity that involves a variety of traditional issues (e.g. area and perimeter) but arises from a problem dealing with folding a rectangle (a special case of Alexandrov's Theorem).

Activity Involving Folding a Rectangle

--------------------------------------------------------------------------------

Description of project for Geometric Structure Course (2012)

Project: Geometric Structures 2012

--------------------------------------------------------------------------------

Some new materials added for Spring, 2011.

-------------------------------------------------------------------------------

Some thoughts about the issue of Standards based curriculum and the teaching of geometry, and implications of Euler's polyhedral formula.

Geometry, New Geometry, and What We Teach

--------------------------------------------------------------------------------

Knots are a familiar geoemtric structure that rarely get the attention they deserve in courses in geometry. This short note talks about knots, graph theory, and representing knots with sticks.

Knots, Graphs, and Sticks

--------------------------------------------------------------------------------

Some notes about affine and projective planes, including a brief account of Desargues's Theorem.

Projective and Affine Geometry and Desargues's Theorem

--------------------------------------------------------------------------------

Review problems for a final examination in Geometric Structures.

Final Examination Review

--------------------------------------------------------------------------------

Here are some practice problems involving ideas relating the Euclidean plane to the real projective plane:

Practice Problems involving the real projective plane

Practice Problems involving the real projective plane including material about determinants

--------------------------------------------------------------------------------

Some notes about finite planes and how to construct a projective plane from an affine plane.

How to Construct a Projective Plane from an Affine Plane

--------------------------------------------------------------------------------

For those individuals who are rusty (or never learned) about congruences (modular arithmetic) this very skeletal account may be of use. We will need these ideas to help us introduce coordinates into finite affine and finite projective planes.

Congruence Primer

-------------------------------------------------------------------------------

Some notes about axiom systems for geometry, and an analogy between the rules of games in sports and axiom systems. There is a brief treatment of finite planes.

Axiom Systems, Rules of Games in Sports, and Finite Geometries

--------------------------------------------------------------------------------

Here is a set of "homework" problems, dealing with various aspects of graph thoery.

Homework 3

-------------------------------------------------------------------------------

Here are some practice problems involving basic graph theory concepts.

Some Problems G (Basic Graph Theory)

--------------------------------------------------------------------------------

Some notes about Euler's formula, Eberhard's Theorem, and polytopal graphs:

Euler's Formula, Eberhard's Theorem, Polytopal Graphs

--------------------------------------------------------------------------------

Some notes about how to generate new graphs from old graphs, especially in the plane graph case:

New Graphs from Old Ones

--------------------------------------------------------------------------------

Here are some practice problems involving the basic graph theory concepts of vertex, edge, and face colorings.

Some Problems F (Basic Graph Theory - Vertex, Face and Edge Colorings)

--------------------------------------------------------------------------------

Some notes about using mathematical induction, in particular, in proving theorems in geometry:

Mathematical Induction

--------------------------------------------------------------------------------

Here are some typical problems involving mathematical induction is you would like to practice your skills with using this proof tool.

Practice Mathematical Induction Problems

-------------------------------------------------------------------------------

Here is a set of "homework" problems, dealing with graph theory,visibility, and taxicab geometry.

Homework 2

-------------------------------------------------------------------------------

These notes treat some basic issues about plane graphs. Isomorphic plane graphs can be distinguished by the fact that the number of sides faces have may differ from drawing to drawing. This can not happen for plane 3-connected graphs, the graphs which arise from convex 3-dimensional polytopes.

Plane Graphs

--------------------------------------------------------------------------------

These notes treat some basic issues about traversability problems in graph theory (Eulerian circuits, Chinese Postman, Hamiltonian circuits, trees, and graph distance.

Traversability in Graphs, Trees, and Distance

--------------------------------------------------------------------------------

Here are some practice problems involving basic graph theory concepts including that of Eulerian circuit and the Chinese Postman problem.

Some Problems E (Basic Graph Theory - Eulerian Circuits and the Chinese Postman Problem)

--------------------------------------------------------------------------------

Here is a set of "homework" problems, dealing with graph theory, nets, and taxicab geometry.

Homework 1

-------------------------------------------------------------------------------

These notes treat some basic issues about graph theory, art gallery problems, and visibility.

Art Gallery Theorems and Visibility

--------------------------------------------------------------------------------

Here is a small sample of problems suitable for research by high school (and other students) that deal with guarding simple polygons (related to the Klee-Chvatal Art Gallery Theorem).

Problems Related to Art Gallery Theorems

-------------------------------------------------------------------------------

These notes treat some basic issues about graph theory, polyhedra and nets of polyhedra, polygons, and polyominoes.

Polygons, Polyhedra, Nets and Graphs

--------------------------------------------------------------------------------

Here are some practice problems involving basic graph theory concepts.

Some Problems D (Basic Graph Theory)

--------------------------------------------------------------------------------

Some problems concerning making Euclidean triangles.

Some Problems A

--------------------------------------------------------------------------------

Some problems contrasting making Euclidean triangles and Taxicab Geometry triangles.

Some Problems B

--------------------------------------------------------------------------------

Some problems concerning basic Graph Theory.

Some Problems C

--------------------------------------------------------------------------------

These notes treat the issues of careful looking, an introduction to graph theory, as well as some remarks about geometry and its nature.

Pleasing Shapes, Careful Looking, Same-Different, and the Power of Words

--------------------------------------------------------------------------------

Description of project for Geometric Structure Course

Project: Geometric Structures 2011

--------------------------------------------------------------------------------

Some new materials added for Fall, 2010.

--------------------------------------------------------------------------------

Some material about graphs of 3-dimensional polytopes: Steinitz's Theorem and Mani's Theorem

Steintiz's Theorem and Mani's Theorem

--------------------------------------------------------------------------------

Some new materials added for Spring, 2010.

--------------------------------------------------------------------------------

Some material about Desargues Theorem in the finite geometry setting.

Desargues Theorem in a Finite Plane Setting

--------------------------------------------------------------------------------

One of the most lovely theorems of projective geometry is Desargues Theorem, due to Girard Desargues. Desargues Theorem holds in the real projective plane and in finite projective planes which arise using coordinates from finite fields. Material related to these finite fields or arithmetics, also know as Galois Fields, and the geometries that can be constructed using them can be found in the links below:

Finite Fields

More About Finite Fields

Finite Arithmetics

Desargues Theorem

Diagram Illustrating Desargues Theorem

Construction of a larger finite arithmetic from a smaller such arithmetic

Essay about finite geoemetres including a discussion of Pascal's and Desargues Theorems

Material about the "combinatorics" of finite geoemtries (and unconnected material about trees) --------------------------------------------------------------------------------

Although the essence of how to construct the real projective plane from the Euclidean plane was worked out during the Renaissance (by artists like Leonardo di Vinci), the formal mathematics was not fully understood until the 18th century when people like Jacob Steiner, Moebius, and Von Staudt, developed the notion of homogeneous coordinates and showed how they could be used to coordinatize the real projective plane with triples of real numbers.

Notes on How to Construct the Real Projective Plane from the Euclidean Plane

--------------------------------------------------------------------------------

Additional practice problems which deal with the real projective plane and related problems in the Euclidean plane.

Some more problems involving points, lines and the real projective plane

--------------------------------------------------------------------------------

Some more practice problems which deal with the real projective plane and related problems in the Euclidean plane.

Problems involving points, lines and the real projective plane

--------------------------------------------------------------------------------

Some more practice problems which serve as a review for the final examination.

More Final Review Problems

--------------------------------------------------------------------------------

Some practice problems which serve as a review for the final examination.

Final Review Probelms

--------------------------------------------------------------------------------

A sample of problems related to Taxicab Geometry

Taxicab Geometry

--------------------------------------------------------------------------------

Some practice problems involving vertex, face, and edge colorings of graphs.

Edge, Vertex and Face Colorings of Graphs

--------------------------------------------------------------------------------

These problems involve adding "diagonals" to plane graphs to triangulate all the faces except the infinite face. There are also problems about guarding a polygon and ears for polygons.

Triangulating Plane Graphs and Polygons

--------------------------------------------------------------------------------

One can prove the formulas that arise by summing powers of integers by mathematical induction. These formulas sometimes give rise to interesting proofs without words, and they are a source of raw material for searching for patterns in algebraic expressions.

Mathematical Induction and Sums of Powers

--------------------------------------------------------------------------------

Some problems to practice and to develop skills with mathemtical inducation. Most of these are traditional examples where algebraic, rather than geometrical issues, are involved.

Mathematical Induction

--------------------------------------------------------------------------------

Some notes about automorphisms of graphs and their relation to polyhedra that might have these graphs as their vertex-edge graphs. Ideas related to the difference between combinatorial symmetry and metrical symmetry are discussed. Also, Steinitz's Theorem and Mani's Theorem are discussed.

Symmetry of Graphs and Convex 3-dimensional Polyhedra

--------------------------------------------------------------------------------

This note explores the difference between symmetries of a graph, where one is looking for combinatorial symmetries, and symmetries of metrical drawings of the graph, where one is interested in isometries. There are many interesting issues related to the symmetry of a polygon or polyhedron thought of as a metrical object and the graph of the polygon or edge-vertex graph of the polyhedron.

Symmetry, Automorphisms, and Isometries

--------------------------------------------------------------------------------

Some practice problems involving plane graphs, duality, and spanning trees.

Practice 6: Plane Graphs, Their Duals, and Spanning Trees

--------------------------------------------------------------------------------

This exploration deals with - among other things - nets for the "triangular bipyramid" and a polyhedron that realizes its dual.

Exploration 2

--------------------------------------------------------------------------------

A brief description with practice questions concerning the subtle concept of an induced subgraph of a graph.

Induced Subgraph

--------------------------------------------------------------------------------

Some practice problems involving deleting vertices and edges from a graph, as well as vertex coloring numbers, graph distance and eccentricity.

Practice 5: G-v and G-e, Vertex Coloring,Graph Distance, Eccentricity

--------------------------------------------------------------------------------

Some practice problems involving duals, vertex and face vectors, and related graph theory ideas.

Practice 4: Duality, Face and Vertex Vectors, Chinese Postman

--------------------------------------------------------------------------------

A brief discusson of the dual of a plane graph.

Duality for Plane Graphs

--------------------------------------------------------------------------------

An example to show how to compute the number of vertices of valence i and the number of faces with k sides in a plane graph.

Example: Number of vertices of valence i and number of faces with k sides in a plane graph

--------------------------------------------------------------------------------

Here is a proposal for a "research" investigation that explores the interface between the nets of regular and other metrical cubes, their spanning trees, and their nets. Even if you do not work on this you might find the issues of interest.

Spanning Trees of the 3-cube and Their Associated Nets

--------------------------------------------------------------------------------

Some fairly mechanical problems involving graphs, their valence and face vectors, Eulerian circuits, and the Chinese postman problem. However, practice of this kind does help one come to grips with the basic ideas.

Practice 3: Eulerian circuits, Chinese postman, degree and valence squences.

--------------------------------------------------------------------------------

Information about research journals in discrete, computational and combinatorial geometry, as well as in graph theory and combinatorics. Also, hints about how to find preprints of research articles on the web.

Discrete Geometrical, Graph Theory and Combinatorics Research Journals

--------------------------------------------------------------------------------

Some comments about loose ends about various topics (nets, chinese postman, resources) related to the Geometric Structures Course

Comments

--------------------------------------------------------------------------------

Project for Geometric Structures Course

Project: Spring 2010

--------------------------------------------------------------------------------

Some practice problems which suggest the applicability and geometric nature of a variety of graph theory based questions. These problems involve valences of graphs, Eulerian circuits, and the Chinese Postman Problem.

Practice 2: Some More Graph Theory Problems

--------------------------------------------------------------------------------

A brief survey about polyominoes, 1x1 squares pasted together along their edges. The perspective is the relation between these geometric structures and graph theory and polygons. A variety of open questions are looked at.

Polyomino Primer

--------------------------------------------------------------------------------

Diagrams of the 12 pentominoes. These are geometric objects arising by pasting five 1x1 squares together along their edges.

Diagrams of the 12 pentominoes

--------------------------------------------------------------------------------

Some practice problems which suggest the applicability and geometric nature of a variety of graph theory based questions.

Practice 1: Some Graph Theory Problems

--------------------------------------------------------------------------------

This exploration deals with nets for the triangular prism.

Exploration 1

--------------------------------------------------------------------------------

This essay shows discusses presenting ideas about basic concepts in geometry so that they support an unsolved problem that can be shown to students in the 5th grade and higher.

Unsolved Geometry Problem

--------------------------------------------------------------------------------

The role of definitions in geometry is often complex and subtle because words that are used in geometry have a meaning in common parlance as well as within geometry. As mathematics evolves the same word is often used for many different mathematical ideas. The reason the same word is used is because of "similarities" between the ideas involved.

Geometry and Definitions

--------------------------------------------------------------------------------

Materials developed prior to 2010.

--------------------------------------------------------------------------------

A brief essay (with exercises) about the value of teaching geometry using manipulatives. This essay raises the issue of how different kinds of manipulatives leads to different kinds of geometrical questions.

Manipulatives

--------------------------------------------------------------------------------

This essay/activity addresses issues about the value and use of definitions in geometry. Different people will use informal language to describe things they see in different ways. The activity challenges students to look at a geometric object and list as many properties of the object as they can.

Careful Looking

--------------------------------------------------------------------------------

This assignment asks for nets of a special truncated pyramid. Its purpose is to raise issues about how to represent 3-dimensional objects in the plane, as well as the difficulty of proving the completeness of lists in ennumeration problems.

Homework 1

You might find reading this material helpful with this assignment:

Essay About Nets

A diagram showing the 11 nets of the 3-dimensional cube can be found here

--------------------------------------------------------------------------------

This assignment probes questions related to quadrilaterals, their properties and classification. Also see Practice 2 and 3 below.

Homework 2

--------------------------------------------------------------------------------

This assignment has questions related to the real projective plane, using triples of real numbers to represent points (homogenous coordinates). There are mechanical exercises about writing down the line thought two points, and finding the point of intersection of two lines. Remember, every pair of (distinct) lines must intersect.

Homework 3

--------------------------------------------------------------------------------

This assignment has questions related to traversabiltiy problems in graphs. Finding Eulerian circuits or solving the chinese postman problem for a graph has applications to such settings as snow removal, street sweeping and garbage collection. Finding Hamiltonian circuits could be interpreted as inspecting corners to see if traffic lights are working properly.

Homework 4

--------------------------------------------------------------------------------

Here are some take home problems that can serve as a midterm examination.

Take Home Problems

--------------------------------------------------------------------------------

Course Project for those wanting or required to do one.

Project

--------------------------------------------------------------------------------

Reiview for the final examination.

Final Examination Review

--------------------------------------------------------------------------------

Sample final examination:

Sample Final Examination

--------------------------------------------------------------------------------

This section offers brief notes about different sessions for a Geometric Structures Course.

--------------------------------------------------------------------------------

This session was devoted to issues about how to define geometry; thinking of geometry as a branch of mathematics; thinking of geoemtry as part of physics; the role of definitions in geometry; using our visual system to find properties of geometric objects.

Session 1

Some notes following up on issues raised in Session 1.

Followup Session 1

--------------------------------------------------------------------------------

This session was devoted to some aspects of axiomatics, and to illustrating the way that one gets three different kinds of geometry depending on whether or not one has unique, no, or many parallels through a point to a given line.

Session 2

Another essay with similar material to that above.

Points, Lines, and Duality

Some notes following up on issues raised in Session 2.

Followup Session 2

--------------------------------------------------------------------------------

This session was devoted in part to an exposition of the real projective plane in a model where triples of coordinates are used to describe points.

Session 3

Some notes following up on issues raised in Session 3. In particular it disucsses the idea of coordinates for lines and equations for points.

Followup Session 3

--------------------------------------------------------------------------------

This session was devoted in part to an exposition of basic graph theory ideas including degree sequence and traversability.

Session 4

--------------------------------------------------------------------------------

This session was devoted in part to a further exposition of basic graph theory ideas including ideas related to Eulerian Circuits.

Session 5

For those individuals who are rusty on work involving congruences (modular arithmetic) this very skeletal account may be of use.

Congruence Primer

In conjunction with further work on finite planes here is material related to finite arithmetics, finite fields, and finite geometries.

Finite Fields 1

Finite Fields 2

Material about Eulerian circuits and the associated Chinese Postman Problem and the use of these ideas in solving various urban operations research problems can be found here.

Some basic ideas about finite geometries, and finite arithmetics (fields) which can be used to construct them (in an historical framework) can be found here.

Another essay about modular arithmetic and finite fields (integers mode a prime and the Galois fields) covers some of the same ground in the other essays but with additional examples.

Finite Arithmetics.

--------------------------------------------------------------------------------

This session was devoted in part to an exposition of how to use finite arithmetics to construct finite affine and finite projective planes. This is done in analogy to how the Euclidean was represented by Fermat-Descartes, and extended to the real projective plane via homogeneous coordinates. Also there is a discussion of how to use mathematical inducation to prove that a tree wtih n vertices (graph theory) has (n-1) edges. The concept of graph distance is discussed and some basic ideas about facility location are developed.

Session 6

--------------------------------------------------------------------------------

Sess1on 7 was devoted to the important ideas of planarity and the drawing of a graph on a particular surface in this case the plane. Plane graphs have not only vertices and faces, but also faces. However, isomorphic plane graphs can have different face structures. Interest in graph theory was stimulated for nearly 100 years by attempts to solve the four color problem.

Here is a link for some notes about plane, planar, and non-planar graphs a

Planar, Plane, and Non-Planar Graphs

Some brief notes about the four color problem (solved by Haken and Appel in 1976) are linked below:

Brief Account of the Four Color Problem

--------------------------------------------------------------------------------

This section offers practice problems and exercises, sometimes including additional new ideas and directions to consider.

--------------------------------------------------------------------------------

Some practice problems related to polygons and some ideas related to diagonals for polygons.

Practice 1: Polygons

--------------------------------------------------------------------------------

Some practice problems and notes related to classifying quadrilaterals. Issues of how to classify quadrilaterals and their properties are raised.

Practice 2: Quadrilaterals

--------------------------------------------------------------------------------

Some practice problems related to quadrilaterals. Issues of how to classify quadrilaterals and their properties are raised.

Practice 3: Quadrilaterals

Here is a brief note about an activity for classifying convex quadrilaterals which includes a diagram for helping students organize their work.

Activity for Classifying Convex Quadrilaterals

--------------------------------------------------------------------------------

Some practice problems involving using determinants to solve problems in the real projective plane. Determinants can be used to check if three points are collinear or if three lines are concurrent.

Practice 4: Determinants, Points and Lines

--------------------------------------------------------------------------------

This practice includes some brief remarks about Desargues' Theorem and then offers some exercises to practice verifying this theorem for some specific triangles in the real projective plane.

Practice 5: Desargues Theorem in the Real Projective Plane

--------------------------------------------------------------------------------

This practice includes involves work with congruences and asks for multiplication and addition tables for some finite algebraic structures.

Practice 6: Congruences

--------------------------------------------------------------------------------

This practice includes involves work with homogeneous coordinates selected from a finite field with 5 elements. Problems here involve writing down equations of lines passing through two points and finding the coordinates of the point where two lines intersect.

Practice 7: Finite Projective Plane (Analytical version)

--------------------------------------------------------------------------------

This practice includes work involving the analogue for a finite field of constructing the complex numbers from the real numbers.

Practice 8: Field Extension of a Finite Field

--------------------------------------------------------------------------------

This collection of exercises involves the concept of plane graph. There is also some additional opportunity to practice with the concepts of Eulerian circuit and Hamiltonian circuit.

Practice 9: Plane Graphs

Note: If G is a plane graph its medial graph is the graph obtained from G by placing a vertex on each edge of G and joining two of these new vertices by an edge if the edges they represent have a vertex in common and lie in the same face.

Here are some questions about the isomorphism of very simple graphs to test your understanding of when graphs are "the same" or "different."

Graph Theory Problems

When a graph is embedded in the plane (so that edges meet only at vertices) it creates regions which are called faces. Perhaps surprisingly, two drawings in the plane which are isomorphic as graphs, may have different face structures.

Tidbit 33: Same and Different: Embeddings of Graphs in the Plane

--------------------------------------------------------------------------------

This practice involves the concept of an induced subgraph of a graph. This an important concept because many characterizations of graph properties "Q" involve determination if a particular graph (or set of graphs) occurs as an induced subgraph of the graph being tested for the property "Q" invovled.

Practice 9: Induced Subgraphs

--------------------------------------------------------------------------------

For teachers looking for projects for their students (high school or beyond), here is a collection of ideas related to tetrahedra that involve connections with other areas of geoemetry and ideas from non-geometrical parts of mathematics.

Student Projects Dealing With Tetrahedra

--------------------------------------------------------------------------------

0. One of the big themes of the geometric structures course is that there are many parts and aspects of geometry. Some years ago, as an "exercise" I tried listing as many of these different aspects as I could. Thouugh many of these aspects overlap heavily I found it useful to list even heavily overlaping parts separately. The result, with a now out of date bibliography which supports learning about these different parts is available via my "Geometry in Utopia" project.

Geometry in Utopia

The list of parts, without the bibliographic "noise" is given below.

Parts of Geoemtry

1. An essay attempting to put Euclid's work in an understandable context.

Essay about Euclid's contribution to Geometry

2. Information about the New York Area Geometry Seminar.

Information about the New York Area Geometry Seminar at the Courant Institute

3. David Eppstein has wonderful materials about geometry as part of his Geometry Junkyard. This particular page is about polyhedra but the link to the Junkyard is at the bottom.

David Eppstein's Polyhedra and Polytope page in the Geometry Junkyard

4. David Eppstein also has a great page dealing with the applicability of Geometry, "Geometry in Action."

Geometry in Action (Applications of Geometry)

5. Here are some interactive programs for working with polyhedra, and other geometrical ideas such as the convex hull of a plane set of points.

Polyhedron Explorer

6. Enthousiasts of "advanced" theorems in the domain of Euclidean geometry will find this journal devoted to such theorems of interest:

Advanced Euclidean Geometry

--------------------------------------------------------------------------------

Return to Joseph Malkevitch's Home Page