MATH 613-600. Graph Theory

Fall, 2017, MWF 10:20- 11:10a.m., BLOC 121

    Instructor: Dr. Catherine Yan

    Office: BLOCKE 513F

    E-mail: cyan@math.tamu.edu,

    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.

    Textbook.

    Introduction to Graph theory, by Douglas West, second edition, Prentice Hall, 2001.
    Also a main reference: A Counrse in Combinatorics, by J.H. van Lint and R.M. Wilson, 2nd edition, Cambridge University Press.

    Grading: Homework assignments will be given about bi-weekly. As exercise is an important part of combinatorics, anyone who doesn't hand in homework fails the course automatically. No late home work will be accepted except for university-approved excuses.

    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).

    Announcement:


    1. There is no class on October 20.


    2. The last lecture in on Dec. 4.


    First-day Handout

    Homework Assignments. All homework assignments will be available through e-campus at least one week before the due date.

    Homework 0: During the first week of school, please send me an email introducing yourself.
    Homework 1. Due on Sep 15 in class.
    Homework 2. Due on Sep 29 in class.
    Homework 3. Due on Oct 18 in class.
    Homework 4. Due on Nov. 3 In class.
    Homework 5. Due on Nov. 17 In class.
    Homework 6. Due on Dec. 4 in class.

    Description of Project

    See the pdf file here. The report is due on Dec 6, 2017. Please submit your project through email.

    List of topics/main references for the projects

    This is the list of topics that some students have chosen to work on for their projects.

    Topics to be covered

    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

        Main References

    2. Modern graph Theory, by Bela Bollabas, Graduate Texts in Mathematics 182, Springer 1998.
    3. Algebraic Graph Theory, by Norman Biggs, Cambridge Universtiy Press, 1993.
    4. Introductory Combinatorics, by Richard Brualdi, fifth edition, Prentice Hall, 2010.
    5. Combinatorics: The Rota Way, by Kung, Rota and Yan, Cambridge University Press, 2009
    6. The Probabilistic Method, by Alon and Spencer, second edition, John Wiley & Sons, Inc, 2000.

    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 .

    Title IX and Statement on Limits to Confidentiality
    Texas A&M University and the College of Science are committed to fostering a learning environment that is safe and productive for all. University policies and federal and state laws provide guidance for achieving such an environment. Although class materials are generally considered confidential pursuant to student record policies and laws, University employees — including instructors — cannot maintain confidentiality when it conflicts with their responsibility to report certain issues that jeopardize the health and safety of our community. As the instructor, I must report (per Texas A&M System Regulation 08.01.01) the following information to other University offices if you share it with me, even if you do not want the disclosed information to be shared:

    These reports may trigger contact from a campus official who will want to talk with you about the incident that you have shared. In many cases, it will be your decision whether or not you wish to speak with that individual. If you would like to talk about these events in a more confidential setting, you are encouraged to make an appointment with the Student Counseling Service (https://scs.tamu.edu/).

    Students and faculty can report non-emergency behavior that causes them to be concerned at Tell Somebody .