Course Identification

Title:

Graph Theory and Applications

Code:

20234071

Lecturers and Teaching Assistants

Lecturers:

Prof. Ehud Friedgut

TA's:

N/A

Course Schedule and Location

Year:

2023

Semester:

First Semester

When / Where:

Tuesday, 11:15 - 14:00, Ziskind, Rm 155

First Lecture:

08/11/2022

End date:

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

Participants:

30

Language of Instruction

English

Attendance and participation

Expected and Recommended

Grade Type

Numerical (out of 100)

Grade Breakdown (in %)

Assignments:

50%

Final:

50%

Evaluation Type

Examination

Scheduled date 1

Date / due date

08/03/2023

Location

Ziskind, Rm 155

Time

1100-1400

Remarks

N/A

Scheduled date 2

Date / due date

30/03/2023

Location

Ziskind, Rm 1

Time

1100-1400

Remarks

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