MATH 613-600. Graph Theory
Fall, 2017, MWF 10:20- 11:10a.m., BLOC 121
Instructor: Dr. Catherine Yan
Office: BLOCKE 513F
Class: MWF 10:20--11:10, BLOC 121
Office hours: Monday, 1:30--3 p.m.
Level : Graduate
Prerequisites : Math 302 (Discrete Mathematics), or Math 431 (Structures and methods in Combinatorics), or equivalent will be sufficient.
Course Description : This is a course at the beginning graduate level to help the students gain basic knowledge of the structure of graphs and the techniques used to analyze problems in graph theory and discrete structures.
The course will cover fundamental concepts such as graphs, cycle, path, circuit, trees, matchings and factors, connectivuties and coloring, network. We will also introduce topics in currently active research areas, including Ramsey theory, extremal combinatorics, algebraic graph theory, combinatorial optimation, and probabistic methods. Time allows, we will also give an introduction to matroids.
The grade will be determined by your homework (80%), and a final project (20%). The final project is due on December 6, 2017. In addition, to get a C or better you cannot have more than 50% absense (excused or unexcused).
1. There is no class on October 20.
2. The last lecture in on Dec. 4.
See the pdf file here. The report is due on Dec 6, 2017. Please submit your project through email.
This is the list of topics that some students have chosen to work on for their projects.
Updated regularly. Each topic will take about 1-2 weeks. You are responsible for taking your own notes.
1. Basic Concepts in Graph Theory 1.5 week.
Definitions, paths, cycles and trails, degree sequences, directed
graphs, planar graphs, Hamilton cycles and Euler circuits.
2. Trees and Algorithms 2.5 weeks.
Cayley's theorem, spanning trees and the greedy algorithm, DFS and BFS, minimal spanning tree and shortest paths. Hook length formulas for binary trees.
3. Matchings and Factors 3 weeks.
Matchings and covers in bipartite graph, Hall's matching condition and SDR, Konig's minmax theorems, independent sets and dominating sets, maximal weight matching and stable matching, algorithms, Tutte's 1-factor theorem.
4.Digraphs and Flows in Network 2 week.
Digraphs, The Ford-Fulkerson Theorem, the integrality theorem, supply and demand
5. Graph connectivity 1 week.
Vertex connectivity, edge-connectivity, Menger's theorem
6. Coloring of Graphs and Ramsey theorem 2 weeks.
Brook's theorem, Ramsey's theorem and Ramsey numbers, (Optional: view of Ramsey theory, Van der Waerden's theorem, density statement, and the compactness principle. )
7. Turan's theorem and extremal graph theory 0.5 week
8. Linear algebra in graph theory 2 week
Spectral of graphs, regular and line graph, Matrix tree theorem, de Brujin sequences, cycles and cut, Tutte polynomial
MAKE-UP POLICY: Make-ups for missed quizzes and exams will only be allowed for a university approved excuse in writing. Wherever possible, students should inform the instructor before an exam or quiz is missed. Consistent with University Student Rules , students are required to notify an instructor by the end of the next working day after missing an exam or quiz. Otherwise, they forfeit their rights to a make-up.
POLICY FOR ABSENCES: Attendance on a regular basis is
expected. While there are occasionally good reasons for you to
choose to miss class, my experience has been that there is a strong
correlation between attendance (as long as you are awake and
listening) and performance in the course.
For absence related to injure or illness, students who are absent from class three or more days should provide instructors with confirmation from a medical provider for an excused absence.
SCHOLASTIC DISHONESTY: Copying work done by others, either in-cl ass or out of class, is an act of scholastic dishonesty and will be prosecuted to the full extent allowed by University policy. Collaboration on assignments, either in-class or out-of-class, is forbidden unless permission to do so is granted by your instructor. For more information on university policies regarding scholastic dishonesty, see University Student Rules .
COPYRIGHT POLICY: All printed materials disseminated in class or on the web are protected by Copyright laws. One xerox copy (or download from the web) is allowed for personal use. Multiple copies or sale of any of these materials is strictly prohibited.
The Americans with Disabilities Act (ADA) is a federal anti-discrimination statute that provides comprehensive civil rights protection for persons with disabilities. Among other things, this legislation requires that all students with disabilities be guaranteed a learning environment that provides for reasonable accommodation of their disabilities. If you believe you have a disability requiring an accommodation, please contact Disability Services, currently located in the Disability Services building at the Student Services at White Creek complex on west campus or call 979-845-1637. For additional information, visit http://disability.tamu.edu .