Graph Theory students explore the math of chess, magic squares, more

If you’ve ever played chess, you’ve probably noted how the knight’s peculiar L-shaped move takes it around the board.  
You’re not alone; its idiosyncrasy been examined by poets, philosophers and mathematicians (including Euler) for a thousand years.
Among the most recent is New College student Michael Dwyer, who studied a classic math problem related to the knight for Professor of Mathematics Eirini Poimenidou’s “Graph Theory” course. He explained it at the class’s semester-end poster presentation.
“The general idea of the Knight’s Tour problem is that you’re trying – using only legal chess moves – to take a knight to every square of the chessboard exactly one time,” Dwyer said. “This relates to graph theory because we can translate the chess board and the possible moves the knight can make at each square into a graph.”
In the graph, he said, each square on the chessboard represents one vertex, and the edges between the vertices are represented by the legal moves the knight can make. From there he goes on to discuss the concept of the Hamiltonian cycle or path, of which the knight’s tour is a specialized case; how the problem changes in cases where you alter the size of the chessboard, where m and n represent the number of squares on a side; “a-b” moves by the knight, and more esoterica.
Dwyer sounds another New College mathematician, in the tradition of the late Fields Medal winner Bill Thurston – except he’s not. Not officially, anyway. Dwyer, form Lakeland, is a third-year humanities student, and his other classes this semester are “The Berlin Wall in Literature,” “Introduction to Psychology,” and “Buddhism in the Himalayas.”  But New College’s academic system, with no numeric grades, encourages students to take on any classes that interest them, which is what Dwyer did.
“I’ve enjoyed math ever since I was in elementary school,” he said. “So I take it because it’s fun, at the end of the day.”
In fact, almost half the students in the class are not concentrating in mathematics. Poimendou said that while graph theory might seem complex, it’s well within the reach of any student.
“Graph Theory is very accessible” she said. “All it is really is lines and dots. You can think of the dots for example as people with a line connecting them if they know each other.  Or dots can represent cities with the line connecting two cities being the distance between them. Or you can also think of dots as people and tasks, with a line between a person and a task if the person can perform that task. Graph theory is a rich branch of mathematics and it has many practical applications.”
“The techniques involved can be quite sophisticated, but the problems themselves are quite accessible.”

That was why Alana Gold, a third-year literature and Latin student, chose to tackle “The Oberwolfach Problem,” which is not the title of a Robert Ludlum novel.
“The Oberwolfach Problem is a problem in graph theory that started out as a seating arrangement problem,” Gold said. “Is it possible to sit an odd number of people around round tables for a certain number of nights such that everyone sits by each other at least once?”
The answer, she explained, is “usually,” demonstrating a process known as the “turning trick” to demonstrate a solution. Some cases are known to be impossible to solve, but other cases have been proven solvable, and mathematicians believe all other cases have solutions.
Gold chose the topic because it was mathematically challenging and yet had real-world applications:  “It’s actually a very practical problem, because it can be helpful not only in seating arrangements but in arranging schedules for multiple people and handling conflicts.”
Natalie Roldan examined magic squares, grids of numbers where the rows, columns and diagonals add to the same number.
As a history student, Roldan found the topic fascinating. “The historical background is really cool, because you think that most math is old, but this is really old. It goes back to 1514,” she said.  “The different kinds of magic squares and how they can be converted into complete bipartite graphs is really cool.”
And like Gold, she found a practical aspect as well: “Now I have more strategies to solve them. It’s not just a give and take and a guess and try to erase and do it again!”
Finally, in case you were wondering: Yes, the knight can make a tour of the entire chessboard, and with maximum efficiency. While there are 33 trillion ways the piece can tour the board, Dwyer said, it can reach every space on the board in just 63 moves – one for each square on the board after its starting point. And that’s fascinating, he said.
“I like chess – I’m not good at it by any means – but it gives me enough joy to figure out these little quirks about the chessboard.”
And the next time he plays, he added, he might have a way to show off.
— David Gulliver is interim associate director of the Office of Communications and Marketing at New College of Florida.