Graph theory (Math 1230)

Announcements

• (5/4). The final class will be next Tuesday (5/9).

Course information

This is an undergraduate course in the study of graphs. Graphs appear all over the place: both in pure and applied mathematics as well as other sciences, such as chemistry, physics, computer science, and linguistics. We will focus on the theoretical aspects of graph theory, although we will also discuss some applications.

Course objectives

• learn about basic properties of graphs (bipartite, Eulerian, matchings, connectivity, colorability, planarity,…)
• prove foundational results (Menger, Hall matching, matrix tree,…);
• understand theoretical trends in graph theory (local-to-global, duality, extremal problems, Ramsey theory);
• investigate connections of graph theory to different areas (combinatorics, topology, linear algebra, probability);
• improve your ability to read/write proofs and critique arguments;
• expose you to things you haven’t seen and challenge you through problem solving.

Recommended prerequisites

Some experience with writing proofs.

Textbook

West, Introduction to graph theory

Course expenses

Just the textbook. In practice, the text may not be absolutely necessary for the course, although you may want it as a reference.

Grading

homework 35%, midterm 30%, final project 30%, participation 5%

• a grade of 90% or higher is guaranteed an A
• a grade of 80% or higher is guaranteed an B
• a grade of 70% or higher is guaranteed an C

Contact information

• (Instructor) Bena Tshishiku: bena_tshishiku at brown.edu
• TAs: Eli Sporn (eli_sporn at brown.edu) and Noah Whelpley (noah_whelpley at brown.edu)

Course events

Lectures: Tu-Th 9-10:30am

Office hours:

• Noah: Tues 7-8p in Page-Robinson 402
• Bena: Wed 11-noon (my office)
• Eli: Fri 2-3 in Kassar 205

Important dates:

• Midterm (take home): due Friday, March 24 by 5pm.
• Final projects: due Friday, April 28 by 5pm

Homework

There will be weekly assignments posted below as the semester progresses. The homework is designed to increase your engagement with the material, with your peers, and with me.

Collaboration: Please collaborate! Working together with your classmates can help you learn the material better. Some of the homework problems may be difficult, so it is recommended that you talk to someone when you are stuck. You are required to write your solutions alone and acknowledge the students you worked with. For any solution you submit, you should understand it well enough that you can explain it to someone else and answer questions about it. If you find yourself writing down things that you can’t explain, you should go back and think more about the problem.

LaTeX: Homework solutions must be typed in LaTeX. If you’re new to LaTeX, you can either download LaTex or use sharelatex which allows you download, edit, and compile LaTeX files online. See here for some commonly used symbols in LaTeX. Also Detexify is a useful tool for finding the commands for various symbols. The source code for the assignments should be a helpful guide. The most basic thing to know/remember is that math always goes in between dollar signs.

Late homework policy: For your homework grade, I will drop the score from your lowest assignment. View this as a one-time “get out of jail free card” in the event that you oversleep, forget, have a midterm, etc. As a general rule, late homework will not be accepted. If you suspect you won’t be able to submit the assignment in time, please notify me as soon as possible.

Homework assignments.

HW1 (due 2/3). tex file (type your solutions in this file), image (include in same folder as tex file), solutions, student solutions

HW2 (due 2/10). tex file, solutions, student solutions

HW3 (due 2/17). tex file, solutions, student solutions

HW4 (due 2/24). tex file, image, student solutions

HW5 (due 3/3). tex file, image, student solutions

HW6 (due 3/10). tex file, image, solutions

HW7 (due 3/17). tex file, image, solutions

HW8 (due 4/7). tex file, final project proposal

HW9 (due 4/14). tex file, final project outline

HW10 (due 4/21). tex file, final project slides

Participation

Occasionally, we may have small assignments or quizzes in class, which are graded more-or-less based on completion. These will count toward the participation part of your grade (5%).

Course materials

• Join the course campuswire page via this link. We will use this for asynchronous discussions (e.g. questions about homework).
• Some midterm solutions

Final Project

Working in groups of 2, you’ll choose a topic and create a 10-minute video. During reading period we’ll watch as many of these as we can.

Some potential topics to get you started (not in any particular order):

1. Art gallery problem
2. Graceful labelings and graceful tree conjecture
3. Szemerédi regularity lemma
4. forbidden subgraph problem
5. Tutte’s spring theorem
6. Groups and Cayley graphs
7. Counting tilings of a chessboard and the permanent of a matrix
8. Dinitz problem
9. 5 color theorem
10. stable roommates problem
11. Hall’s matching theorem for infinite graphs
12. perfect graphs
13. De Bruijn graphs
14. Errera graph and the 4-color theorem
15. Polyhedral graphs
16. Knight’s tour problem
17. circle packing theorem
18. Hamiltonian graphs
19. Frucht graph and Frucht theorem
20. unit distance graphs
21. Graph girth and cages
22. Well-covered graphs
23. Erdos-Gyarfas conjecture
24. Tait conjecture
25. graph isomorphism problem
26. Heawood conjecture
27. Tutte’s theorem (generalizing Hall)
28. Whitney’s planarity criterion
29. Linkless embeddings of graphs
30. Hadwiger–Nelson problem
31. Kasteleyn’s Theorem: Domino tilings for planar regions
32. Anything else that is related to the course and interests you!

Potential sources for further ideas:

• Sections listed as “Optional” in West
• Wikipedia here and here
• Proofs from the book has a chapter on graph theory
• Linear algebra miniatures has some sections on graph theory applications (of course this requires some familiarity with linear algebra)

Tentative schedule (subject to change)

• Week 1: Introduction (West pg 1-11, 13, 34-36, 38)
  • Thurs (1/26). Graphs, vertex degrees, isomorphism, subgraphs, what is graph theory? notes (just this once)
• Week 2: Fundamental concepts (West 19-30, 44-46)
  • Tues (1/31). degree sequences, bipartite graphs
  • Thurs (2/2). bipartite graphs, Eulerian graphs, counting trees
  • Fri (2/3). HW1 due
• Week 3: Trees (West 68-71, 73-75, 81-83)
  • Tues (2/7). characterization of trees, Cayley’s theorem
  • Thurs (2/9). Cayley’s theorem, spanning trees, Bridg-it
  • Fri (2/10). HW2 due
• Week 4: Matchings (West 107-115)
  • Tues (2/14). matchings, Hall’s theorem, vertex covers
  • Thurs (2/16). maximum matchings, Konig’s theorem, Hall’s theorem
  • Fri (2/17). HW3 due
• Week 5: Matchings (West 130-132)
  • Tues (2/21). No class (university holiday)
  • Thurs (2/23). Konig’s theorem, stable matchings, Gale-Shapely
  • Fri (2/24). HW4 due
• Week 6: Connectivity (West 149-150, 167-168, 176-181, 183)
  • Tues (2/28). vertex cut, Menger’s theorem, flows on networks, matrix-tree theorem
  • Thurs (3/2). Menger’s theorem, Ford-Fulkerson, sports elimination
  • Fri (3/3). HW5 due
• Week 7: Coloring (West 191-194, 204-208)
  • Tues (3/7). Chromatic number, greedy coloring, Brooks’ theorem, Mycielski construction, extremal problem
  • Thurs (3/9). Turan graphs, chromatic polynomial, sudoku
  • Fri (3/10). HW6 due
• Week 8: Planarity (West 6.1-6.2)
  • Tues (3/14). chromatic polynomial, planar graphs, Kuratowski’s theorem
  • Thurs (3/16). Kuratowksi’s theorem, linear planar embeddings, untangle
  • Fri (3/17). HW7 due
• Week 9: Planarity
  • Tues (3/21). Art gallery problem, map coloring, platonic solids
  • Thurs (3/23). No class (work on the midterm)
  • Fri (3/24). Take-home midterm due at 5pm.

• Week 10: Spring Break

• Week 11: Ramsey theory (West 8.3)
  • Tues (4/4). Ramsey theory for graphs, numbers, and knots
  • Thurs (4/6). No class: work on your final project!
  • Fri (4/7). HW8 due
• Week 12: Ramsey theory, Random graphs (West 8.5)
  • Tues (4/11). Ramsey lower bound, random graphs
  • Thurs (4/13). Connectedness and diameter of random graphs, Rado graph
  • Fri (4/14). HW9 due
• Week 13: Random graphs, Spectral graph theory (West 8.6)
  • Tues (4/18). Erdos-Renyi random graphs, phase transitions, Rado graph properties
  • Thurs (4/20). Adjacency matrix and its eigenvalues, matrix tree theorem, Cauchy-Binet
  • Fri (4/21). HW10 due
• Week 14:
  • Tues (4/25). matrix tree theorem, graph Laplacian
  • Thurs (4/27). No class: finish your final project!
  • Fri (4/28). Final project due
• Week 15: final projects
  • Tues (5/2). presentation watch party (art gallery problem, de Bruijn graphs, infinite Hall, 4-color theorem, register allocation, Dinitz problem, Tutte’s generalization of Hall’s theorem)
  • Thurs (5/4). presentation watch party (Good Will Hunting, ant colony optimization, stable roommates problem, knight’s tours)
• Week 16: final projects
  • Tues (5/9). presentation watch party (end of course)