Bena Tshishiku

Bena Tshishiku

Mathematician

Graph theory (Math 1230)

Undergraduate course, Brown University, 2023

Announcements

  • (1/18). This webpage has the syllabus for the course. Please read it carefully.

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.

Some experience with writing proofs will help.

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 30%, midterm 20%, final project 20%, final exam 20%, participation 10%

  • a grade of 92% or higher is guaranteed an A
  • a grade of 84% or higher is guaranteed an B
  • a grade of 76% or higher is guaranteed an C

For students taking this course S/NC, a minimum grade of 70% and a minimum participation grade of 70% is required to guarantee a grade of S.

Contact information

  • (Instructor) Bena Tshishiku: bena_tshishiku at brown.edu
  • TAs: Rafi Ash (rafael_ash at brown.edu)

Course events

Lectures: MWF 9-9:50 in Smith-Buonanno Hall G13

Office hours:

  • Bena: TBD
  • Rafi: TBD

Important dates:

  • Midterm:
  • Exam: Thursday, May 7 at 2pm
  • Final projects: presented in class during reading period

Homework

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

Collaboration is encouraged. Working 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. That said, 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: As a general rule, late homework is not accepted. I know things happen, so I will drop your lowest assignment. For exceptional circumstances, please email me.

Homework assignments.

HW1 (due 1/30).

Participation

Occasionally, we may have assignments or quizzes in class. These will count toward the participation part of your grade (10%).

You can also participate by coming to office hours and coming to

Final Project

Working in groups of 2, you’ll choose a topic related to the course to investigate and create an N-minute presentation to be given during reading period. To help you prepare for this, I will ask you to submit a draft outline of your talk and a draft of your slides.

Tentative schedule (subject to change)

  • Week 1: Introduction (West pg 1-11, 13, 34-36, 38);
    • Wed (1/21). Graphs, vertex degrees, isomorphism, subgraphs
    • Fri (1/23).
  • Week 2: Fundamental concepts (West 19-30, 44-46);
    • Mon (1/26). degree sequences, bipartite graphs, Eulerian graphs, counting trees
    • Wed (1/28).
    • Fri (1/30). HW1 due
  • Week 3: Trees (West 68-71, 73-75, 81-83)
    • Mon (2/2). characterization of trees, Cayley’s theorem, spanning trees, Bridg-it
    • Wed (2/4).
    • Fri (2/6). HW2 due
  • Week 4: Matchings (West 107-115)
    • Mon (2/9). matchings, Hall’s theorem, vertex covers, maximum matchings, Konig’s theorem
    • Wed (2/11).
    • Fri (2/13). HW3 due
  • Week 5: Matchings (West 130-132)
    • Mon (2/16). No class (university holiday)
    • Wed (2/18). Konig’s theorem, stable matchings, Gale-Shapely
    • Fri (2/20). HW4 due
  • Week 6: Connectivity (West 149-150, 167-168, 176-181, 183)
    • Mon (2/23). vertex cut, Menger’s theorem, flows on networks, matrix-tree theorem, Ford-Fulkerson
    • Wed (2/25).
    • Fri (2/27). HW5 due
  • Week 7: Coloring (West 191-194, 204-208)
    • Mon (3/2). Chromatic number, greedy coloring, Brooks’ theorem, Mycielski construction, extremal problem, Turan graphs, chromatic polynomial
    • Wed (3/4).
    • Fri (3/6). HW6 due
  • Week 8: Planarity (West 6.1-6.2)
    • Mon (3/9). chromatic polynomial, planar graphs, Kuratowski’s theorem, linear planar embeddings
    • Wed (3/11).
    • Fri (3/13). HW7 due
  • Week 9: Planarity
    • Mon (3/16). Art gallery problem, map coloring, platonic solids
    • Wed (3/18).
    • Fri (3/20).

  • Week 10: Spring Break

  • Week 11: Ramsey theory (West 8.3)
    • Mon (3/30). Ramsey theory for graphs, numbers, and knots
    • Wed (4/1).
    • Fri (4/3). HW8 due
  • Week 12: Ramsey theory, Random graphs (West 8.5)
    • Mon (4/6). Ramsey lower bound, random graphs, connectedness and diameter of random graphs, Rado graph
    • Wed (4/8).
    • Fri (4/10). HW9 due
  • Week 13: Random graphs, Spectral graph theory (West 8.6)
    • Mon (4/13).
    • Wed (4/15).
    • Fri (4/17). HW10 due
  • Week 14:
    • Mon (4/20).
    • Wed (4/22).
    • Fri (4/24).
  • Week 15:
    • Mon (4/27). final projects
    • Wed (4/29). final projects
    • Fri (5/1). final projects
  • Week 16:
    • Thurs. Final exam 2-5pm