Course Identification

Graph Theory and Applications
20204062

Lecturers and Teaching Assistants

Prof. Ehud Friedgut
N/A

Course Schedule and Location

2020
Second Semester
Sunday, 14:15 - 17:00, WSoS, Rm 2
19/04/2020

Field of Study, Course Type and Credit Points

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

Comments

Will be taught via Zoom starting April 19th.

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

12/08/2020
N/A
1100-1400
N/A

Scheduled date 2

02/09/2020
N/A
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