Lattice Points and Biased Graphs

Fall 2005

This course has two parts that are related, although it is not immediately obvious. The theme, however, is to introduce you to research topics in combinatorics in which I am interested. I intend to present the topics in a way that makes them accessible without requiring you to have a combinatorics background. There will be a lot of geometry.

The course 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"). If you aren't sure whether you might be interested or ready for this class, please see me.

We meet on MWF 1:10 - 2:10 in LN-2205.

Special class times: | |

Week of October 3: No class. | |

Week of November 7: No classes. |

Special class times: | |

Wed., October 10: 1:10 - 2:10 | |

Thurs., November 3: 1:15 - 2:15 in LN-2201 | |

Thurs., December 8: 1:15 - 2:30 in LN-2201 |

There is a Combinatorics Seminar that meets usually on Tuesdays at 4:15, but occasionally at a different time; check the schedule. All 580 students are expected to attend (if the room is big enough for 580 students).

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, I hope) to discuss your progress and any questions you or I may have. I will frequently collect written work: see the homework assignments below and the lists of additional homework problems:

- Additional Ehrhart-theory homework problems: PostScript or PDF,
- Homework problems on hyperplane arrangements: PostScript or PDF,
- Homework problems on signed, gain, and biased graphs (to appear): PostScript or PDF.

- Part O: Introductory stuff. A day or two.
- Part I: Counting lattice points, and what it's good for. Based on the forthcoming book,
- Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra by Matthias Beck and Sinai Robins.

Errata for Ch. 1-6: PostScript, PDF (in progress). - Part I.5: Hyperplane arrangements, matroids, lattice-point counting: a short introduction. This will fit into both halves of the course: the end
of Part I and early in Part II. The readings are in:
- "IOP": "Inside-out polytopes" by Matthias Beck and Thomas Zaslavsky, to appear in Advances in Mathematics,
- "MML": "An enumerative geometry for magic and magilatin labellings" by Matthias Beck and Thomas Zaslavsky, to appear in Annals of Combinatorics.
- "SLS": Extract from "Six little squares and how their numbers grow" by Matthias Beck and Thomas Zaslavsky, in preparation. The extract shows the calculations to find the number of 3×3 magic squares with magic sum t. (Sorry, no pretty plane diagrams.)

- Part II: Signed and biased graphs, and what they might be good for. Based on papers by the teacher. I will make this accessible to students who
have not studied graph theory, but you will have to study. The readings will be from my articles
- "GRS": "The geometry of root systems and signed graphs". American Mathematical Monthly, 88, No. 2 (February, 1981), 88-105.
- "BG1": "Biased graphs. I. Bias, balance and gains", Journal of Combinatorial Theory Series B 47 (1989), 32-52.
- "BG2": "Biased graphs. II. The three matroids", Journal of Combinatorial Theory Series B 51 (1991), 46-72.
- "BG3": "Biased graphs. III. Chromatic and dichromatic invariants", Journal of Combinatorial Theory Series B 64 (1995), 17-88.
- "BG4": "Biased graphs. IV. Geometrical realizations", Journal of Combinatorial Theory Series B 89 (2003), no. 2, 231-297.

Week of | Topic | Reading | Homework to hand in | |||

Aug. 29-Sept. 2 | Introductory survey. Examples of lattice point counting. | Beck-Robins: Ch. 2 | ||||

Sept. 7-9 | Examples of lattice point counting. | Ch. 2 | ||||

Sept. 12-16 | Lattice point counting. Pick's, rational triangles. Frobenius and geometry. | Ch. 2 Ch. 1 | 9/16: Three approved problems from Ch. 2. Approved so far: 10, 15, 21, 22, 30 (if not from Thm. 2.9). | |||

Sept. 19-23 | Integral and rational polytopes and cones. | Sect. 3.1-3 | 9/23: Three problems from Ch. 1. | |||

Sept. 26-30 | Integral and rational polytopes and cones. | Sect. 3.3-5 | 9/26: Three problems from Ch. 3.
9/30: Presentations. | |||

Oct. 3-7 | (No class.) | |||||

Oct. 10-14 | Curve fitting (interpolation). | Sect. 3.6 | 10/12: Six more problems from Ch. 3.
10/10-12: Presentations. | |||

Oct. 17-21 | Rational polytopes and cones. Reciprocity. | Sect. 3.7-8 Sect. 4.1-4 Sect. 5.1 | 10/21: Three problems from Ch. 4.
Presentations. | |||

Oct. 24-28 | Face numbers of simple polytopes. Volume. Magic and semimagic squares (weak form). | Sect. 5.1-5.4 Sect. 6.1-6.3 | 11/2: Two problems from Ch. 5. | |||

Oct. 31-Nov. 4 | Magic and semimagic squares (weak form).
Hyperplane arrangements, intersection poset (matroid), lattice points. Magic and semimagic squares. | Sect. 6.3-4 "IOP" and "MML" | 11/16: Three problems from Ch. 6. | |||

Nov. 7-11 | Hyperplane arrangements and lattice points.
Magic and semimagic squares. | "IOP" and "MML" | Student group discussions at regular class time. | |||

Nov. 14-18 | Hyperplane arrangements and lattice points.
Magic and semimagic squares. Graphs: coloring, orientation, geometry. | "IOP"
"MML", "SLS" | 11/21: Three problems from the "Hyperplanes" problem list. | |||

Nov. 21-23 | Graphs. Signed graphs: coloring, geometry. | "GRS" | ||||

Nov. 28 - Dec. 2 | Signed graphs: coloring, orientation, geometry. | Three problems from the "Signed, Gain, and Biased Graphs" problem list. | ||||

Dec. 5-9 | Gain graphs: dependence structures, geometry, coloring.
Biased graphs. | "BG1-4" ... | especially "BG1" Sect. 5, "BG2" Sects. 2, 3, "BG3" Sect. 4, "BG4" Sects. 2.1, 4.1. |

To my home page.