I taught two courses for Columbia Splash this fall, each one hour long. The first was an introduction to graph theory, and the second was an introduction to mathematical modeling. The graph theory course was entirely new. I taught math modeling at Columbia and MIT last fall in two hour blocks, so this course was modified from that version.
Bridges, Maps, and Networks: An Introduction to Graph Theory
A lot of intro graph theory courses start by defining a graph, vertices, and edges and then cover some basic types of graphs and some results related to those graphs. I wanted to give more of a sense for key areas of graph theory, the history of the field, and how graph theory is used, so I structured this class around the bridges of Königsberg, the four color problem, and network models.
I started with bridges of Königsberg. I drew two maps with the same number of land masses and bridges but with the bridges distributed differently. One was the classic Königsberg arrangement; the other had an Eulerian path but no Eulerian circuit. I posed the problem of walking over all the bridges exactly once, and then I gave the students about a minute to think on their own. After that minute, I told them to talk in pairs or groups of three, checking their paths if they found them and thinking about why there couldn’t be a path if they thought that was the case. After a couple more minutes (and some really great conversations; I was pleased), we took a vote, and everyone agreed that the first layout had no solution and the second layout did have one.
I confirmed this, though with everyone agreeing, my confirmation didn’t feel necessary. I asked if anyone had ideas for why the first map didn’t have a solution, and someone brought up odd numbers of bridges right away. I filled in the explanation — we can only have an odd number of bridges at the places where we start and end — and then wrote out the theorem for this. I defined Eulerian path here for sure, and I think degree as well. I don’t remember if this is where I introduced edge and vertex. Then I put up the theorem for Eulerian circuits as well because circuits had come up in the discussion about parity. I babbled a little bit about how there are whole areas of graph theory around knowing certain types of paths or cycles exist, finding them, or counting them. I wasn’t as prepared for that as I should have been, and I think I’d like to expand that to talking about finding certain structures in graphs; that feels more relevant to graph theory as a current field.
The four color problem section was less interactive, and I’m worried I lost the group, especially in the proof of the five color theorem (which properly done, could be an entire class…). I posed the question in terms of a map and then said that there were really two embedded questions. The main one was whether or not every map could be colored with only four colors, but the second, somewhat implied one was whether there were any maps that required four. I gave everyone a minute to try to find one that required four. No one did, and I got a response from someone that indicated that I may not have communicated what I was asking as clearly as I wanted. (Some people definitely got the question, but not everyone.) I drew a circle with a concentric circle and the outer annulus divided into three parts to show them that there are maps for which we definitely need four.
And then I jumped to proving the five color theorem (after first explaining why I wasn’t proving the four color theorem). I explained what a dual was (and got a clarifying question!) and then told them to take two things for granted: duals of maps are planar, and all planar graphs have a vertex of degree at most five. I was about to start the proof when I remembered that it was inductive, and I asked if anyone had seen induction. Of the 19 or so students, one person thought they’d maybe seen it, and everyone else said no. I gave a quick ladder-based explanation, but I should have prepared that more and spent more time there. (I got a question about it later that I hope helped, but I definitely went too fast in here.)
Okay, then for the actual proof. I stopped and asked if there were questions a couple of times, and people seemed okay, but this is pretty tricky. It seemed like people got it, or at least the basic idea, but if I were to do this again I would slow it down. I meant to talk about chromatic graph theory as a broader field after I finished the proof, but I forgot; I ended up circling back to it right before ending class.
I moved on to networks, and I tried to introduce that section by asking what they all thought we could use graphs to represent. I got a lot of silence and one person who said pretty much anything. She wasn’t wrong, but that was hard to go off of; I said that they were really versatile but some things were better modeled as graphs than others. I talked some about social networks (online and offline) and about spread of information or disease through them. That was a good opportunity to talk about choice in modeling and about refining models so that they’re more realistic. This is the section of class that needs the most work; I felt like I was floundering a little at the end. I had expected more response to work off of.
So, this class felt like it started well and then went downhill a bit, but to some extent that was predictable; I was winging the last section by far the most. I plan to teach this class again (maybe at Columbia in the spring), and the network portion is the one I should either develop more or scrap in favor of something else.
This class was smaller, 12-15 students. I started off with a problem that I’ve always used at the start in the past, but I tried to frame it differently. (Spoiler alert: it crashed and burned.) The problem is the computer problem included in the GAIMME report, but instead of starting with the table of performance and ease of use ratings, I first asked the students what factors someone might consider when choosing a computer and got a pretty good list of answers. At that point, I said these were a lot of factors to try to consider all at once and that something we often do in modeling is to start small and then build up from there, so we’d just look at two factors to start.
I told the students to think about having a list of computers, each with a 1-10 rating for two factors. How would figure out which computer was best? How would they combine the ratings?
A lot of things went wrong at this point. I did a bad job choosing two factors. Thinking about the rating for price is hard; is a higher rating a higher price? I also initially chose a pair that didn’t make sense with the numbers I planned to put up a little later. I also didn’t communicate as well as I should have; the first answer I got from a student was thinking more from a manufacturer’s point of view, about pricing a more efficient computer more highly. When I did clarify that, I still didn’t get the typical answers. Someone said efficiency/price (thinking of low price instead of a high price rating), and someone said whichever was closest to the average. I put up the numbers I had at this point, hoping it would help, and realized I needed to switch from efficiency to usability, which didn’t improve things. After not getting anything else, I went ahead and put up addition or multiplication of the factors as common solutions.
I then went through and marked which computer won for each combined measure and tried to talk about the strengths and pitfalls of each measure, but I was talking a lot to try to regain some control and direction. I then said that we could then think about how to include other factors and that we could weight different factors differently. Someone asked about that, so I gave a linear combination example.
Luckily, the next part of the class went much better. I had the students work in pairs or groups of three on the GAIMME hot dog stand problem (though I said it was a taco truck instead). I told the students before they started working that they should feel free to ask me questions but that lots of the time, my response was going to be “You get to decide, but state whatever you decide as an assumption.”
Not everyone was engaged, and some people weren’t engaged very deeply, but at least half the class was having really amazing conversations and trying different things with this problems. I wandered around the classroom, listening and asking groups what they were thinking about. After maybe five minutes, I brought everyone back together. (I was kind of loathe to do so because I knew I was interrupting some people’s thinking, but it felt like the best choice overall.) We talked about different assumptions and approaches to the problem, and we really didn’t end up talking about solutions, which was refreshing and kind of perfect. I don’t think I even realized it at the time, but that’s exactly the focus I want. I had overheard one student talking about some additional information that would change her answer, so I asked her to share, and we got a list going of ways that we could change or extend the problem.
I felt underprepared for the next part, but I think it went well, even if some of it was an exercise in not judging student answers. I posed this problem, but I was more general — didn’t say how many parks or which parks, didn’t tell the students what data was provided. I just told them the question was about assessing risk for sea level rise at National Parks, and I asked them what information they would want to know. We built up a long list of information, some relevant to the question of assessing risk and some more related to potential extension questions. After getting a lot of answers, I told them that the question was from a contest and that, while people were allowed to look up whatever they wanted, the information provided was about past and present sea level rise and that the most basic goal was to predict future rise. I talked a bit about potential approaches from there and about how the other information they’d brought up could be relevant to related questions.
Ideally, I’d like to not be talking about potential approaches myself, but this all felt a little too open to hand that to them. “Say you have data about sea level rise; what do you do with it?” sounded a lot like the question that hadn’t gone well earlier, and it really can be easier to know what you want to do with data when you can play around with it a bit. I was talking to someone about this class later, and they mentioned that students might sign up for it if they’re interested in thinking about math more concretely and less abstractly, and that might have been part of what went wrong earlier.
I closed the class by talking about some common types of models, focusing on two models for disease: SIR compartmental models and graph/network models. I explained the basic idea of compartmental/stock-and-flow models and then pretty much repeated my graph model explanation from the hour before. We talked a bit (there was at least one question) about when you might want to use which type.
In contrast to graph theory, this class started badly but got better. I’m teaching this at MIT in a couple of weeks, so I’m thinking about how to rework the beginning. I have a few different options. I’m going to try one in a microteaching session at school soon, so we’ll see how it goes.