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

10 Vertex Coloring
(West) 5.1,2 Notes,
Print Version
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 Application of the Probabilistic Method on Graphs
(Mitzenmacher and Upfal) Notes

14 Application of the Probabilistic Method on Graphs
(Mitzenmacher and Upfal) 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
10	Vertex Coloring (West) 5.1,2	Notes, Print Version	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	Application of the Probabilistic Method on Graphs (Mitzenmacher and Upfal)	Notes
14	Application of the Probabilistic Method on Graphs (Mitzenmacher and Upfal)	Notes