Teaching objectives
A university lab in Optimisation and Discrete Mathematics about a single problem that turns up in five disguises: pairing up students who get along, putting cameras on the streets of a neighbourhood, choosing a different delegate for each club, sharing documents among translators and assigning students to internships. Blocks A, B and F work from upper secondary school.
The thread is that a maximum matching is proved. A "this is maximum" is certified by a cover of the same size (König), a "there is no perfect matching" by a Hall set, and an optimal assignment by a reduced matrix with independent zeros. The lab never says "this is optimal" without showing the certificate.
The order follows experience, not the table of contents of a textbook chapter. The first room uses no technical word at all: the student pairs people up by hand and gets stuck. "Maximal" and "maximum" are only named once the difference has been lived with a marker that cannot be erased. In every room that computes a number (ν, τ, the optimal cost, how many swaps are needed), the student first writes down a prediction.
What is learned
- Telling a maximal matching (no edge can be added) from a maximum one (as many edges as possible), and seeing why the greedy method stops at the first.
- Improving a matching by flipping an augmenting path, and recognising when there is none left (Berge's theorem).
- Following the augmenting-path algorithm step by step, with its depth-first search and its failing branches, and the obstacle of odd cycles that Edmonds overcame.
- Understanding vertex covers and the inequality ν ≤ τ, and seeing that equality holds in bipartite graphs (König's theorem).
- Studying a matching and a cover together through the concordant pair and its defect, and bringing the defect down to zero with two operations: change only M or change only C.
- Deciding whether one side of a bipartite graph can be saturated, always with a certificate: the matching, or a set S with |N(S)| < |S| (Hall's theorem), and applying it to regular boards and a card trick.
- Solving assignment problems with costs by the Hungarian method, understanding why subtracting a constant from a row or column does not change the solution, and why the minimum number of lines is König again.
- Finding blocking pairs, following the Gale–Shapley algorithm round by round and checking that whoever proposes comes out ahead.
- Seeing what a perfect matching chosen at random looks like (block G): domino tilings of the Aztec diamond and lozenge tilings of a hexagon, in which the arctic circle appears.
Key mathematical ideas
- Every result comes with a certificate. Matching and cover keep watch on each other: every pair needs its own camera, so |M| ≤ |C| always, and when they are equal neither can be improved.
- An augmenting path gains exactly one edge. It has one more edge outside M than inside. That is why, starting from nothing, reaching a perfect matching in a 7 + 7 graph always takes 7 swaps.
- The defect counts the free vertices of C. In a concordant pair, f = |C| − |M| is exactly the number of cover vertices left without a partner. The two operations lower it; in a bipartite graph it always reaches zero, and then both certificates are there at once.
- Odd cycles are the obstacle. In the triangle or the pentagon ν < τ, and the defect does not drop below 1.
- Hall is necessary and sufficient. If no group of clubs has fewer candidates than clubs, there are delegates for all. On a board where every row and column has r painted squares, n rooks always fit, and a deck dealt into 13 piles of 4 always yields all 13 values.
- Subtracting from a line lowers every total by the same amount. The order of the assignments does not change, and an all-zero assignment in a matrix without negatives is optimal.
- Whoever proposes wins. Both versions of Gale–Shapley give stable assignments, each the best possible for the proposing side.
Credits
The rooms "Concordant pairs", "Operation 1", "Operation 2", "Zero defect" and "Rooks on painted squares" are based on the worksheet Паросочетания и покрытия by Vania Yakovlev (Кроссворд Тьюринга, https://d1-d57.github.io/matchings/), where the notions of concordant pair and defect come from.
Classroom notes
- "The permanent marker" explains the difference between maximal and maximum in thirty seconds.
- "Operation 2": the chain reaction works very well projected. Ask the class whether the chain will close before launching it.
- "Zero defect": the moment when M and C certify each other is the best introduction to König's theorem.
- "The card trick": shuffle three or four times in front of the class and ask a volunteer to find the choice.
- Secondary-school route: blocks A → B → F. Blocks C, D and E need university level, and E relies on the room "Zero defect".
Room-by-room contents
Room 1 · Partners for the lab session
Twelve friends who want to work in pairs; each line is a friendship. With no technical word at all, the student forms pairs by tapping lines or both friends. The graph (a 3 × 4 grid with some diagonals) has exactly one way to pair up all twelve; choosing at random gets stuck 94% of the time, and in most dead ends undoing a single pair is not enough. The room detects every dead end and invites the student to undo; after two it names who is left alone and after four it shows the solution.
Student tasks
- Form six pairs so nobody is left alone.
Room 2 · The permanent marker
Pairs are drawn with a marker and cannot be undone, and on each board someone has already marked one in a hurry. When nothing more fits, the student says whether, starting from scratch, more pairs could be formed. The three boards are chosen so that intuition fails: on the first one it can always be improved, on the second two vertices are left free and still not a single pair more fits (removing the centre leaves three triangles), and on the third it depends on what was marked. Then come the definitions of maximal and maximum with two separate questions about them, and a final challenge: if the marker gets stuck with 5 pairs, the maximum has at most 10.
Student tasks
- Decide on three boards whether more pairs could be formed.
- Say whether every maximum is maximal and whether every maximal is maximum.
- Bound the maximum from a maximal matching with 5 edges.
Room 3 · How many pairs can be formed?
Four graphs in which «half the vertices» is not the answer or is not obvious: a tree with 9 vertices (ν = 3), two centres with four triangles (14 vertices, ν = 6), the 4 × 4 board without two opposite corners (ν = 6) and the Petersen graph (ν = 5). The student predicts ν while looking at the graph and then has to build a matching of that size by hand; the explanation only appears if the prediction is wrong. It ends with a Tutte-style argument (20 vertices; removing one leaves 5 odd pieces: at most 8 pairs). The board challenge links to the dominoes of the Polyominoes lab.
Student tasks
- Predict ν for four graphs and build a matching of that size.
- Bound ν with the odd-pieces argument.
Room 4 · The swap
It starts with an animation on a small graph: what an augmenting path is and what it is not (one ending with a blue edge, another with two unused edges in a row), a path that is augmenting, drawn edge by edge, and the animated swap, which adds one pair. It can be replayed from every challenge. Vertices carry no names. Challenges: an 8-vertex (2 × 4) ladder with two pairs already marked that fit together in no perfect matching: with single edges one always gets stuck at 3, and reaching 4 requires a path of at least 3 edges (it ends by pressing «It is already maximum», which is checked); a unique 5-edge augmenting path with dead-end branches; a 12-vertex graph needing two swaps without being told; a 6 + 6 bipartite graph with a unique 7-edge path; and the numerical question about M △ M′ (|M| = 5, |M′| = 8: at least 3 augmenting paths).
Student tasks
- Watch the animation of the augmenting path and the swap.
- Grow an empty matching up to the maximum.
- Find and swap augmenting paths with 5 and 7 edges, and reach the maximum with two swaps.
- Bound how many augmenting paths there are in M △ M′.
Room 5 · Find the path
Three graphs with a maximal matching that is not maximum; in each one the student has to find an augmenting path (any will do) and apply it. In the first, a 6 + 6 bipartite graph with four free vertices, there are only two paths, of 5 edges, and both leave the free vertex b3: b2 is the end of none of them, so starting there wastes time. The second (12 vertices, non-bipartite, with triangles) has two free vertices and a single 7-edge path; the forks are real and the edge from 8 to 9 leads to a dead end. The third is a blossom: the path goes round a 5-vertex cycle the long way, and the short cut between the two free vertices does not alternate. Solving it brings in Edmonds (1965) and the problem of odd cycles. After three failures in a row the path is shown.
Student tasks
- Find an augmenting path in the bipartite graph, choosing the starting free vertex well.
- Find the only path in a graph with triangles and dead ends.
- Solve the blossom and see why the short cut does not work.
Room 6 · The final-year projects
The augmenting-path algorithm run by hand. Six students (a1…a6) apply for projects among six (b1…b6), each only among those they like, and they are processed in turn: on each turn the student must mark an augmenting path that starts exactly at whoever's turn it is (any other starting point is rejected). If every student simply took the first free project on their list, the turns of a5 and a6 could only be solved by moving others: chains of 3 and 5 edges. After each swap the next turn starts on the same board. Then, on a random 7 + 7 bipartite graph with no perfect assignment (ν is 5 or 6), the student predicts at most how many students can get a project; if wrong, the room shows the group of students with fewer projects than students and, if the answer was too low, an assignment. The final challenge uses another 7 + 7 graph, from a set of hard ones (ν = 6, 18-20 edges and only 4 maximum matchings): build a maximum matching from scratch and decide yourself when to press «It is already maximum», which only works when it is.
Student tasks
- Mark the augmenting path of each student, from a1 to a6.
- Predict how many students can get a project in a random 7 + 7.
- Build a maximum matching from scratch and recognise when it cannot be augmented any further.
Room 7 · Is it maximum yet?
Berge's theorem as a decision: four boards with a marked matching and the question «is it maximum, or can it be augmented?». The first two are 6 + 6 bipartite graphs: in the first, four vertices are left free and there are two 5-edge paths; in the second only two are free and there is none (a3, a4, a5 and a6 only have edges to b4, b5 and b6). The other two are non-bipartite, with 12 vertices: in the third there are alternating chains of up to 10 edges that end at a taken vertex, and yet it is maximum; in the fourth there is a single 7-edge path. Whoever says «it can be augmented» has to mark the path; whoever says «it is maximum» and is wrong has to go and find it. Choosing the wrong branch counts as a failure, and after three failures the room shows the path or, for the maximum ones, the longest chain that reaches a dead end and the reason for the bound. Getting «it is maximum» right does not require a proof: for now the student is taken at their word. It ends with the statement of Berge's theorem.
Student tasks
- Decide on four boards whether the matching is maximum or can be augmented.
- Mark the augmenting path when there is one, also in non-bipartite graphs.
- Tell a long alternating chain that reaches no free vertex apart from a real augmenting path.
Room 8 · Pairs versus cameras
Cameras at the crossings of a neighbourhood with 14 crossings and 17 streets (a 3 × 6 grid with gaps): every street that is watched lights up. Three challenges. First the minimum number of cameras is predicted and then placed: coloured like a chessboard, the 7 crossings of one colour already watch everything, but the minimum is 6, unique, and mixes both colours. Second, in the same neighbourhood, build at the same time a matching M and a cover C with |M| = |C| = 6. Third, the Petersen graph (3-regular, 15 streets): what is τ? The first hint recalls that each camera watches 3 of the 15 streets; the second, that 5 cameras would watch 5 · 3 = 15 streets, exactly all of them, with no street having a camera at both ends, and asks to look at the outer pentagon. When the challenge ends (whether answered correctly or missed three times) the board always shows a cover with 6 cameras and the proof that 5 are not enough: with 5 cameras every street would have a camera at exactly one end, so along any cycle the crossings would alternate «camera» and «no camera», which is impossible in the outer pentagon (5 vertices, an odd number); hence τ ≥ 6, and the board shows that 6 are enough. Every unwatched street and every extra camera is pointed out when checking.
Student tasks
- Predict and place the minimum number of cameras (6) that watches every street.
- Build at the same time a matching and a cover of the same size.
- Find τ in the Petersen graph and follow the proof that 5 cameras are not enough.
Room 9 · How big can ν be?
Given τ, which values can ν take? First there is an unscored exploration: two sliders (τ from 3 to 7 and the number of triangles t) draw t disjoint triangles plus τ − 2t loose edges and write τ and ν = τ − t underneath, with nothing explained yet. Then the student builds with a palette of pieces that are added as disjoint components and can be removed (edge, path of 3, triangle, 4-cycle, 5-cycle and K₄); τ and ν of the whole graph are not shown live, only when pressing Check. Challenges: τ = 6 with ν as small as possible (3, three triangles), τ = 6 with ν as large as possible (6, pieces with τ = ν such as edges) and τ = 7 with ν = 4 using at most 3 pieces, which forces two triangles and a 5-cycle or a K₄. If the graph has τ = 6 but a ν that is not the extreme, the room says a smaller or larger one can be obtained. Then, with τ = 9, which values can ν take? Any from 5 to 9; every wrong option is refuted with its counterexample. At the end the theorem ν ≤ τ ≤ 2ν stays on screen with the proof of both inequalities.
Student tasks
- Explore with two sliders how τ and ν change.
- Build with pieces a graph with τ = 6 and minimum ν, another with maximum ν, and another with τ = 7 and ν = 4 using only 3 pieces.
- Decide which values ν can take when τ = 9.
Room 10 · Concordant pairs
Matching and cover studied together. After the two definitions (a pair (M, C) is concordant if C covers and every edge of M has exactly one end in C; the defect is f = |C| − |M|), the student decides on two 6 + 6 bipartite graphs whether the pair shown is concordant, with four options whose mistake is explained one by one. In the first, the edge a3–b3 of M has both ends in C; in the second the pair is concordant (f = 2), although several edges outside M have both ends in C: that is the temptation. Then comes the question of what f = 0 guarantees: that M is maximum and C minimum, because |M| ≤ ν ≤ τ ≤ |C|. The final challenge is to build a concordant pair with f = 0 on a 7 + 7 bipartite graph with 19 edges, ν = τ = 6 and a single minimum cover, which mixes both sides; the room says what fails: C does not cover, an edge of M touches C twice, or the defect is not zero.
Student tasks
- Decide whether a pair (M, C) is concordant and understand why the other options fail.
- Deduce what a zero defect guarantees.
- Build a concordant pair with f = 0.
Room 11 · Operation 1
A short definition of operation 1 (an augmenting path whose vertices alternate inside C, outside C, …: M grows by one edge, C does not change and f drops by 1) and a slow animation on a 3 + 3 example: find the vertex of C with no partner, walk the path with a green corridor behind the edges, flip it stage by stage, and f drops from 1 to 0. Then three simple challenges, each with «Watch the explanation» and, on success, the operation animated stage by stage with «Watch again»: a 3 + 4 graph with f = 1 and a single valid path of 3 edges; a 4 + 4 graph with f = 2 where the two vertices of C with no partner are joined by an edge (the tempting path a4–b2 enlarges M but does not alternate with C and is rejected) and the valid path has 3 edges; and a 4 + 5 graph with f = 2 and a valid 5-edge path, with a shorter tempting path that ends inside C. Every mistake is explained and every challenge has its own two hints.
Student tasks
- Mark the path of operation 1 on a 7-vertex graph.
- Tell any augmenting path apart from the one that works for operation 1.
- Find a 5-edge path that alternates with C.
Room 12 · Operation 2
It starts with the simplest case, switching off a camera that is not needed (S of a single vertex), with its own animation and challenge, before the general case. The definition of operation 2 as an algorithm (start at a vertex of C with no partner, follow its edges out of C, put into S the partners of the vertices reached, repeat; then S leaves C and its partners come in) and a slow animation on a small example. Three challenges of growing size, each with «Watch the explanation» and, on success, the operation animated stage by stage: a 4 + 4 graph with an S of 2 vertices, a 5 + 4 graph with a chained S of 3 vertices, and a 7 + 6 graph with an S of 4 vertices that spreads through two levels; in all three M is maximum (no augmenting path), f = 1 and there is only one valid S. Mistakes are explained (S not independent, an edge would be left uncovered, the defect does not go down). At the end, a summary of the two operations on one pair (4 + 5, f = 2): operation 1 with a 3-edge path (f drops to 1) and operation 2 with an S of 2 vertices (f drops to 0), in a stage-by-stage animation, and a text: operation 1 changes only M (it grows by one edge), operation 2 changes only C (it loses as many vertices as there were vertices with no partner in S), and both keep the pair concordant and lower f.
Student tasks
- Build S by following edges out of C and then partners, on three boards of increasing size.
- See what changes with each operation (M or C) on one and the same pair.
Room 13 · Zero defect
König's theorem lived before it is stated, and the only room where the two operations are combined. Two big buttons choose the operation («I will do operation 1 (mark a path)» or «I will do operation 2 (mark S)»), the active one is highlighted, one line says what to mark and a single button applies the chosen operation; the error messages of one operation never mention the other. First challenge: a random 5 + 5 bipartite graph, with M empty and C equal to one side, and with ν = 4 < 5, so to reach f = 0 enlarging M is not enough: C has to be reduced with operation 2. Second: a 7 + 7 graph with 17 edges, half built (|M| = 5, |C| = 8, f = 3), which is always solved with exactly two operations 1 and one operation 2, and with at least one 5-edge path. On reaching f = 0, M and C blink together (it can be replayed). Third: a non-bipartite graph with 11 vertices (a pentagon with two branches) where at the start only operations 2 are available; the defect goes down to f = 1 and no operation applies any more, and the student has to declare it («It cannot go any lower»): doing so too early counts as a failure. A final question: what prevents it? An odd cycle (here ν = 5 and τ = 6); the room refutes the options of the even cycle, the degree-1 vertex and the vertex with three neighbours using the graph itself. It ends with König: in bipartite graphs, ν = τ. The hint (free, after two failures or 60 s without progress) first shows the starting vertex and, when pressed again, draws the operation that works and switches on its button; at the fifth failure the room applies it.
Student tasks
- Bring a random 5 + 5 bipartite graph to zero defect when operation 2 is needed.
- Do it on a 7 + 7 that demands two augmenting paths and a change of C.
- Recognise when the defect cannot go lower in a graph with an odd cycle, and explain why.
Room 14 · Club delegates
A different delegate for each club: 7 clubs and 8 people, and the student taps the line joining a club to one of its members. The first challenge has a solution (17 edges, 4 assignments), but going club by club with «the first free member» gets stuck at the seventh, and chosen at random it only works about 18% of the time; the hint reminds the student that Cris and Eva are only in Theatre. The second challenge has the same statement and the same two buttons but no solution (ν = 6): here «It cannot be done» is the right answer, and then it has to be proved by marking the only group of clubs that prevents it, five clubs (Choir, Dance, Judo, Painting and Climbing) with only four people between them. In the first, pressing «It cannot be done» counts as a failure; if the group marked does not work, the room says how many people it adds up to. It ends with Hall's condition as a necessary condition.
Student tasks
- Assign a different delegate to each of the seven clubs.
- Decide that the second version cannot be done.
- Mark the group of five clubs that has only four people.
Room 15 · Hall detective
Four 7 + 7 bipartite graphs with 20 edges and no vertex of degree 1, with the question: is there a matching that saturates A? The answers, in order, are yes, no, no, yes. The student chooses the branch and proves it: with the matching (each of the two «yes» graphs has 4 perfect matchings and the greedy method gets stuck) or with a group S of A with |N(S)| < |S|. In the two «no» graphs the violating group is unique and cannot be seen by looking at degrees: in the second it is 4 vertices with only 3 neighbours, and a7, which has degree 2, is not in S; in the third, 5 vertices with 4 neighbours. Choosing the wrong branch counts as a failure and is explained, and each graph has its own second hint. It ends with Hall's theorem: the condition is not only necessary, it is also sufficient.
Student tasks
- Decide for each of the four graphs whether there is a matching that saturates A.
- Give the certificate: the matching or the group S that prevents it.
Room 16 · Rooks on painted squares
In the 8 × 8 challenge rooks can be tried before answering, and the board can be viewed as a rows–columns graph, synchronised with the rooks. If every row and every column has r painted squares, n non-attacking rooks always fit. Three challenges. First, a 7 × 7 board with 20 painted squares, which is not regular and has 4 complete placements: going row by row to the leftmost free column gets stuck at row 7. Second, an 8 × 8 board with 24 painted squares on which 8 rooks do not fit: with the board locked the student predicts how many fit, 6, and then places them; rows 1, 2, 4, 5, 7 and 8 only have squares in columns b, c, g and h (six rows for four columns), and the room marks them after three failures. Third, a multiple-choice question on why n rooks always fit when there are r per row and per column: k rows hold rk squares, which touch at least k columns (Hall). Among the wrong answers, that the total is a multiple of n (the previous 8 × 8 refutes it) and the rule of the first free column (which fails on a 4 × 4 with 2 squares per row).
Student tasks
- Place 7 rooks on a board where the greedy method gets stuck.
- Predict and place the maximum number of rooks (6) on an 8 × 8 where they do not all fit.
- Explain with Hall's condition why they always fit when every row and column has r squares.
Room 17 · The card trick
A 52-card deck dealt at random into 13 piles of 4: one card must be chosen from each pile so that all 13 values come out. While choosing, the room only counts how many piles you have done; the values that come out and the ones repeated are shown marked when pressing Check. The deck can be shuffled again as many times as wanted and there is always a solution. After two failed attempts a hint button appears that fixes one card, and after three the room shows a solution (not counted as a success). It ends with a multiple-choice question on why it can always be done: k piles hold 4k cards and, since there are 4 of each value, among them there are at least k different values; it is Hall with piles and values, because the piles–values multigraph is 4-regular. Each wrong answer is refuted (counting cards is not enough, suits do not matter, a pile can repeat a value).
Student tasks
- Choose one card from each pile so that all 13 values come out.
- Explain with Hall's condition why it can always be done, however the cards are shuffled.
Room 18 · The assignment problem, by eye
Four translators and four documents, with a 4 × 4 table of the hours each one needs for each document. First the student computes what the greedy strategy adds up to, in which each translator, in order, takes the quickest document still free: 17 h. Then the student picks by hand one cell per row and column with the smallest total possible. There are 24 assignments and the optimum is unique, 12 h (T1–D4, T2–D3, T3–D2, T4–D1), only 2 h better than the second best; it uses neither the minimum of T1's row nor that of T4's, so deciding row by row is not enough. When wrong, the room only says the total reached (and warns that the student is close if it is within 2 h of the optimum); when right, it shows that it is the only 12 h assignment among the 24.
Student tasks
- Compute the total given by the greedy strategy (17 h).
- Find the assignment with the smallest total, 12 h, among the 24 possible ones.
Room 19 · Subtracting changes nothing
The same 4 × 4 table is used. First the student computes by how much the total of one given assignment changes if 2 is subtracted from row T2 and 5 is added to column D4 (+3, with sign). Then comes the question of whether that change alters which assignment is optimal; among the four options each mistake is refuted: every assignment uses exactly one cell of each row and of each column, and that is why all of them change by the same amount. The final challenge is six sliders (from 0 to 9) on a 3 × 3 table: subtract an integer from each row and each column until no negatives are left and there are three independent zeros. The table marks zeros and negatives, and it is checked when a slider is released. There is only one solution (rows 3, 0, 4 and columns 0, 3, 1), and the subtlety is that subtracting from each line its minimum is not enough: it leaves at most 2 independent zeros. A hint appears after 12 moves and the solution after 30.
Student tasks
- Compute by how much an assignment's total changes when subtracting from a row and adding to a column.
- Explain why the optimal assignment does not change.
- Get three independent zeros with no negatives using the sliders.
Room 20 · The Hungarian method, step by step
The matrix is reduced step by step: the student writes the minimum of each row and the matrix changes on screen; then that of each column; then counts zeros, covers them with the fewest lines, adjusts and builds the assignment, always with the current matrix in view. The 4 × 4 table of hours, transformed step by step with the Hungarian method and two adjustments; the unique optimum is 20 h. First the row minima (5, 2, 2, 3) and the column minima (0, 0, 2, 0) are subtracted and the remaining zeros are counted: 6. Then the student finds the maximum number of independent zeros (2) and covers all the zeros with as few lines as possible by clicking the headers (2: row T3 and column D4; here König appears, applied to the matrix of zeros). Next the student computes the value of a cell after the first adjustment (the one at T3 and D4, where the two lines cross, with smallest uncovered value 1), how many lines are needed now (3) and the value of another cell after the second adjustment (smallest uncovered value 4). Finally the student marks four zeros that form a complete assignment and computes its cost in the original table: 20 h, with T1–D2, T2–D4, T3–D1 and T4–D3. Each question has two hints and a solution.
Student tasks
- Reduce rows and columns and count the remaining zeros.
- Find the independent zeros and cover them with the minimum number of lines.
- Apply two adjustments and compute the value of a cell after each.
- Mark the assignment of zeros and compute its cost in the original table.
Room 21 · The technicians
With the reduced table in view and a live sum of the marked cells. Five technicians and five faults, with a 5 × 5 table and no guidance: the student has to pick the assignment with the smallest total, 22 h (optimal and unique; the greedy method by rows gives 33 h). The two reductions alone are not enough, because 4 lines are still needed to cover the zeros, so an adjustment is needed; the warning that the student is close only appears within 1 h of the optimum. Then comes a profit-maximising problem, with four sales reps and four areas: first the student chooses how to turn it into a minimising one (subtract each profit from the largest in the table, 19; taking the reciprocal 1/b or replacing by ranks gives an assignment of only 52 thousand € against 54, and dividing only changes the scale) and then picks the assignment with the largest profit, 54 thousand € with C1–Z3, C2–Z4, C3–Z1 and C4–Z2. Taking the maximum of each row does not work: C2 and C3 both want Z4, and C1 and C4 both want Z3.
Student tasks
- Find the assignment with the smallest total on a 5 × 5 table with no guidance.
- Choose how to turn a maximising problem into a minimising one.
- Find the assignment with the largest profit.
Room 22 · Blocking pairs
Five students and five internship companies with their complete preference lists, and the definitions of assignment, blocking pair and stable assignment. It starts with a step-by-step animation (with people and with a graph) on a 3 × 3 example: what a blocking pair is and is not. Then four graded challenges (3 × 3, 4 × 4 and two 5 × 5): the student points out a blocking pair (choosing a student and a company) or presses «It is stable»; tapping a student marks the companies they prefer to their own, and each failed attempt says who prefers what. The animation can be replayed in every challenge.
Student tasks
- Decide whether each assignment is stable and, if not, point out a blocking pair.
- Tell a blocking pair apart from one in which only one of the two prefers.
Room 23 · Gale and Shapley
The deferred-acceptance algorithm, run by the student in a table of rounds (one row per round, one column per receiver), with the same preferences as the previous room and the lists coloured as in the animation (amber: application, green: kept, red: rejected and crossed out). First the students apply for a place (4 rounds, 11 applications, with two chains of rejections: Ana displaces Carla at S and Elena displaces David at P): in each round the student taps, in the list of each free student, the first uncrossed company and, once the last one is marked, decides in each column whom each company with candidates keeps (the new ones and the one it already held); the room computes nothing for them. It is a mistake to apply with someone who already has a partner, skip an uncrossed option or pick a worse candidate, to move on to the next round with nobody free, or to press “Done” with someone still free: each mistake counts as a failure and is explained, and three in a row bring up the full hint (a three-level hint at each step). Then the companies offer the position (another 4 rounds, 9 offers, with 4 decisions between two candidates). The result does not depend on the order in which the free ones are handled. Two of the three stable assignments come out, differing in 4 of the 5 companies. Then an exploration challenge: starting from those two, the student looks for the missing one by pairing in the graph (tapping a person and a company) and checking with «Is it stable?», which marks blocking pairs in red. The hints show that each student ends up between their two Gale–Shapley companies and how to go from one stable assignment to another with a downward chain (a rotation); at the end it is explained that this yields all of them (Irving and Leather, 1986). A final question: when the students propose, what does each company get? Its worst stable partner; whoever proposes wins. When the third stable assignment is found, the room explains why it exists: for some students there is a gap between their two Gale–Shapley companies, and the third one falls in it. It ends with the 2012 Nobel and the assignment of medical residents.
Student tasks
- Run the algorithm when the students apply, writing each round in the table: the applications and the decision of each company.
- Repeat it when the companies propose and compare the results.
- Recognise which side comes out ahead.
- Find the third stable assignment with a rotation.
Room 24 · The arctic circle
Dominoes and lozenges chosen at random. Part A: the Aztec diamond AD(n) (rows of 2, 4, …, 2n, 2n, …, 4, 2 squares) and its domino tilings, which are perfect matchings. The student builds by hand the 8 tilings of AD(2) (with a hint and an “I cannot find more” button), works out how many AD(4) has from 2, 8 and 64 (2^(n(n+1)/2), Elkies–Kuperberg–Larsen–Propp, 1992) and predicts what will be seen when one tiling of a large diamond is chosen at random. Then the exact draw is shown with the domino shuffling algorithm (destroy, slide, create), with play, pause, speed, step by step and size up to n = 150: four single-colour zones appear and, between them, the inscribed circle (arctic circle theorem, Jockusch–Propp–Shor, 1995). Part B: the hexagon with sides a, b, c on the triangular lattice and its lozenge tilings (perfect matchings of the honeycomb), which with three shades look like piles of cubes in an a×b×c box. The student flips vertices (adding or removing a cube), finds that going from the empty to the full box takes abc flips (8 in 2×2×2), that the lozenges of each shade are always a·b, b·c and a·c (15 dark ones in 3×4×5) and predicts the shape of the disordered zone of a large hexagon. A last board lets the full box melt through random flips (Glauber dynamics) until the circle appears (the inscribed ellipse when a, b, c differ; Cohn–Larsen–Propp, 1998). It closes with the common idea: all of this is perfect matchings chosen at random.
Student tasks
- Build the 8 tilings of AD(2).
- Deduce that AD(4) has 1024 tilings.
- Predict the shape of the disordered zone of a random tiling of the diamond.
- Watch the diamond grow with domino shuffling up to the arctic circle.
- Flip the lozenge hexagon and compute the minimum number of flips from the empty to the full box (8).
- Count the lozenges of one shade in the 3, 4, 5 hexagon (15 dark ones).
- Watch the box melt into the inscribed ellipse.
Rooms to project
The most striking ones to show and discuss in class.