Signed Graphs

Fall 2014

This course is an introduction to fundamental concepts of signed graph theory, generalizations, and related geometry, including a dash of matroids. There is no official book but there are lots of papers available (electronically, and I can give real reprints of several of them to those who like that sort of thing). A linked list will be posted later. I'll recommend a basic graph theory book when I can think of one that's most appropriate. (Diestel or Tutte will be satisfactory though not perfect.)

The course is not normally suitable for first-year graduate students. However, there are **no specific prerequisites** except the traditional ``mathematical maturity''?not even a course in graph or matroid theory, though it will be helpful. Basic graduate algebra is *very* helpful.

- The latest course notes for Chapter I: Graphs.
- The latest course notes for Chapter II: Signed Graphs.
- The "complete" (but not really complete) course notes from the class in 2008-10 as slightly modified by me since then.
- The header file for typing up LaTeX notes from the course (for daily reports). Also, tips for typing up LaTeX of the daily report.
- A sample daily report (draft of the day's notes) for guidance.

I will be happy to see graduate students at any time, as far as possible (that means, not early in the morning and not when I'm rushing to prepare a class). We can make appointments, but they're not required.

All students are *strongly encouraged*, if not required, to attend the Combinatorics Seminar, usually on Tuesdays, 1:15 - 2:15. There will be talks you can't understand, as well as some you can't help understanding, on all kinds of topics in graph theory and other combinatorics as well as in number theory (and sometimes both at once). (You'll be surprised how much you learn by not understanding a great many talks.)

I will lecture, for the most part.

Student work: You will have to work hard sometimes to understand the lectures and readings. Keep your colored pencils handy. Ask questions!

I will have you write up the notes of some of the lectures (in LaTeX). I'll use them to prepare lecture notes where there are gaps in or additions to the existing notes.

Your grade will be based partly on your note-taking and write-ups. It may be based partly on student presentations. I will also meet with each of you individually on a regular basis.

Here is the most basic list. A big list of related readings appears at the end of the course notes.

- [SG] T.Z., "Signed graphs". Discrete Appl. Math., 4 (1982), 47-74 (and correction). Basic (but not necessarily elementary) concepts and properties.
- [SGC] T.Z., "Signed graph coloring". Discrete Math., 39 (1982), 215-228. Basic (but not necessarily elementary) concepts and properties of coloring and the chromatic polynomial.
- [MTS] T.Z., "Matrices in the theory of signed simple graphs". Introductory survey.

- [GRS] T.Z., "The geometry of root systems and signed graphs". Amer. Math. Monthly, 88 (Feb., 1981), no. 2, 88-105. A readable introduction to some of the connections between graph theory and geometry.

- [BG1] T.Z., "Biased graphs. I. Bias, balance and gains". Fundamentals of gain graphs and biased graphs.
- [BG2] T.Z., "Biased graphs. II. The three matroids". The closure operations that are basic to the theory, in ?? 2, 3.

To my home page.