Partially Ordered Thoughts

While the course I’m teaching this semester is called Applied Combinatorics, I do try to incorporate some theory into the course. The handful of math majors in the course generally thrive on these days. However, the vast majority of the students are computer science and computer engineering majors. In the past, theory-intensive days were the days where their eyes glazed over and they followed nothing or else they nodded in their sleep and suggested that they understood. This semester, I’m trying to do a lot more active learning in my classes, and theory days are good candidates.

My first big foray into doing something other than using clickers and peer instruction or just some small-group problem solving in this course came today. There’s a famous result in graph theory that says there are triangle-free graphs with arbitrarily large chromatic number. This is a great way to help computer science majors understand that determining a graph’s chromatic number is not just about finding cliques or computing vertex degrees. There are two common constructions used to prove this result. Last time I taught the course, I lectured on one construction and told the students to read the other. Massive failure was the result. This time, I got creative and pulled out an active learning technique called jigsaw. I’d been hankering to find a place for it in one of my math classes, and I’m pleased to say it went well.

What is jigsaw? Here’s a summary from Arizona State. Let’s say you don’t want to read that, and I’ll give the quick outline:

1. Break up the material the students are to encounter based on the sizes of your groups. (In my case, we use groups of four.)
2. Give each “position” in the group a portion to learn. (I use playing cards, inspired by Barbara Millis.)
3. Give the students some time to work with the material outside class.
4. When they come to class, have students form “expert” groups. (Clubs in one corner, etc.)
5. Give students some time to clear up any issues they have and figure out the best way to present to group members.
6. Have students re-form their usual groups and explain the material to their peers.
7. Conduct some sort of debriefing for the whole class.

How did I implement this? I assigned two suits to each construction (one of the constructions is particularly hard for them to wrap their heads around, so having two heads helped). Of the two suits assigned to a construction, one was also responsible for establishing the graph’s chromatic number while the other tackled the lack of triangles. The handout I gave them in advance for reading took the proof from the book and broke it down into smaller steps with questions for them to think about as they worked through it while preparing and to guide the discussion in class.

Leading up to class, I was a little worried about how it was all going to turn out. What if half my class didn’t show up? What if the students resisted (even though we’ve been doing lots of group work)? What if they couldn’t figure it out and gave up in disgust? Fortunately, none of my fears came to pass. Out of 16 groups, only a handful reported only having two or fewer members present. (I had those groups come meet with me so that I could see about merging them for the day, but the suits didn’t work out, so we played it by ear.) The expert group meetings ran a little long, but it was good for them to work through things. Some of the expert groups got a lot from one or two very well-prepared group members. Others needed a little help from me. However, they were really engaged when I met with them. It was like teaching a small class of 16 inside my class of 64, and I did it with only my hands as visual aids.

When the students shifted back into their regular groups, things just kept on rolling. Some groups were really stuck, so I helped them out. However, I’d say that of my 16 groups, there were only three I spent any significant time with. One of those was a group that was shorthanded and wanted to work through both constructions, so that barely counts. Through the whole class, almost all the students were thoroughly engaged. They were really working hard to figure out what was going on and to get a grasp on things. Did the students leave class understanding every single detail? Of course not. However, I’m skeptical that any student other than my A students walked out understanding any details with straight lecture last time. This time, my students got to see some of how mathematicians struggle through things. The computer science majors got a feel for why computing a graph’s chromatic number is hard, something that it’s not clear their undergraduate CS classes provide.

Today I managed to save enough time to debrief the activity properly, too. We didn’t run through the constructions or anything like that. However, I made sure to help the students get the take-aways that I mentioned above. I made it super-clear to them that I wasn’t worried about them reproducing parts of the proofs or the constructions. Today was about the experience and helping my students develop the gut-level intuition you need in combinatorics. I hope I was successful. I left them with the result that there are graphs with arbitrarily large girth and chromatic number and told them that we have to get at those graphs through probability and not a construction. I was thrilled to look out at their faces and see a genuine appreciation of such a result.

On Wednesday, we move from graph theory to posets. This is the chapter of our book that needs the most work. (Tom and I need to take a step back and stop writing for our usual poset audience and write for our usual textbook audience.) However, I’ve got enough days that I can pace the material with some more experiences like today. Does anyone else have thoughts on topics in the math curriculum where jigsaw would be a good tool? I’m eager to try it with trig substitution next time I teach calculus but would be curious to hear about others’ successes or just ideas.