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

September 6, 2023

UBC mathematician Dr. Stephanie van Willigenburg and colleagues

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.

For more information, contact…

Chris Balma
  • Mathematics

Musqueam First Nation land acknowledegement

UBC Science acknowledges that the UBC Point Grey campus is situated on the traditional, ancestral, and unceded territory of the xʷməθkʷəy̓əm.

Learn more: Musqueam First Nation

Faculty of Science

Office of the Dean, Earth Sciences Building
2178–2207 Main Mall
Vancouver, BC Canada
V6T 1Z4
UBC Crest The official logo of the University of British Columbia. Urgent Message An exclamation mark in a speech bubble. Arrow An arrow indicating direction. Arrow in Circle An arrow indicating direction. A bookmark An ribbon to indicate a special marker. Calendar A calendar. Caret An arrowhead indicating direction. Time A clock. Chats Two speech clouds. External link An arrow pointing up and to the right. Facebook The logo for the Facebook social media service. A Facemask The medical facemask. Information The letter 'i' in a circle. Instagram The logo for the Instagram social media service. Linkedin The logo for the LinkedIn social media service. Lock, closed A closed padlock. Lock, open An open padlock. Location Pin A map location pin. Mail An envelope. Mask A protective face mask. Menu Three horizontal lines indicating a menu. Minus A minus sign. Money A money bill. Telephone An antique telephone. Plus A plus symbol indicating more or the ability to add. RSS Curved lines indicating information transfer. Search A magnifying glass. Arrow indicating share action A directional arrow. Twitter The logo for the Twitter social media service. Youtube The logo for the YouTube video sharing service.