Section 4 MATH605 - Graphs and Algorithms
This course introduces students to linear programming techniques, with a particular emphasis on the simplex algorithm and its applications in combinatorial optimization. Topics include fractional relaxations of classical graph parameters such as the vertex cover number, independence number, chromatic number, and matching number, as well as Delsarte’s linear programming bound in the context of association schemes and coding theory.
Time permitting, we will also explore the fundamentals of semidefinite programming and its role in combinatorial optimization, through topics such as Lovász’s theta function for Shannon capacity, the Goemans-Williamson approximation algorithm for Max-Cut, and Schrijver’s contributions to coding theory.
Additional applications of semidefinite programming, potentially covering areas such as association schemes, extremal combinatorics, and topological graph theory, may be discussed depending on time and student interest.
Subsection 4.1 Course Outline
Linear programming is a fundamental tool in optimization and discrete mathematics, with numerous applications. Linear programs are efficiently solvable and possess a rich duality theory. A central strategy in combinatorial optimization is to formulate problems as integer linear programs, then relax the integrality constraints to obtain linear programs that are easier to solve.
Linear programs are a subset of convex optimization problems. Semidefinite programming (SDP) extends linear programming to a broader class of convex programs, retaining many of the desirable properties of LPs while often providing tighter approximations. SDP methods have achieved groundbreaking results in combinatorial optimization, such as Lovász’s work on Shannon capacity and the Goemans–Williamson 0.878-approximation algorithm for Max-Cut.
This course provides an introduction to linear and semidefinite programming methods and their applications in combinatorial optimization.
The course will be organized around the following main topics:
-
Linear Programming and the Simplex Method: We will cover the foundations of linear programming, including duality theory, Bland’s rule, simplex tableaux, and basic computational implementations.
-
Graph Theory and Graph Invariants: This includes fundamental definitions, graph representations, an introduction to spectral graph theory, strongly regular graphs, and classical graph invariants (e.g., chromatic number, independence number) along with their fractional relaxations and how these can be analyzed using LP techniques.
-
Association Schemes and Coding Theory: Topics include the algebraic structure of association schemes, with a focus on Hamming and Johnson schemes, leading to Delsarte’s Linear Programming bound. These tools will illuminate connections between algebra, graph theory, and optimization in addressing extremal problems in coding and information theory.
-
Semidefinite Programming: If time permits, we will explore further applications of semidefinite programming in combinatorial optimization, including more advanced examples from graph theory, coding theory, and extremal combinatorics.
Subsection 4.2 Prerequisites
Students are expected to have completed the following courses, or have obtained consent from the instructor:
-
Math 375: Introduction to Discrete Mathematics — covering logic, sets, combinatorics, graphs, and basic proof techniques. -
Math 417orMath 517: Introductory Real Analysis — foundational concepts of analysis including limits, continuity, and convergence. -
Math 447orMath 547: Linear Algebra — including vector spaces, linear transformations, eigenvalues, and matrix theory.
If you have not taken these courses but believe you have the equivalent background, please consult the instructor for approval.
Subsection 4.3 Textbooks and Resources
Course notes will be provided throughout the semester. Much of this material will be written and updated as the course progresses, so please stay engaged, read carefully, work through the details, and report any typos or errors to the instructor for correction.
Much of the course content is adapted from the following texts by Bernd Gärtner and Jiří Matoušek:
-
Jiří Matoušek and Bernd Gärtner. Understanding and Using Linear Programming. Springer, 2007.
-
Jiří Matoušek and Bernd Gärtner. Approximation Algorithms and Semidefinite Programming. Springer, 2012. (Available freely through the library as a PDF.)
Additional resources include:
-
Vašek Chvátal. Linear Programming. A Series of Books in the Mathematical Sciences. W. H. Freeman and Company, New York, 1983. xiii+478 pp. ISBN: 0-7167-1195-8; 0-7167-1587-2.
-
A. Schrijver. Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons, Ltd., Chichester, 1986. xii+471 pp. ISBN: 0-471-90854-1.
-
László Lovász. Semidefinite Programs and Combinatorial Optimization. In Recent Advances in Algorithms and Combinatorics, 137–194, CMS Books Math./Ouvrages Math. SMC, 11, Springer, New York, 2003.
-
Lecture notes by Monique Laurent and Frank Vallentin (updated version available on the D2L site).
-
Lecture notes by Ryan O’Donnell:
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ -
Lecture notes by Bill Martin:
http://users.wpi.edu/~martin/RESEARCH/CIMPA/
Subsection 4.4 Course Assessments
Assessments in Math 605 will consist of two in-person exams (a midterm and final, worth 15% each), a computer project (15%), and a final reflective report based on your semester-long journal (55%).
Problem sets will be posted every few weeks but will not be collected or graded. You are expected to work collaboratively, seek help when needed, and evaluate your own understanding of the material.
Subsubsection 4.4.1 Exams
There will be both a midterm and a final exam. The midterm will be announced at least one week in advance, along with a short list of topics to guide your preparation. The final exam will take place according to the University’s exam schedule, during the first class period that would occur in finals week.
Each exam is worth 15% of your final course grade.
Subsubsection 4.4.2 Computer Project
Midway through the semester, a computing project will be assigned either individually or in small groups of two. The project will involve reading and summarizing a relevant research paper, and implementing a linear or semidefinite programming algorithm to solve one or more problems discussed in that paper or a comparable resource.
The computer project and report is worth 15% of your final course grade.
Subsubsection 4.4.3 Reflective Journal and Final Report
A significant portion of your grade (55%) will be based on a reflective report supported by a personal journal that you will maintain throughout the semester. This journal should document your ongoing engagement with the course outside of scheduled class time.
The journal should log your time spent and summarize your work on tasks such as:
-
Attempting and revising Learning Problem sets
-
Studying lecture notes and revisiting course material
-
Collaborating with peers in discussions or study groups
-
Attending office hours or scheduling additional help sessions
-
Emailing questions or feedback related to course content
-
Reading assigned or recommended references
-
Proofreading the course notes and offering constructive feedback
-
Other meaningful forms of engagement, including participation during class
At the end of the semester, you will submit a final reflective report that synthesizes insights from your journal and presents a well-reasoned argument for the grade you believe reflects your work in this part of the course. The report should critically assess your engagement, growth, and consistency, and must include selected journal excerpts to support your reflection.
While there is no fixed number of entries required, regular and thoughtful journaling is expected, in line with the university’s credit hour policy (6–9 hours per week of work outside class). Your final report should go beyond a simple summary — it should demonstrate how your efforts contributed to your learning over the semester.
This ungrading model emphasizes intrinsic motivation, self-awareness, and the development of professional habits of mind. It also recognizes that meaningful learning can take many forms not easily captured through traditional assessments.
Subsection 4.5 Course Grades
Final letter grades will be assigned based on the weighted averages outlined above. Specific gradelines will be drawn after all course grades are calculated based on student work in alignment with the university policy for graduate students outlined in Subsection 6.2.
