Graph theory course blurb, from Explore page syllabus. However, the ``Blackboard page'' for the course, which also has this information, will further contain proprietary material open only to Georgetown students who are registered for it.
A graph is a set of nodes with some pairs connected by links, as towns are joined by roads or people by relationships. Basically, graphs are what you get when you take a network and strip away the extra numerical information such as vehicles/hr and cost. Directed graphs include diagrams of syntax as well as the URLs and hypertext pointers that make up the World-Wide Web. The goal of the course is to give students a good idea of what graphs are and how they fit into mathematics and its applications. This is a fun course about very useful mathematical objects, which can be represented making simple drawings on a piece of paper (or computer screen). As the above (and following) remarks make clear, graphs are now ubiquitous in many areas of science and even of society, and their study has become extremely popular. I will also use a powerful software tool from Wolfram Research (maker of the famous Wolfram Alpha) in order to illustrate graphs. Georgetown has a site license, and students who wish can take the opportunity to learn how to use this software, which is called "Mathematica" (version 9). Students will be required to recognize some of the basic properties of graphs and to compute various graph-invariants, such as vertex-connectivity or crossing number, after these concepts have been introduced in class. Some simple proofs will also be on the agenda but for the harder derivations, we will mostly rely on plausibility arguments. The course meets twice a week (T/Th 3:30 -- 4:45, in Reiss 281). In addition to Mathematics, Computer Science, and Statistics majors, for whom it should be a required course, a variety of other fields, including Sociology, Psychology, Biology, and Physics, as well as Medicine, Business, Foreign Service, and Law, have found graph theory valuable. The lecturer, Paul Kainen, has worked in both the theory and applications of graphs and wrote his first paper on graphs when he was a graduate student, based on work he did while still an undergraduate. It is hoped that some of the students will be similarly inspired to begin a research career, but all of you will be able to use it as a tool in your professions. Texts & Readings We are using the classic text, Graph Theory, by Frank Harary, Addison-Wesley, Reading, MA, 1969, which is available on-line at http://www.dtic.mil/dtic/tr/fulltext/u2/705364.pdf but the book is so good that every math student should buy a copy (used copies are available from Amazon, and the book has been reprinted as well, unfortunately at a quite high price). As a number of important results have appeared in the last 4 decades, some remarks will illustrate what is new. Assignments & Expectations of Students Here is the approximate syllabus. We cover most of chapters 1 to 12 of the book (approximately 150 pp), together with a small amount of additional material on more recent results and applications. Chapter 1 is introductory, Chapters 2--5 are on graphs, blocks, trees, and connectivity, and deal with structure. Chapters 6--10 cover partitions, traversability, line graphs, factorization, and coverings of graphs, while Chapter 11 is on planarity and Chapter 12 on colorings of graphs, both of which are important in applications. If time permits, we will also look at Chapter 16, on directed graphs. A more detailed syllabus including which sections we shall omit and a list of homework problems will appear a few weeks prior to the start of the class. Homework will be assigned so that students can "learn by doing" (as procedural knowledge is more valuable than mere memorization of results). The answers will be discussed in class and students will have the opportunity to present and discuss their own solutions to the problems. Course grade will depend on 2 midterms and a final exam, as well as on a number of announced and unannounced quizzes. Since the class period of 75 minutes is too long for a lecture, there will usually be a quiz or a discussion to break it up. Your quiz total will count as 20 percent, the two midterms as 40 percent, and the final exam also as 40 percent. With the instructor's permission, students who have worked hard but haven't done well on quizzes and/or midterms will be allowed to do a project in order to show that they do have a useful grasp of the subject. Projects are due April 28. Midterm exams will be held in the evening from 7:30 until 9:30 in order to remove time pressure and to save the class periods to cover the material. The first midterm (on chapters 1--5) will be held on Tuesday, Feb. 11, and the second midterm (on chap. 6--10) on Tuesday, March 25. Classes end on April 28, so our last class is on April 24. The final exam will be cumulative and will be on whatever we have covered in class. Final exam locations will be available from the Registrar's Office, while the locations of the two midterms will probably be St. Mary's Hall (exact room information will be posted). Graph theory has no formal prerequisites but you should probably be comfortable with sets and basic logic: E.g., the union of two sets is the set of all elements which belong to either of them; if A and B are statements, A implies B, and B is known to be false, then A is also false. Those who are uncertain about their qualifications to take the class should make appointments to see me, so that I can give you some guidance.
See colorful outerplanar layouts for some circulant graphs for some of what one can do with graphs.
The course, Graph Theory, Math 220-01, will meet Tues. and Thurs. 3:30 to 4:45 pm in Reiss 284.
Office: 313.6 St. Mary's, phone 202-687-2703
e-mail: Kainen at Georgetown dot edu
My office hours in Spring 2014 will be T/Th/F 5 to 6:30 pm. Back to the index page .