Yale-NUS faculty and students successfully collaborated to prove a mathematical theorem

Asst Prof Matthew Stamps and his students Khwa Zhong Xuan and Luo Xinyu, together with alumnus Christian Go (not in photo), have successfully proven a theorem in combinatorics. Image by Glen Ang for Yale-NUS College. 

A Yale-NUS team, comprising two students, an alumnus and a faculty member, has successfully proven a theorem in combinatorics, an area of mathematics about counting and arranging.

Assistant Professor of Science (Mathematics) Matthew Stamps, Khwa Zhong Xuan and Luo Xinyu (both from the Class of 2020) and alumnus Christian Go (Class of 2017) have proven a theorem on spanning tree enumeration, a subfield in combinatorics. Combinatorics has many applications ranging from logic, statistical physics and computer science to evolutionary biology. These include computer network routing protocols and civil network planning, as well as design networks in areas such as telecommunication, water supply and electrical grids.

The team’s work built upon a paper co-written by Asst Prof Stamps and Associate Professor Steven Klee of Seattle University in February 2019, titled ‘Linear algebraic techniques for spanning tree enumeration’. In the paper, the two mathematicians introduced new techniques for proving spanning tree enumeration formulas in networks, based on several well-known results in the field of linear algebra. The result greatly simplifies the process of computing the number of spanning trees in significant families of networks.

“These new techniques enable us to produce simple proofs of several known formulas in the literature,” said Asst Prof Stamps. “Additionally, they are accessible to undergraduates, not requiring any sophisticated mathematical theory beyond linear algebra. This makes the topic well-suited for students to pursue as capstone projects.” The paper is slated for publication in the American Mathematical Monthly, the most widely-read mathematics journal in the world.

At Yale-NUS, all students round off their academic journey with a year-long capstone, an independent, in-depth research paper or project within their chosen major. For students like Zhong Xuan and Xinyu, the capstone can take the form of a collaboration with faculty on an active line of research.

Image by Glen Ang for Yale-NUS College. 

In August last year, Zhong Xuan, Xinyu, Asst Prof Stamps and Mr Go, who is currently a teaching assistant at the National University of Singapore (NUS)’ Department of Mathematics, started meeting weekly to work together to understand the various lemmas (intermediate theorems in a proof) needed to prove Asst Prof Stamps’ original theorem. By the fourth meeting, the team successfully came up with a new theorem, which explicates the conditions that a network must fulfil such that its spanning trees can be successfully enumerated with one of the methods in Asst Prof Stamps’ original paper. This then allows for the original theorem to be applied to a broader range of graphs, beyond those in the original paper.

Following this success, Zhong Xuan and Xinyu both built upon the new method in their capstone projects, each focusing on different aspects of spanning tree enumeration.

For Xinyu’s capstone, she focussed on combinatorics and is working to extend Klee and Stamps’s enumeration method to the study of bipartite networks, an effort which would have various practical applications. She explained, “In computer networks, we usually require each router to remember a spanning tree structure to avoid routing loops or redundant connections. Applications like this motivate us to study the number of spanning trees in graphs.”

Zhong Xuan’s capstone, on the other hand, focuses more on linear algebra. He translated the combinatorial properties of Ferrers and threshold networks into linear algebraic terms. This allowed him to count the number of spanning trees using a single nesting property, which was simpler than the proofs provided in the original paper.

For both students, the research process has come with a set of challenges and insights. “I realised that learning about theorems and conducting research are very different,” said Xinyu. “When studying theorems proven by previous mathematicians, I often marvelled at their ability to construct something so brilliant.”

“However, when trying to prove a conjecture myself, I realised that this process takes a much longer time, and that clever twists do not happen groundlessly but through a countless number of trial and errors.”

At the same time, collaborating with Asst Prof Stamps to develop novel research insights was a source of excitement for Zhong Xuan. “The approach we’re taking is not one that’s commonly used to address this problem, so much of the project has been delving into relatively unknown areas,” said Zhong Xuan.

“While I’m still hopeful of finding a better categorisation of the networks, I’m excited to see everything is coming together and also about the prospect of writing a paper to share our findings.”