Math 581: Topics in Graph Theory
Fall 2006
Algebraic Graph Theory
Description
The course is for students in the second year and higher; it is not an introductory graduate course. The absolute minimum requirement is a good understanding of abstraction and a solid modern algebra background (as from a graduate course), and the more graduate math you know, the better (that's the famous "mathematical maturity").
Previous knowledge of graph theory is not essential!
If you aren't sure whether you might be interested or ready for this class, please see me.
We will use as textbook Algebraic Graph Theory by Chris Godsil and Gordon Royle (published by Springer Verlag), selected chapters, supplemented by my own (vastly improved??) interpretations using signed graphs. The main topics of the course are something like the following list (the details will be decided during the course, but I hope to cover Chapters 8-12 at least):
- Getting started: graphs, groups. (Most of Ch. 1-4.)
- Adjacency and incidence matrices. Eigenvalues. Distance regular graphs. (Ch. 8, 9, 4, extra stuff, etc.)
- Two-graphs, strongly regular graphs. Signed complete graphs and signed switching. (Ch. 10, 11, and extras.)
- Line graphs, generalized line graphs, and line graphs of signed graphs. Root systems. (Ch. 12 and extras.)
I will expect you, the students, to study the material and to work on as many of the exercises as you can. I will meet separately with each student frequently (every week or two) to discuss your progress and any questions you or I may have. I will frequently collect written work: see the homework assignments below. I will accept a second version of any problem, if you want to rewrite it for a better grade (or any other reason), but only within a reasonable time (let's say, about two weeks from when I returned the first version).
We meet MWF 1:10 - 2:10 in LN-2205. There will be student presentations, possibly during extra meetings.
You should do as many as you can of the exercises in the chapters we cover. Do a good job: it's better to do fewer well than more badly. I won't give specific assignments, except for a few problems to be handed in.
Schedule
- Week 1 (8/28-9/1): Read Chapter 1, do all exercises as far as time allows.
- Week 2 (9/6-8): Read Chapter 2, but you may skip Sect. 2.3. Do all exercises not related to assymmetric graphs, as far as time allows.
- Week 3 (9/11-15):
- Read Sects. 3.1-2; do the related exercises. In Sects. 3.3-4 read the exposition and statements of results (the proofs are optional). In Sect. 3.5 read the first paragraph (definitions). In Sect. 3.6 read to the middle of page 46.
- Read Sects. 4.1-2. Do related exercises.
- Week 4 (9/18-20): Read Sects. 4.2-3.
- Week 5 (9/25-29): Read Sects. 4.4-5. Extra material on distance-regular graphs. Do related exercises.
- Week 6 (10/4-6): Read Sect. 8.1. Extra material on distance-regular graphs. Do related exercises.
- Week 7 (10/9-13): Read Sects. 8.2-6. Signed graphs: balance, switching, incidence matrix. Do related exercises, including several from A5-A11.
- Week 8 (10/16-20): Read the main definitions and results of Sects. 8.7, 8.8--10, 8.12. More on signed graphs: balance, switching, incidence matrix. Do related exercises, including some from A12-A16 and some on eigenvalues of graphs.
- Week 9 (10/23-27): Read Sects. 10.1-2. Do related exercises.
- Week 10 (10/30-11/3): Read Sects. 10.3-5. Do related exercises. In particular, do #A5.
- Week 11 (11/6-10): Read Sects. 10.5-7. Try to get the general picture of how the Krein bounds are proved, but don't sweat the details. Do related exercises.
- Week 12 (11/13-17): Read Sects. 10.8-9, 11.1-2. Do related exercises.
- Week 13 (11/20): Read Sects. 11.3-5. More on two-graphs, signed complete graphs, double cover graphs. Do related exercises, especially exercises on basic properties of two-graphs (correct definition) and the double cover (correct definition).
- Week 14 (11/27-12/1): Read Sects. 11.6-7 (and glance at 11.8), 12.1, signed line-graph handouts. Generalized line graphs. Do related exercises.
- Week 15 (12/4-8): Read Sects. 12.2-4, handouts on line graphs. Bidirected graphs; line graphs of signed graphs, bidirected graphs, et al. Do related exercises.
- Week 16 (12/11-14):
Extra classes:
- Mon. 2:00-3:30 (approx.) in LN-2205 on signed graphs with eigenvalues ≤ 2 and graphs with eigenvalues ≥ −2;
- Tues. 11:30-12:30 (at latest) in LN-1402 on the general properties of star-closed line systems used in their classification.
Read Sects. 12.6, 12.8. Do related exercises.
Scan Sections 12.5, 12.7, 12.9 to get the idea of the results and methods; omit the details.
Problem "c.n" means Chapter c, #n. Your written work should be a final draft and logically complete (all necessary steps written and explained).
- Wed. 10/11 (due in class or before): 1.8, 1.10, 2.12, 3.2, 4.1, 4.A1.
- Mon. 11/6: 8.9 (with multiplicities), 8.A3.
- Wed. 11/8: 8.A6, 8.A9.
- Mon. 11/20: 8.A21, 10.2.
- Tues. 11/21 (or Wed. a.m.): 10.1, 10.A1, 10.A2.
- Fri. 12/8: 11.1, 11.A2.
- Fri. 12/8: 11.A3, 11.A5, 11.A8.
- Mon. 12/11 (may be postponed to Wed.): 11.A7.
- Wed. 12/13: (OMIT 12.A2), 12.A5, 12.5.
See the separate page.
The presentations will be on Tuesdays, 1:15 - 2:40 (but not usually using all that time) in LN-1402. The schedule:
- 11/12:
- Justin will explain how the two definitions of a Moore graph are equivalent.
- Gareth will explain why the Clebsch graph is unique.
- 11/19:
- Darryl will explain the Paley graphs.
- 11/26:
- Elizabeth will explain Paley digraphs and antisymmetric conference matrices.
- 12/5:
- Garry will show us a construction of a generalized quadrangle.
- Jackie will prove uniqueness of a strongly regular graph.
To my home page.