Course Identification

Graph Theory and Applications
20234071

Lecturers and Teaching Assistants

Prof. Ehud Friedgut
N/A

Course Schedule and Location

2023
First Semester
Tuesday, 11:15 - 14:00, Jacob Ziskind Building, Rm 155
08/11/2022
10/02/2023

Field of Study, Course Type and Credit Points

Mathematics and Computer Science: Lecture; Elective; Regular; 3.00 points

Comments

N/A

Prerequisites

No

Restrictions

30

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

50%
50%

Evaluation Type

Examination

Scheduled date 1

08/03/2023
Jacob Ziskind Building, Rm 155
1100-1400
N/A

Scheduled date 2

30/03/2023
Ziskind, Rm 1
1100-1400
N/A

Estimated Weekly Independent Workload (in hours)

2

Syllabus

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.

Learning Outcomes

Upon successful completion of this course students should be able to:

[1] Describe the basic notions of graph theory.

[2] Discuss many of the elements of the cutting edge of modern research in the field of graph theory.

[3] Demonstrate familiarity with some striking examples of the applications of graph theory in topology, number theory, combinatorial geometry and other fields.

Reading List

N/A

Website

N/A