CMP 694 - Graph Theory

CMP 694 - Graph Theory (Spring 2025)

CMP 694 - Graph Theory (Spring 2025), D5 — Time: Monday 9:30 - 12:20

Instructor

Lale Özkahya

Office Hours:
Email to arrange an appointment.

All communication will be on https://piazza.com/hacettepe.edu.tr/spring2025/cmp694

Learning objectives
This is an in-depth course on graph theory and its applications.
Text

Introduction to Graph Theory, by Douglas B. West.

Extremal Combinatorics with Applications in Computer Science, by Stasys Jukna. (electronically available at our library)

Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal.

Cook/Cunningham/Pulleyblank/Schrijver, Combinatorial Optimization.

Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms.

Korte/Vygen, Combinatorial Optimization.

Kozen, Design and Analysis of Algorithms.

Papadimitriou/Steiglitz, Combinatorial Optimization.

Schrijver, Combinatorial Optimization: Polyhedra and Efficiency.

Tarjan, Data Structures and Network Algorithms.

The texts below are not required. Reading materials will be distributed as necessary. Reading assignments will be posted on the schedule, please check regularly.

Foundations of Computer Science , a free textbook written by A. Aho and J. Ullman

The Art of Mathematics, Coffee Time in Memphis, by Béla Bollobás. (electronically available at our library)

Proofs from the Book, by Martin Aigner, Günter M. Ziegler. (electronically available at our library). Also a translation into Turkish exists.

Courses on Applications

CS 6241: Numerical Methods for Data Science (Cornell)

Grading

Midterm Exam 30%

Problem Session 30%

Final Exam, 40%

Attendance, 5% (Extra)

Schedule
Notes:

Week Topic Notes Exercises (DBW)

1 Introduction and Counting I: The Binomial Theorem, Double Counting,
Jensen's Inequality, The Averaging Principle
(Jukna) 1, (West) 1.1, 1.2 1, 2 1.1: 10, 11, 12, 13, 18, 29, 31
1.2: 1, 2, 8, 10, 11, 14, 16, 21

Mathematical (mostly Combinatorial) Tools used in Machine Learning

2 Trees and Distance
(West) 2.1 Notes 2.1: 4, 6, 7, 13, 14, 15, 16, 18, 19

3 Maximum Matchings in Bipartite Graphs
Augmenting Path Algorithm
(West) 3.1 Notes 3.1: 1-17, 28, 36, 39, 40

4 Matchings in Graphs
(West) 3.3 Notes 3.3: 1-5, 8, 9, 11, 14, 15

5 Cuts and Connectivity
(West) 4.1 Notes

6 Problem Session

7 Holiday

8 Midterm Exam

9 k-connected Graphs
(West) 4.2 Notes

10 Vertex Coloring
(West) 5.1,2 Notes
Coloring Large Complex Networks

11 Planar Graphs
(West) 6.1 Notes(LLL)
Notes(Planar),
Print Version

12 Hamiltonian Graphs
(West) 7.2 Notes,
Print Version

13 Problem Session

14 National Commemoration Day Notes

© 2025 Hacettepe University

Week	Topic	Notes	Exercises (DBW)
1	Introduction and Counting I: The Binomial Theorem, Double Counting, Jensen's Inequality, The Averaging Principle (Jukna) 1, (West) 1.1, 1.2	1, 2	1.1: 10, 11, 12, 13, 18, 29, 31 1.2: 1, 2, 8, 10, 11, 14, 16, 21 Mathematical (mostly Combinatorial) Tools used in Machine Learning
2	Trees and Distance (West) 2.1	Notes	2.1: 4, 6, 7, 13, 14, 15, 16, 18, 19
3	Maximum Matchings in Bipartite Graphs Augmenting Path Algorithm (West) 3.1	Notes	3.1: 1-17, 28, 36, 39, 40
4	Matchings in Graphs (West) 3.3	Notes	3.3: 1-5, 8, 9, 11, 14, 15
5	Cuts and Connectivity (West) 4.1	Notes
6	Problem Session
7	Holiday
8	Midterm Exam
9	k-connected Graphs (West) 4.2	Notes
10	Vertex Coloring (West) 5.1,2	Notes	Coloring Large Complex Networks
11	Planar Graphs (West) 6.1	Notes(LLL) Notes(Planar), Print Version
12	Hamiltonian Graphs (West) 7.2	Notes, Print Version
13	Problem Session
14	National Commemoration Day	Notes