Maths IA · Modelling · topic 94 of 97
Exam timetables: how few sessions are needed? · IB Maths IA idea: guide, sample graph and step-by-step plan
clash = edge, session = colourTwo subjects cannot sit in the same exam session if a single student takes both. How few sessions can a whole school get away with? You're going to find a lower bound, an upper bound, and close the gap.
- ✓ you like scheduling puzzles with a hidden structure
- ✓ you are happy learning a new idea and explaining it fully
- ✓ you can get anonymised or simulated subject-choice data
The big idea
Make each subject a vertex and join two subjects whenever some student takes both. A timetable is then a colouring: give each vertex a colour (a session) so joined vertices differ. The fewest colours is the chromatic number. Graph colouring is not in either course, so you must explain it from scratch, building on the graph vocabulary of AI HL. A group of subjects that all clash with each other forces that many sessions, which gives a lower bound; a greedy method gives an upper bound. The method is routine. The marks come from closing the gap: when does greedy fail, how does the order of subjects matter, and how close do the bounds get on real or simulated data?
Make it yours: pick one twist
Copying a classic won't show your choices. Pick one of these (or invent your own) and your IA becomes yours.
Swipe for more twists →
Turn a table of students and their subjects into an adjacency matrix, and check it against the table for a few students.
→ A matrix built from data. Explain what a high-degree vertex means for the timetable.Find the largest group of subjects that all clash with each other (a clique) and explain why that many sessions are needed.
→ A proof by counting. Check whether the lower bound is also enough, and what it means if it is not.Colour with the greedy method in different orders, then in order of decreasing degree (Welsh-Powell), and compare the number of sessions.
→ An algorithm whose answer depends on the order. Count how many orders give the best colouring.Show that greedy never needs more than one more colour than the largest degree, and that Welsh-Powell gives a sharper bound.
→ A proof that uses the greedy method's rule. Compare each bound with the colouring you actually found.Limit how many papers fit in a session, or add a room-capacity rule, and see how the answer changes.
→ A harder problem than colouring alone. Say why the earlier bounds no longer apply.Use anonymised subject choices from a school, or simulate a cohort with realistic subject popularity.
→ Real data is denser than a textbook example. Check how the number of sessions grows with cohort size.Your Maths IA research question: run the check
real, anonymised or simulated?Write your own question first. Then make sure it ticks every box:
- Names the cohort, the number of subjects and students, and where the choices come from (real, anonymised or simulated).
- Says what a session is, and what counts as a clash.
- Names the quantity found: the fewest sessions, or the gap between a bound and an algorithm.
- Says how you will know the answer is the fewest: a matching lower bound or an exhaustive check.
- States what is left out: room sizes, exam lengths and special arrangements.
The model
Subject choices become clashes, and clashes become a graph to colour. Draw the conflict graph of your own cohort and colour it.
How your Maths IA could be laid out
The usual order for a topic like this, what each part needs to show, and roughly how much of your 12 to 20 pages it takes. The words are all yours.
The timetabling problem, why fewer sessions matter and a prediction before any method.
Vertices, edges and the adjacency matrix, with your data summarised and its source explained.
Chromatic number, cliques and the lower bound, each explained from first principles.
Both methods run on a small case and on your data, with the number of sessions for each.
A proof that the bounds hold and an exhaustive check on a small graph.
How the number of sessions grows as you add students or subjects.
Back to your aim: the fewest sessions found, and how sure you are it is the fewest.
Real exam rules, room sizes and fairness to students. Say which constraint would change the answer most.
Where the algorithms, bounds and data came from.
What your Maths IA graph could look like
plot the lower bound tooMade-up values to show the form of a strong graph: the number of sessions needed as the cohort grows. Yours will look different. example only
- Sessions needed is a count, so the points should sit at whole numbers, joined or fitted only if you can justify it.
- A curve is a claim: say what model it comes from and where it should stop.
- Plot the lower bound from a clique as well, so the gap is visible.
- Say how many cohorts you simulated for each point.
The maths in action
worked through, not sketched!The graph above was a sketch with made-up numbers. This figure works the idea through from the model itself, so you can see what a finished figure looks like. The source line under it says where every number comes from.
Your game plan
Tick steps off as you go. We'll remember on this device.
0 of 10 done
- Read and predictFind out what graph colouring is. Before any method, guess how many sessions a small cohort needs.
- Get the dataUse anonymised subject choices from a school, or simulate a cohort with realistic popularities and say how you chose them.
- Draw the conflict graphMake a vertex per subject and an edge for every clash. Write the adjacency matrix and check it against three students.
- Trial run (1 lesson)Colour a graph of 6 vertices by hand, find the fewest colours, and explain how you know it is the fewest.
- Find a lower boundFind the largest clique in your graph and explain why that many sessions are needed.
- Colour greedilyRun the greedy method in two or three orders, then Welsh-Powell. Compare sessions and show every step.
- Go further, with a reasonProve an upper bound, test random cohorts of different sizes, or add a session-size limit. HL: this is where the rigour for criterion E comes from.
- Close the gapWhere your bounds differ, check all colourings of a small case or argue that no better colouring exists.
- Reflect as you goAfter every result write one line on what it means for a real timetable and what it ignores. These lines become your evaluation.
- Cut, check, then sendCheck every graph is labelled, every symbol is defined once and the conclusion answers your aim. Then send your teacher one draft.
The maths you'll use
- Conflict graph and adjacency matrix – Build if some student takes both subject and subject , and read degrees from the row sums.
- Lower bound by clique – Find the largest clique and show every colouring needs at least colours.
- Greedy colouring – Colour vertices in a given order using the smallest colour not used by a neighbour, and count the colours used.
- Welsh-Powell bound – Order vertices by degree and show that .
- Simulation – Generate random cohorts with realistic popularities and estimate the mean number of sessions with a confidence interval.
Key equations
Syllabus links
- 1.15Proof by induction, contradiction and counterexampleHL
- 3.14Graph theory: vocabulary and types of graphHL
- 3.15Adjacency matrices, walks and transition matricesHL
- 4.1Populations, samples, bias and sampling
- 4.2Presenting data
- 4.12Designing data collection; reliability and validityHL
Read up first
Data and sources to start from
Use anonymised subject choices from a school (with permission), or simulate students choosing subjects with realistic popularities.
References to cite
- Welsh, D. J. A., & Powell, M. B. (1967). An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1), 85-86.
- Appel, K., & Haken, W. (1977). Every planar map is four colorable. Part I: Discharging. Illinois Journal of Mathematics, 21(3), 429-490.
- Wilson, R. J. (2010). Introduction to graph theory (5th ed.). Pearson.
Cite what you actually use, in your own format, and say where each number came from.
Traps to avoid in this Maths IA
greedy is only an upper bound- Calling the greedy answer the chromatic number. It is only an upper bound unless it meets a lower bound.
- Using real students' names or identifiable subject combinations. Anonymise the data and say how.
- Joining two subjects when no student takes both. A clash needs at least one shared student.
- Forgetting that the order of subjects changes the greedy result.
- Assuming the four colour theorem applies. A conflict graph is usually not planar.
- Giving a lower bound with no proof that the clique you found is the largest one.
More Maths IA ideas like this
Shortest route: how good is a quick heuristic?●●○
Matching students to places: the Gale-Shapley algorithm●●●
Walk every bridge once: from Königsberg to your city●●○
This guide shows how a topic like this is usually approached. It is not an IA. Your question, choices, data, analysis and words must be your own: change something, tell your teacher where the idea came from, and follow your school's rules on outside help.