Expander Graphs, Math 9148A, Fall 2017

Class times and location: TuTh 9am-10:30am, MC108, starting Sep 7 and ending Dec 7

Prerequisites: No official prerequisites, but see the following statement.


This is an introduction to graphs.  You do not need to know anything about them, but you should probably know some linear algebra.

Most of the theory we need we will develop in class.  The goal is to define an expander graph and to explain why one might be interested in them. We will develop the language needed to make a precise definition and to explain how one exhibits them.  A typical example is an "undirected" graph which is both "regular" and "sparse" yet "highly connected".  An extreme example is a "Ramanujan graph".  Mathematicians and Computer Scientists each have interesting applications of expander graphs, and time permitting, we will describe some.


Instructor: Chris Hall

Office Hours: after class

Text: There is no textbook for the course, but I will provide access to articles and texts via a shared folder on Dropbox.  Foundational and inspirational articles include: 

-- "Expander graphs and their applications'' by S. Hoory, N. Linial, A. Wigderson;
-- "Expander graphs in pure and applied mathematics'' by A. Lubotzky;
-- "Expander graphs'' by E. Kowalski.

Inspirational books include:

* Elementary Number Theory, Group Theory, and Ramanujan Graphs by G. Davidoff, P. Sarnak, A. Valette;
* Algebraic Combinatorics by C. Godsil;
* Spectra of Graphs by A.E. Brouwer and W.H. Haemers;
* Discrete Groups, Expanding Graphs, and Invariant Measures by A. Lubotzky;
* Expansion in Finite Groups of Lie Type by T. Tao.

Electronic copies of the articles will be provided, but none of the books are required. 


Dropbox: I will share electronic articles and notes using Dropbox.  Please provide me with the e-mail address you use to login.

Attendance: Our class is small and someone's absence can greatly impact the rest of the class. Therefore you are expected to attend class or to let me know in advance when you are unable to attend.

Journal: At the end of the semester you should turn in a collection of ten completed (approved) exercises. I will suggest problems over the course of the semester, and you can decide which you want to do.  You are encouraged to share your journal with me during the semester so that I can give you feedback.  You must turn in an electronic copy to me by Dec 8.

Typesetting Notes: Each student must typeset notes for two consecutive lectures.  In addition to attending lecture those days and taking you notes, after the end of the second lecture you will need to:

1. typeset a first draft;
2. meet with me to discuss first draft within one week;
3. produce a final draft;
4. obtain approval from me of final draft within two weeks.

Once you have my approval, you need to provide the following for the final version of the document:

5. a copy for me of the LaTeX source;
6. a copy I can share of the PDF.

There are two goals.  First, I want a record of the lectures we can all refer to.  Second, I want you to gain experience working in LaTeX.

Projects: Each person must schedule a 30-minute meeting with me during the exam period Dec 10--21 for a private oral exam.  Please complete a survey to indicate what times would work for you; I will be the only one who sees your answers, and I will use it during the last week of class to schedule the exams.  If you need me to commit before Dec 8 to the date of your exam, please let me know asap. 

To prepare for this exam you must:

1. select a topic from my list or negotiate your own topic, and obtain my approval by Nov 1;
2. read material I suggest to you;
3. prepare an outline for a 5-page document relevant to your topic, and obtain my approval by Nov 15;
4. use your outline to complete your document;
5. submit a PDF version of your document to me by the last day of classes Dec 8.

You should certainly meet with me if you have questions or concerns about how to prepare.  At the exam in December we will discuss your project and analyze your document.


Basis: Your performance will be measured using three tangible items: problem journal, project document, typeset notes.  Each will contribute 30% to your final grade.  The remaining 10% consists of a grade for the oral exam. 

Scholastic offences: Scholastic offences are taken seriously and students are directed to read the appropriate policy, specifically, the definition of what constitutes a Scholastic Offence, at the following Web site: