We will learn ...
This course focuses on graph structures—the connectivity, the planarity, and the minors. We will see how Menger's theorem characterizes the connectivity of a graph. On the other hand, Kuratowski's theorem shows that a graph is planar if and only if it does not contain \(K_5\) nor \(K_{3,3}\) as a minor. We will study the notion of minors and topological minors of a graph and see various families of graphs that are characterized by certain forbidden minors. In the end, we will go deeper into graph minors and study tree-width, tangle, the graph minor theorem, and so on.
Connectivity
cut-set, internally disjoint path, and Menger's theorem
Planar graphs
drawing a graph on a plane without crossing edges, forbidden structure, and Kuratowski's theorm
Graph minors
a smaller graph with the similar structure and the graph minor theorem
Colin de Verdière parameter (optional)
a linear algebra characterization of the planar graphs
You need to do ...
HW0: Tell me your email before September 13 to get extra 2pt — this is a required work. Important information will be announced through email.
Homework (30%): The homework will be assigned weekly in class. You have to use \(\LaTeX\) to type your work.
Active Learning (10%): Learn actively and regularly. Reflect on what you have learned. Post a photo on Padlet, write a few sentences about what you have learned, and leave your student IDs. Names are optional. Each post before the final exam counts as 0.25 point.
Connectivity
Midterm 1 (20%): [ pdf ]
Planar graphs
Midterm 2 (20%): [ pdf ]
Graph minors
Survey (20%):
A few tips for learning mathematics ...
Mistakes Make You Smarter: Everyone learns through experiences and mistakes. For each new concept you learn, generate as many examples as possible to train your brain to distinguish between right and wrong.
Ask Questions: Beyond knowledge, mathematics is fundamentally about logic. Question everything you encounter—why it is defined this way, why an assumption is required, why a proof needs a particular step, and so on.
Think Carefully: Sound arguments should hold true in any circumstance. Verify the examples you generate to ensure they align with your argument.
Help Each Other: Learning together can make the process easier. Teaching others is also an effective way to reinforce your own understanding.
Course Info
- Term: Sep 9, 2024 – Jan 10, 2025
- Meeting time: Tuesday, 2:10 pm – 5:00 pm @ SC4013
- Instructor: Jephian Lin | 林晉宏
- Email: chlin [at] math.nsysu.edu.tw
- Office: SC2002-5
- Office Hours: Monday, 3:10 pm – 5:00 pm
- Office Hours: Thursday, 3:10 pm – 5:00 pm
- Discord: https://discord.com/invite/behbC9NmqNJ
Textbook
Graph Theory
Reinhard Diestel
***** NSYSU has subscription to the electronic version of this book; visit Springer's website here through the school internet to access the book*****Course website
Tentative Schedule
Policies/Ethics
Accessibility
Students with diverse learning styles and needs are welcome in this course. In particular, if you have a disability/health consideration that may require accommodations, please feel free to approach me.
Grading
Percentage scores will be converted to letter grades according to the university-wide standard table.
Attendance
You are expected to attend the classes.
Missing work
If you miss some course components due to illness, accident, family affliction, or religious observances, please talk to me and provide the documentation. In such cases, the course component is excused, and your course score will be calculated by distributing the weight of the missed item(s) across the other course components. Missing components are limited to at most 20%.
Academic integrity
Do not copy others' work, including others' homework, the textbook, online materials, and others' answers in an exam; if it is really necessary, add proper citations to your references. It makes no point (and gives you no point) if the work is not yours since you learned nothing.