Graph Theory and Applications
Lecturers and Teaching Assistants
Prof. Ehud Friedgut
Course Schedule and Location
Tuesday, 11:15 - 14:00, Ziskind, Rm 155
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; Regular; 3.00 points
Attendance and participation
Scheduled date 1
Scheduled date 2
Estimated Weekly Independent Workload (in hours)
We will cover a subset of the following. Basic definitions and parity arguments, Sperner's lemma; Borsuk-Ulam theorem; Hamilton and Euler circuits; trees: Cayley's theorem and the matrix-tree theorem; Flows and matchings: mincut-maxflow, Hall's theorem, Tutte's theorem; Connectivity: Menger. ; Planarity, Euler's formula. Applications to combinatorial geometry; Extremal graph theory: Turan's theorem, Erdos-Stone, Szemeredi's Regularity Lemma and applications; Random graphs and applications. Algebraic graph theory and spectral graph theory.
Upon successful completion of this course students should be able to:
 Describe the basic notions of graph theory.
 Discuss many of the elements of the cutting edge of modern research in the field of graph theory.
 Demonstrate familiarity with some striking examples of the applications of graph theory in topology, number theory, combinatorial geometry and other fields.