Image of sample graph

Graph Brain Project Tackles Graph Theory Problems

For the past four years, Associate Professor Dr. Craig Larson in the Department of Mathematics and Applied Mathematics has been running a summer research program for interested undergraduate and graduate students, and even high school students and other faculty. Larson’s Graph Brain Project provides students and faculty the opportunity to do research on widely-studied Graph Theory problems. This year participants conducted research on finding necessary or sufficient conditions for graph hamiltonicity — a widely studied, and very difficult, problem.

Dr. Craig Larson

Dr. Craig Larson

Dr. Larson, who earned his Ph.D. in Mathematics at the University of Houston in 2008, held the first Graph Brain Project summer workshop in 2015 as a way to experiment in how the use of automated mathematical discovery software, databases, large collaboration, and systematic investigation provide a model for how mathematical research might process in the future. For the last two years Assistant Professor Dr. Neal Bushaw has co-organized the workshop. Dr. Nico Van Cleemput of Ghent University (Belgium), a frequent visitor to VCU has also been a key participant.

Dr Larson says that collaboration is essential to mathematical discovery. Discovery either builds on the work of others—or is the direct result of working together. The Graph Brain Project gives students an opportunity to experience this kind of collaboration and to work towards a mathematical goal. Dr Larson often tells his students: “Together we know more than any of us does individually.”

“The Summer Research [program] was designed so people of every level can make contributions,” said Larson. “Every mathematical theorem starts as a “conjecture” (a mathematician’s word for a hypothesis). Larson and Van Cleemput have written software that can make mathematical conjectures. Students can learn how to use this program, and Sage—a general-purpose mathematical program—find counterexamples, generate improved conjectures—and learn lots of math along the way. These conjectures then need to be proved. “Faculty usually prove conjectures but everyone is shown how to use Sage and how to use the Conjecturing program and Graph Theory.”

The workshop has had 10 to 20 participants every summer—everyone is welcome—the only requirements are interest and enthusiasm. High school students, VCU students, various department faculty, students from other schools such as Virginia Tech and the University of Virginia, and even faculty from other universities have all come together to take part in the workshop. In the past, the workshop lasted three to four weeks with research being done Monday through Friday.

The project was motivated by research done by Larson and fellow colleagues involving automated mathematical conjecturing programs and developing a program that could be used to generate invariant-relation and property-relation conjectures in many areas of mathematics.

Larson and Van Cleemput’s Conjecturing program builds off of the idea that computers can easily generate and evaluate all expressions formed from standard mathematical ingredients and can easily check whether the statements formed are true at least for a relatively small numbers of example mathematical objects.

The workshop also focuses a great deal on graphs or networks. A graph is a mathematical object consisting of vertices and edges between them that can all connect to each other.

“Graph theorists investigate relationships between graph properties,” said Larson. “Two examples of a graph properties include having a cycle and having the number of edges equal the number of vertices. A conjecturing program might discover a relationship between these properties.” While this is a simple example, this same idea can be used to investigate relationships between properties of significant research interest—like graph hamiltonicity.

Graphs are used to model situations including molecular structure, the World Wide Web, social networks, and GPS satellite networks.

“Graphs cannot only be used to model real-world circumstances but theorems in graph theory can also be applied to other areas of mathematics,” said Larson.

“Every mathematical theorem, or a true math statement, starts as a conjecture,” said Larson. “The conjecturing program is used as a starting point for research.”

In this process, the program makes a conjecture and if it is disproved the counterexample may be added to the program. If it is true then the theorem or theoretical bound may be added to the program. In each case the process may be iterated and guaranteed to yield new conjectures. Dr Larson says that students have been exceptionally good at finding counterexamples to conjectures.

Larson stated that the ultimate goal of the workshop is to produce new mathematical knowledge and to prove these conjectures in an enthusiastic environment. It sounds like Dr Larson and his colleagues are having a lot of fun.

More information regarding the Graph Brain Project can be found at https://arxiv.org/pdf/1801.01814.pdf. A date for the Summer 2019 workshop has not been scheduled yet but will be occuring. If you are interested in participating please contact either Dr Larson or Dr Bushaw.

Written by Jess Wetzler