Canadian mathematicians de-claw graph theory, nab U.S. award

Work disproving a 1995 theorem in graph theory has earned UBC mathematician Dr. Stephanie van Willigenburg and colleagues the 2023 David P. Robbins Prize.

In its simplest form, graph theory involves studying varying structures of connected nodes in which some nodes (called vertices in discrete mathematics) can be related. A typical example might represent individuals on a social network. A graph could also use nodes of different colours to represent times and connecting lines (edges) to represent individuals, helping to visualize schedules and conflicts.

In a 1995 paper on the chromatic symmetric function, former MIT mathematician Dr. Richard P. Stanley stated that there was no known graph that was not contractible into a claw pattern and whose chromatic symmetric function was not e-positive, that is, not a positive linear combination of elementary symmetric functions.

But along with Drs. Angèle Foley (Wilfrid Laurier University) and Samantha Dahlberg (now with the Illinois Institute of Technology), Dr. van Willigenburg disproved the theory by uncovering infinite families of graphs that are not contractible to the claw and whose chromatic symmetric functions are not e-positive.

“The claw pattern really has no general bearing on e-positivity,” explains Dr. van Willigenburg. “These families completely changed people’s ideas about the claw pattern, and opens up new avenues in graph theory—not only on the theoretical side, but for applications including scheduling, understanding social network interactions, and recommendations on content platforms.”

The researchers are the first women, and the first team of mathematicians based at Canadian institutions, to claim the prize.

Dr. Dahlberg says she enjoyed collaborating with curious researchers who found a challenging question that had long gone unanswered.

“Not only was it fun to spend time with them during our research meetings, but together we were able to improve our long messy proofs into short neat proofs,” she says. “It is great to be skeptical in mathematics, and it’s worth running computer searches even on well-believed conjectures.”

The researchers credit increases in computing power since Stanley wrote his paper in 1995 in helping the team accomplish the work. The first counterexamples in graphs with six vertices took less than a minute to complete. The team then ran programs to compute graphs with seven vertices, which took less then hour. Eight-vertex examples took three days to complete.

The team then searched for graphs with nine vertices to confirm their findings. However, the time needed was increasing exponentially and completing the search would have taken three years. Fortunately the graphs needed to confirm their findings were returned much sooner than that, and the team were ecstatic.

The David P. Robbins Prize recognizes novel research in algebra, combinatorics or discrete mathematics, and is awarded every three years by the American Mathematical Society (AMS) and the Mathematical Association of America (MAA).

Papers are judged on quality of research, clarity of exposition, and accessibility to undergraduates. The paper must have been published within six years of the presentation of the prize, and must be written in English. In the event of joint authors, the prize is divided equally.