Joseph Malkevitch: Geometric Structures Geometric Structures (Notes)

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/

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

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

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

Some new materials added for Summer, 2016.

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

In getting insights into geometry using graph theory as a window to see some of the problems that interest modern geometers, it is helpful to have lots of examples of different kinds of graphs. This essay was written many years ago and offers basic questions to try to get students to explore different aspects of geometry by looking at special classes of graphs. These classes include trees, bipartite graphs, polytopal graphs, cubes, etc.

Classes of Graphs

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

Some new materials added for Summer, 2015.

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

I am a big fan of proofs without words. Roger Nelson and Claudi Alsina have published several wonderful books of such proofs. The January 2015 issue of the MAA College Mathematics Journal had a very lovely proof (page 10) that the area of a regular dodecagon inscribed in a circle of radius 1 is exactly 3. The proof shows this by dissecting the dodecagon into parts that form three squares of side 1 that can be made with the triangular parts. A more general question that occurred to me about when regular polygons have integers areas had already been answered:

Killgrove, R. B., and D. W. Koster. "Regular Polygons with Rational Area or Perimeter." Mathematics Magazine (1991): 109-114.

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

Geometric ideas often prove useful in genomics. The idea of edit distance or Levenschtein distance plays a big role in finding the "distance" between two DNA strings or genes. The algorithm for finding this distance has been "rediscovered" independently several times.

Algorithms for edit distance

A recent contribution to complexity theory suggests that it may be hard to improve the best running time of algorithms for edit distance.

Optimality of edit distance algorithms

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

While the vast majority of new research being done related to geometry involves Euclidean ideas, non-Euclidean spaces get their share of research attention as indicated by this conference:

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

Geometry concerns itself both with mathematical theory and applications of geometry to physics. One concern is what the "true" geometry of space is. One way to judge what geometry space has is to measure its "curvature." This can be accomplished via observations using satelittes. The most recent work based on results obtained by the Planck mission (European Space Agency) can not rule out that space is flat, that is Euclidean. Euclidean space has 0 curvature so proving that space is Euclidean experimentally is not easy.

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

Some new materials added for Spring, 2015.

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

Syllabus: Spring, 2015

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

Geometry has a very varied landscape, and this list of "parts" for geometry gives some idea of the breadth of what modern geometry is like. These parts of geometry are heavily overlapping but it is still useful to think about these different pieces of geometry.

Geometry's Parts

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

One can use the Galois fields, or more narrowly the integers mod a prime, to get a model for finite affine or finite projective planes. Here is a bit of information about the connection between finite arithmetics and geometry.

Finite Arithmetics Connected to Geometry

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

Here are some review problems for topics that were treated in the Geometric Structures course.

Review Problems for Geometric Strutures

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

Here are some brief notes about the real projective plane and the relationship between the analytical geometry of the real projective plane and that of the Euclidean plane.

The real projective plane

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

This assignment allows one to see the feedback between the analytical approach to Euclidean geometry, and the analytical approach to the real projective plane. Determinants can be used to find the line through two points or the point where two lines meet.

Assignment 4: Real Projective Plane.

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

In order to construct models of finite projective and affine planes one needs to know a bit about finite arithmetics and fields. A first step here is to know about properties of the integers modulo m, or congruences.

Congruence Primer

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

Axiomatic approaches to geometry tend to come "after" the basic geometric ideas have been explored. Changing axioms in a geometric system is similar to changing rules in a sport. One gets a "new" game, not necessarily better or worse, just different, but somehow familiar. Changing the parallelism axiom in Euclidean geometry yields a very rich geometry with important ties to other branches of mathematics including number theory and algebra. Two brief essays about dealing with the relationship between affine (Euclidean geometry) and projective geometry are given below, but there are other "essays" and practice problems are available in materials much further below here.

Euclidean Geometry and Projective Geometry

From Affine to Projective Geometry and Back

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

This web site has a variety of appealing visual displays of geometric objects and curves.

Curve Bank

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

Here are some expository items related to the Klee-Chvatal Art Galley (Museum Guard problem.

Art Gallery Tidbit

Art Gallery Problem

AMS (American Mathematical Society) Feature Column related to polygons and art gallery theorems I

AMS Feature Column related to art gallery probelms II

AMS Feature Column tribute to Victor Klee

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

Mathematical induction is one of the most important proof tools available. To carry out the "induction step," using the truth of T(k) to show T(k+1) must hold is usually the hard part. In showing number theoretic results algebraic manipulation is the key to this step, but in geometrical uses of inducation, some geometric "foundation" must be laid to carry out this step.

Practice 4: Mathematical Induction

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

This assignment deals with a variety of issues related to graphs and polyhedra. Convex polyhedra have vertices and edges which give rise to a graph structure. This graph must be planar and 3-connected. However, when a graph is planar and 3-connected is it the graph of some convex 3-dimensional polyhedron? The answer is "yes." This is the content of Steinitz's Theorem, which allows one to think about convex 3-dimensional polyhedra as objects (graphs) in the plane. The graph theory formulation of the theorem is due to Branko Grünbaum and Theordore Motzkin. There are also some questions about coloring problems.

Assignment 3: Graphs and Polyhedra.

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

Geometry is important both for theoretical reasons as well as applications. However, one of its charms for educational settings is that it quick starting compared with other parts of mathematics in that often the problems that researchers are working on are easy to state, though typically not to solve. The computational geometry journal linked here will give you some idea of the kinds of questions that geometers are asking and solving. All of the articles can be downloaded for free as pdf files, and there is a seach feature to that you can see what has been published in this journal dealing with, say, Steinitz's Theorem or polygons.

Journal of Computational Geometry

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

d-dimensional cubes, for d more than 3 are very intriguing as a way to get a window on thinking about higher dimensional objects. Here are some articles I prepared about cubes. The coordinates of a d-cube can be taken to be the binary sequences of length d, that is, the vertices are labeled with binary sequences of length d. The edges of the cube are those that join two strings (vertices) that differ in exactly one position, that is, have Hamming Distance 1.

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

There are a great many ways in which planar and plane graphs are of special interest. In particular, knots and links, a phenomenon of 3-dimensional space have been much studied by 20th century geometers and topologists. If a knot or link is projected onto a plane, a 4-valent graph results. Perhaps unexpectedly, 4-valent plane graphs give a fair amount of insight into knots and links. Gil Kalai elicited some interesting thoughts on planar graphs with a queston he asked on Math Overflow.

Why are planar graphs exceptional: I

Why are planar graphs exceptional: II

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

Attempts to show that the Parallel Postulate of Euclid was a consquence of the other axioms Euclid studied was doomed to failure because, in fact, there are consistent geometries where there are no parallel lines or multiple parallel lines through a point to a given line. Lambert was a pioneer in ideas that led to hyperbolic geometry (the multiple parallels case) and this is an interesting essay (pdf file) that puts in historical perspective what he accomplished.

Lambert's work "anticipating" hyperbolic plane geometry

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

Polygons and polyhedra were studied in Euclid's Elements and have fascinated geometers and mathematicians ever since. Thus, it is very remarkable that a way of understanding when a graph is the edge-vertex graph of a 3-dimensional convex polyhedron is very remarkable for how recently it was developed. While the basic result is due to Ernst Steinitz, it was not until Branko Grünbaum and Theodore Motzkin reformulated this result in graph theory language in the 1960's that the true significance and importance of Steinitz's Theorem started to be appreciated. A torrent of new results about polyhedra is still occurring as a result of new ways of using this fantastic theorem.

Information about Steinitz's Theorem (characterizing the graphs which can be the edge vertex graphs of 3-dimensional convex polyhedra) and Mani's Theorem (relating the symmetry of convex 3-dimensional polyhedra and their graphs

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

For those who enjoy celebrating Pi Day, here are a few items that have some connection with this course, in particular, the value of "pi" for the taxicab plane.

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

This is a collection of practice problems involving the concept of cut vertex (removing the vertex increases the number of components or pieces of the graph) and bridge (cut edge) (removing the edge increase the number of components of the graph. It also treats the concept of the eccentricity of a vertex. The eccentricty of vertex v is the farthest any vertex can be from v. In some graphs the eccentricty of all the vertices is the same.

Practice 3: Graph Theory

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

Polygons seem like a simple idea until one begins to look at the great variety of different kinds of polygons there are and how one can find a simple collection of words to get across this important idea.

What is a Polygon?

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

Many years ago I made some visits to lower grade classes to make presentations about geometrical ideas that were not part of the standard curriculum but which I thought that children should see. Here are some notes about these ideas that I prepared. I still think it is a good idea for young children to have experiences of this kind.

Geometry for Kindergarteners

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

Joel David Hampkins is a colleague of mine at CUNY and he prepared these notes about "graph theory for kids." I would have tried to link some of this to applications such as snow removal, salt spreading, etc. (for the Euler circuits) and conflict resolution for the vertex coloring problems.

Graph Theory for Kids

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

Polygons are are a very general class of geometrical objects. The "central" features of polygons are that they consist of straight line segments, and that at each vertex there are two edges. We will concentrate on polygons whose vertices and edges lie in a plane but there are lots of interesting issues about polygons in 3-space, including matters related to knotting. So (in a plane) one can look at convex and non-convex polygons, simple polygons (edges don't meet except at vertices), regular polygons, equilateral and equiangular polygons, etc. However, some geometers think that that the "usual" approach to defining polygons is too narrow because these definitions don't behave well with respect to continuity. Geometers like Branko Grünbaum would allow vertices of polygons to coincide with each other resulting in many interesting ideas and new questions, though the ideas that Grünbaum builds go back to an approach to polygons developed in the 18th century.

Practice 2: Polygons

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

Some interesting natural shapes. Examples of this kind often are inspirations for new geometrical ideas.

Strange Natural Shapes

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

This collection of problems allows you to practice issues related to planar/plane graphs by constructing duals of given graphs, and looking the valence vectors and face vectors of these graphs.

Practice 1

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

There is a tension between abstractness and concreteness throughout mathematics. The immediacy of graph theory, in part, stems from its visual aspects, but for those who like the more abstract one can always go that route. Education transmits and codifies known things but it also strives to encourage people to create new ideas.

Abstract Graphs

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

This assignment is designed to "probe" knowledge of some of the basic ideas of graph theory as related to trees, nets, polyhedra, planarity, and valence sequences.

Assignment 2

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

How to produce some hearts for Valentine's Day but it works equally well on any day.

Surprising Way to Make Hearts

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

Polyominoes are an interesting collection of geometrical structure that have connections with graph thoery, polygons, polyhedra, and nets. They are a nice topic for mathematics students at all levels. There are many nice puzzles and research mathematical activities that can be based on them.

Polyomino Primer

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

This note has templates of equilateral triangles that fold to an appealing and interesting higly symmetrical non-convex solid. Active research is going on about simple questions related to this discussion. The templetes are not "nets" in the usual sense because they have vertices in the interior.

Folding Clusters of Equilateral Triangles

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

Although Euler "invented" graph theory in an attempt to answer a problem in recreational mathematics, ideas related to traversability questions in graphs have many applications. Eulerian circuits don't exist in all graphs - the graph has to be connected and even-valent for this to happen. The underlying efficiency qustions for, say, pot-hole inspection routes still are there. Thus, Euler's ideas are also part of the more practical "chinese postman model." This model deals with providing many kinds of urban services more efficiently, and there are many theoretical and applied variants. A column I wrote for the Americal Mathematicla Society Feature column sheds light on this and some details which we did not cover about these matters in class.

Urban Geometry

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

We discussed briefly that physics has theories and mathematics has theorems. But some theories are hard to test - string theory and other issues that come up in cosmology. Some argue that string theory is just "theoretical mathematics" without being "real" physics. Common "scientific" wisdom is that the universe started with "a Big Bang." However, note the following:

Big Bang?

It is noteworthy that mathematics typically plays a big part in all of this physics "theorizing."

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

This assignment is designed to "access" very basic knowledge of some of the basic ideas of graph theory.

Assignment 1

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

This essay hits some of the topics that were treated in one of our class sessions but raises some ideas and issues that we did explicitly discuss.

An overview of different aspects of geometry

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

Is "physical space" Euclidean? Before "answering" this question it is worth noting that there are three major kinds of geometry: Euclidean, Hyperbolic and Elliptical. They are distinguished by having zero, negative, and positive curvature and the behavior of "parallel lines" in the geometries. There is only one way to have zero curvature, but there are many ways to have positive or negative curvature. So their are many "different" Lobachevsky Geometries though they all have their negative curvature in common. So the usual answer to the question is that based on current understanding physical space is not Euclidean. Our best insights are obtained by using General Relativity Theory. For a basic look at the distinctions between the three kinds of geometry mentioned you can look at the first web page and for more detail the second web page. Note, however, that "locally" hyperbolic and elliptical geometry are "Euclidean." Thus, we live on a big sphere but for many calculations the curvature of the earth need not be taken into account.

Basic Ideas about Euclidean and Non-Euclidean Geometry

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

Graphs, geometrical diagrams consisting of dots and line segments (or curves), are very important both as a theoretical and applied tool. Here are some thoughts about how graph theory can be used give insight into such geometric structures as polygons, polyhedra, and polyominoes. There is also a discussion which contrasts lines in diagrams and the edges of a graph.

The Unifying Power of Graph Theory

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

Project: Geometry: Spring, 2015

Geometry Project for Spring 2015 version of "Geometric Structures"

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

Rather amazingly Taxicab Geometry differs from Euclidean Geometry at the axiomatic level, in that one axiom (rule) of Euclidean Geometry does not hold in Taxicab Geometry. Though we will not look at the taxicab plane until later in the semester, I recently came across a new paper which tries to understand the Euclidean plane better by studying to what extent Euclidean theorems break down or must be modified in their statements in the taxicab plane. Here is the link to this paper (which can be downloaded as a pdf file) which deals with the "butterfly theorem."

Butterfly Theorem in the Taxicab Plane

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

Geometry inspires artists and artists via their work often inspire geometers to consider new geometrical questions. Here are the works that were exhibited at the Joint Mathematics Meetings in San Antonio.

Mathematical Art Exhibit at the 2015 Joint Mathematics Meetings

Bridges: Art and Mathematics

You can find some interesting geometrical images involving ice at this web site:

Ice

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

You can download a pdf file of a nice activity about surfaces in 3-space formed from simple planar "pieces" from this site devoted to continuing the traditions of the great expositor of mathematics, Martin Gardner. This activity is related to the Moebius Band.

Moebius Band Activity (pdf file)

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

Here is a very simplified introduction (basically one graphic) which is the basis an introduction to graph theory.

Graph Theory Primer

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

Some notes related to our first session which deals with word meanings, same and different, and the way geometry grows.

Session 1: Notes

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

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.

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

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

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

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

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

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

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.

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

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

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

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

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

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

### Geometry Resources of Various Kinds

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: